26397523
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.
15233558
A new look at fault tolerant network routing
Consider a communication network G in which a limited number of link and/or node faults F might occur. A routing &rgr; for the network (a fixed path between each pair of nodes) must be chosen without any knowledge of which components might become faulty. Choosing a good routing corresponds to bounding the diameter of the surviving route graph R(G,&rgr;)/F, where two nonfaulty nodes are joined by an edge if there are no faults on the route between them. We prove a number of results concerning the diameter of surviving route graphs. We show that if &rgr; is a minimal length routing, then the diameter of R(G,&rgr;)/F can be on the order of the number of nodes of G, even if F consists of only a single node. However, if G is the n-dimensional cube, the diameter of R(G,&rgr;)/F≤3 for any minimal length routing &rgr; and any set of faults F with |F|<n. We also show that if F consists only of edges and does not disconnect G, then the diameter of R(G,&rgr;)/F is ≤ 3|F|+1, while if F consists only of nodes and does not disconnect G, then the diameter of R(G,&rgr;)/F is ≤ the sum of the degrees of the nodes in F, where in both cases &rgr; is an arbitrary minimal length routing. We conclude with one of the most important contributions of this paper: a list of interesting and apparently difficult open problems.
14995360
A model-theoretic analysis of knowledge
A general semantic model of knowledge is introduced, to allow reasoning about statements such as «He knows that I know whether or not she knows whether or not it is raining». This approach more naturally models a state of knowledge than previous proposals (including Kripke structures). Using this notion of model, a model theory for knowledge is developed. This theory enables one to interpret the notion of a «finite amount of information»
47316226
Equations Between Regular Terms and an Application to Process Logic
Regular terms with the Kleene operations $ \cup $, ; and $ * $ can be thought of as operators on languages, generating other languages. An equation $\tau _1 = \tau _2 $ between two such terms is said to be satisfiable just in case languages exist which make this equation true. We show that the satisfiability problem even for $ * $-free regular terms is undecidable. Similar techniques are used to show that a very natural extension of the Process Logic of Harel, Kozen and Parikh is undecidable.
152014
Causality, Responsibility, and Blame: A Structural-Model Approach
This talk provides an overview of work that I have done with Hana Chockler, Orna Kupferman, and Judea Pearl (H. Chockler and J. Y. Halpern, 2004), (H. Chockler, et al., 2003), (J. Y. Halpern and J. Pearl, 2005), on defining notions such as causality, explanation, responsibility, and blame. I first review the Halpern-Pearl definition of causality, what it means that A is a cause of B, and show how it handles well some standard problems of causality. This definition of causality (like most in the literature) views causality as an all-or-nothing concept. Either A is a cause of B or it is not. I show how it can be extended to take into account the degree of responsibility of A for B. For example, if someone wins an election 11-0, each person is less responsible for his victory than if he had won 6-5. Finally, I show how this notion of degree of responsibility can be used to provide insight into model checking notions such as coverage
215949262
Knowledge, probability, and adversaries
What should it mean for an agent to know or believe an assertion is true with probability 9.99? Different papers [2, 6, 15] give different answers, choosing to use quite different probability space...
14707750
Probability Update: Conditioning vs. Cross-Entropy
Conditioning is the generally agreed-upon method for updating probability distributions when one learns that an event is certainly true. But it has been argued that we need other rules, in particular the rule of cross-entropy minimization, to handle updates that involve uncertain information. In this paper we re-examine such a case: van Fraassen's Judy Benjamin problem [1987], which in essence asks how one might update given the value of a conditional probability. We argue that--contrary to the suggestions in the literature--it is possible to use simple conditionalization in this case, and thereby obtain answers that agree fully with intuition. This contrasts with proposals such as cross-entropy, which are easier to apply but can give unsatisfactory answers. Based on the lessons from this example, we speculate on some general philosophical issues concerning probability update.
2990183
Performing work efficiently in the presence of faults
We consider a system of t synchronous processes that communicate only by sending messages to one another, and together the processes must perform n independent units of work. Processes may fail by crashing; we want to guarantee that in every execution of the protocol in which at least one process survives, all n units of work will be performed. We consider three parameters: the number of messages sent, the total number of units of work performed (including multiplicities), and time. We present three protocols for solving the problem. All three are work optimal, doing O(n+t) work. The rst has moderate costs in the remaining two parameters, sends O(t p t) messages, and takes O(n+t) time. This protocol can be easily modied to run in any completely asynchronous system equipped with a failure detection mechanism. The second sends only O(tlogt) messages, but its running time is large (O(t 2 (n+t)2 n+t )). The third is essentially time optimal in the (usual) case in which there are no failures, and its time complexity degrades gracefully as the number of failures increases.
16360228
Least expected cost query optimization: an exercise in utility
We identify two unreasonable, though standard, assumptions made by database query optimizers that can adversely affect the quality of the chosen evaluation plans. One assumption is that it is enough to optimize for the expected case---that is, the case where various parameters (like available memory) take on their expected value. The other assumption is that the parameters are constant throughout the execution of the query. We present an algorithm based on the ``System R''-style query optimization algorithm that does not rely on these assumptions. The algorithm we present chooses the plan of the least expected cost instead of the plan of least cost given some fixed value of the parameters. In execution environments that exhibit a high degree of variability, our techniques should result in better performance.
10093090
A decision-theoretic approach to reliable message delivery
Summary. We argue that the tools of decision theory should be taken more seriously in the specification and analysis of systems. We illustrate this by considering a simple problem involving reliable communication, showing how considerations of utility and probability can be used to decide when it is worth sending heartbeat messages and, if they are sent, how often they should be sent.
35307334
Performing Work Efficiently in the Presence of Faults
We consider a system of t synchronous processes that communicate only by sending messages to one another, and together the processes must perform n independent units of work. Processes may fail by crashing; we want to guarantee that in every execution of the protocol in which at least one process survives, all n units of work will be performed. We consider three parameters: the number of messages sent, the total number of units of work performed (including multiplicities), and time. We present three protocols for solving the problem. All three are work optimal, doing O(n+t) work. The first has moderate costs in the remaining two parameters, sends $O(t\sqrt{t})$ messages, and takes O(n+t) time. This protocol can be easily modified to run in any completely asynchronous system equipped with a failure detection mechanism. The second sends only O(t log t) messages, but its running time is large (O(t2(n+t) 2n+t)). The third is essentially time optimal in the (usual) case in which there are no failures, and its time complexity degrades gracefully as the number of failures increases.