15236721
Bounds on secret key exchange using a random deal of cards
We present a general model for communication among a “team” of players overheard by a passive eavesdropper, Eve, in which all players including Eve are given private inputs that may be correlated. We define and explore secret key exchange in this model. Our secrecy requirements are information-theoretic and hold even if Eve is computationally unlimited. In particular, we consider the situation in which the team players are dealt hands of cards of prespecified sizes from a known deck of distinct cards. We explore when the team players can use the information contained in their hands to determine a value that each team player knows exactly but Eve cannot guess.
207660233
Impossibility of distributed consensus with one faulty process
The consensus problem involves an asynchronous system of processes, some of which may be unreliable. The problem is for the reliable processes to agree on a binary value. In this paper, it is shown that every protocol for this problem has the possibility of nontermination, even with only one faulty process. By way of contrast, solutions are known for the synchronous case, the “Byzantine Generals” problem.
7656106
Geometric Searching in Walkthrough Animations with Weak Spanners in Real Time
We study algorithmic aspects in the management of geometric scenes in interactive walkthrough animations. We consider arbitrarily large scenes consisting of unit size balls. For a smooth navigation in the scene we have to fulfill hard real time requirements. Therefore, we need algorithms whose running time is independent of the total number of objects in the scene and that use as small space as possible. In this work we focus on one of the basic operations in our walkthrough system: reporting the objects around the visitor within a certain distance. 
 
Previously a randomized data structure was presented that supports reporting the balls around the visitor in an output sensitive time and allows insertion and deletion of objects nearly as fast as searching. These results were achieved by exploiting the fact that the visitor moves "slowly" through the scene. A serious disadvantage of the aforementioned data structure is a big space overhead and the use of randomization. 
 
Our first result is a construction of weak spanners that leads to an improvement of the space requirement of the previously known data structures. Then we develop a deterministic data structure for the searching problem in which insertion of objects are allowed. Our incremental data structure supports O(1+k) reporting time, where k is a certain quantity close to the number of reported objects. The insertion time is similar to the reporting time and the space is linear to the total number of objects.
15568865
Appraising two decades of distributed computing theory research
Abstract.The field of distributed computing started around 1970 when people began to imagine a future world of multiple interconnected computers operating collectively. The theoretical challenge was to define what a computational problem would be in such a setting and to explore what could and could not be accomplished in a realistic setting in which the different computers fell under different administrative structures, operated at different speeds under the control of uncoordinated clocks, and sometimes failed in unpredictable ways. Meanwhile, the practical problem was to turn the vision into reality by building networks and networking equipment, communication protocols, and useful distributed applications. The theory of distributed computing became recognized as a distinct discipline with the holding of the first ACM Principles of Distributed Computing conference in 1982. This paper reviews some of the accomplishments of the theoretical community during the past two decades, notes an apparent disconnect between theoretical and practical concerns, and speculates on future synergy between the two.
17113954
INTEGRATING ANTHROPOLOGICAL APPROACHES TO THE STUDY OF CULTURE: THE “HARD” AND THE “SOFT”
Much anthropological interest in methods derived from the natural sciences has been motivated by a search for tools with which to describe ethnographic settings in more “rigorous” terms. These have generally failed, and these failures are due to implicit conventions in anthropology regarding what to observe and how. I suggest that natural science methods were developed as a result of a process that aimed to solve problems that are generally different from those that social scientists pursue and that social scientists need to take the underlying ideas and rebuild them for their own purposes if they want to import them. Likewise, most qualitative anthropologists are also guilty of inappropriate borrowing, in particular in their importation of postmodern philosophy from literary criticism rather than adapting these ideas from the source in a manner more suited to the discipline. I examine some the conditions that would be necessary to integrate the various fractions of the anthropological community within a flexible but common framework. I conclude that anthropology must include a major qualitative perspective and, in response to this, suggest that if we are to formalize our study we must adopt some new conventions. These include a broadening of analysis beyond causality to include interpretive reasoning within a common framework, the addition of deontic operators to our basic formal framework, and an emphasis on declarative semantics over procedural semantics. We end by briefly describing some speculative work using Information Theory as a basis for quantitatively evaluating qualitative descriptions, models, and analysis.
16340460
Bi-directional Coupling of Simulation Tools with a Walkthrough-System
Visualising is amethod used to help experiencing a nd understanding causal cohesions in simulation processes. For this purpose, tools for visualising are already implemented in prevalent simulation systems. The user creates his imulation model and generates a 3-dimensional (2,5-dimensional) visualising by means of the simulation system. This helps examining the process which makes it easier for the viewer to “understand” it. Simulatio n tools usually only provide the opportunity for a unidirectional visualising. In a 3-dimensional surr ounding the viewer can not implement an interaction with the simulation while the system is running. Though an interaction during the simulation run enables the user to gain a better un derstanding of causal cohesions. Solutions via HLA are sophisticated and therefore rather suited f or extensive projects. We present a distributed system consisting of a com mercial manufacturing simulation tool, a coupling module and a walkthrough system. The distr ibuted system in conjunctions with the coupling module guarantees generality and a wide field of applications of the walkthrough system. Further it guarantees flexibility and selection of the specialized graphics hardware for the walkthrough system. A further contribution of this paper is the solution of the time synchronisation problem caused by simulation tool and walkthrough s ystem.
62681368
Lambda-calculus schemata
A lambda-calculus schema is an expression of the lambda calculus augmented by uninterpreted constant and operator symbols. It is an abstraction of programming languages such as LISP which permit functions to be passed to and returned from other functions. When given an interpretation for its constant and operator symbols, certain schemata, calledlambda abstractions, naturally define partial functions over the domain of interpretation. Two implementation strategies are considered: the retention strategy in which all variable bindings are retained until no longer needed (implying the use of some sort of garbage-collected store) and the deletion strategy, modeled after the usual stack implementation of ALGOL 60, in which variable bindings are destroyed when control leaves the procedure (or block) in which they were created. Not all lambda abstractions evaluate correctly under the deletion strategy. Nevertheless, both strategies are equally powerful in the sense that any lambda abstraction can be mechanically translated into another that evaluates correctly under the deletion strategy and defines the same partial function over the domain of interpretation as the original. Proof is by translation into continuation-passing style.