Modelling knowledge and action in distributed systems

We present a formal model that captures the subtle interaction between knowledge and action in distributed systems. We view a distributed system as a set ofruns, where a run is a function from time toglobal states and a global state is a tuple consisting of anenvironment state and alocal state for earch process in the system. This model is a generalization of those used in many previous papers.Actions in this model are associated with functions from global states to global states. Aprotocol is a function from local states to actions. We extend the standard notion of a protocol by definingknowledge-based protocols, ones in which a process' actions may depend explicitly on its knowledge. Knowledge-based protocols provide a natural way of describing how actions should take place in a distributed system. Finally, we show how the notion of one protocolimplementing another can be captured in our model. Joseph Y. Halpern received a B.Sc. in mathematics from the University of Toronto in 1975, and a Ph.D. in mathematics from Harvard University in 1981. In between, he spent two years as the head of the Mathematics Department at Bawku Secondary School, in Ghana. After a year as a visiting scientist at MIT, he joined IBM in 1982. He is currently the manager of the Mathematics and Related Computer Science Department at the IBM Almaden Research Center, and a consulting professor in the Computer Science Department at Stanford. His major research interests are reasoning about knowledge, distributed computation, and logics of programs. He was program chairman and organizer of the first conference of Theoretical Aspects of Reasoning About Knowledge, program chairman of the Fifth ACM Symposium on Principles of Distributed Computing, and was the co-recipient (with Ronald Fagin) of the MIT Publisher's Prize for the Best Paper Paper at the 1985 International Joint Conference on Artificial Intelligence. Ronald Fagin is manager of the Foundations of Computer Science group at the IBM Almaden Research Center. He received his B.A. degree in mathematics from Dartmouth College in 1967 and his Ph.D. in mathematics, specializing in mathematical logic, from the University of California at Berkeley in 1973. He joined IBM in 1973 at the Thomas J. Watson Research Center. In 1975, he transferred to the San Jose Research Laboratory (now the IBM Almaden Research Center) where most of his research has centered on applications of logic to computer science. In particular, he has done research on the theory of relational databases and, more recently, on theories of knowledge and belief. He has received three IBM Outstanding Innovation Awards for his contributions to relational database theory, extendible hashing, and reasoning about knowledge. He was co-recipient (with Joe Halpern) of the MIT Press Publisher's Prize for the Best Paper at the 1985 International Joint Conference on Artificial Interlligence.Some material in this paper appeared in preliminary form in Halpern and Fagin (1985). An abridged version of the paper appeared in Vogt F (ed) Proceeding of Concurrency 88 (Lecture Notes in Computer Science Vol. 335) Springer-Verlag, 1988, pp 18–32     

Ada/Mindstorms 3.0

The paper presents a computational environment built on the LEGO Minstorms RCX kit for introductory robotics and programming. The author describes the Ada/Mindstorms 3.0, a software environment for teaching using the LEGO Mindstorms RCX kit. He discusses the design choices made, the reasons for those decisions, and show examples of how the system works. Ada/Mindstorms has been used in computing classes at the US Air Force Academy and around the world and is freely available online.     

Social class, child age, and parental socialization values.

Upper-, middle-, and lower-class parents were asked to explain a proverb which had both "growth" and "stability" interpretations to their 11- and 16-yr-old sons. The growth interpretation was overwhelmingly endorsed by most parents. With 16-yr-olds, lower-middle-class parents continued to endorse the growth interpretation; most upper-class parents endorsed the stability interpretation. (PsycINFO Database Record (c) 2010 APA, all rights reserved)     

Field programmable gate arrays and floating point arithmetic

We present empirical results describing the implementation of an IEEE Standard 754 compliant floating-point adder/multiplier using field programmable gate arrays. The use of FPGA's permits fast and accurate quantitative evaluation of a variety of circuit design tradeoffs for addition and multiplication. PPGA's also permit accurate assessments of the area and time costs associated with various features of the IEEE floating-point standard, including rounding and gradual underflow. These costs are analyzed, along with the effects of architectural correlation, a phenomenon that occurs when the cost of combining architectural features exceeds the sum of separate implementation. We conclude with an assessment of the strengths and weaknesses of using FPGA's for floating-point arithmetic     

Determination of the DNA bend angle induced by the restriction endonuclease EcoRV in the presence of Mg2+

We have used the method of Zinkel and Crothers (Zinkel, S.S., and Crothers, D.M. (1990) Biopolymers 29, 29-38) to determine the degree of bending induced by the binding of the restriction endonuclease EcoRV to its recognition sequence (-GATATC-). A set of four calibration DNA fragments was constructed that contained zero, two, four, or six phased A-tracts in their centers and an EcoRV site at the 5'-end to account for the electrophoretic influence of the bound protein. The mobilities of these calibration molecules complexed with EcoRV were compared to that of a test DNA containing a central EcoRV site also complexed with EcoRV. The EcoRV-induced bend angle was found to be 44 degrees +/- 4 degrees. These experiments were performed with a catalytically inactive EcoRV mutant that still binds DNA specifically in the presence of Mg2+. In the absence of Mg2+, which is necessary for specific binding, there is no difference in the mobilities of the fragments with a peripheral or a central EcoRV site complexed with EcoRV, indicating that nonspecific binding on average does not lead to measurable DNA bending.     

Stochastic servomechanism design via optimal filter theory

The feedback realization of the continuous optimal filter is applied to familar problems of the design of servomechanisms with stochastic inputs and disturbances. This approach leads immediately to optimal feedback configurations and, interestingly, to integral plus derivative control for the wind torque disturbed antenna servo problem. As in optimal filter theory, time-varying gains are generated for the finite time or "lock on" problem. Since digital computer programs are already available for computing these gains the design of complex intercoupled servos is feasible. The application to "minimum bandwidth" servo design is indicated.     

Efficiently extendible mappings for balanced data distribution

In data storage applications, a large collection of consecutively numbered data “buckets” are often mapped to a relatively small collection of consecutively numbered storage “bins.” For example, in parallel database applications, buckets correspond to hash buckets of data and bins correspond to database nodes. In disk array applications, buckets correspond to logical tracks and bins correspond to physical disks in an array. Measures of the “goodness” of a mapping method include:

1. Thetime (number of operations) needed to compute the mapping.
2. Thestorage needed to store a representation of the mapping.
3. Thebalance of the mapping, i.e., the extent to which all bins receive the same number of buckets.
4. The cost ofrelocation, that is, the number of buckets that must be relocated to a new bin if a new mapping is needed due to an expansion of the number of bins or the number of buckets.

One contribution of this paper is to give a new mapping method, theInterval-Round-Robin (IRR) method. The IRR method has optimal balance and relocation cost, and its time complexity and storage requirements compare favorably with known methods. Specifically, ifm is the number of times that the number of bins and/or buckets has increased, then the time complexity isO(logm) and the storage isO(m ²). Another contribution of the paper is to identify the concept of ahistory-independent mapping, meaning informally that the mapping does not “remember” the past history of expansions to the number of buckets and bins, but only the current number of buckets and bins. Thus, such mappings require very little information to be stored. Assuming that balance and relocation are optimal, we prove that history-independent mappings are possible if the number of buckets is fixed (so only the number of bins can increase), but not possible if the number of bins and buckets can both increase.     

Reasoning about Knowledge: A Response by the Authors

Minds and Machines -