3055934
A knowledge-theoretic analysis of uniform distributed coordination and failure detectors
Abstract.It is shown that, in a precise sense, if there is no bound on the number of faulty processes in a system with unreliable but fair communication, Uniform Distributed Coordination (UDC) can be attained if and only if a system has perfect failure detectors. This result is generalized to the case where there is a bound t on the number of faulty processes. It is shown that a certain type of generalized failure detector is necessary and sufficient for achieving UDC in a context with at most t faulty processes. Reasoning about processes’ knowledge as to which other processes are faulty plays a key role in the analysis.
10886930
Belief Revision with Unreliable Observations
Research in belief revision has been dominated by work that lies firmly within the classic AGM paradigm, characterized by a well-known set of postulates governing the behavior of "rational" revision functions. A postulate that is rarely criticized is the success postulate: the result of revising by an observed proposition ? results in belief in ?. This postulate, however, is often undesirable in settings where an agent's observations may be imprecise or noisy. We propose a semantics that captures a new ontology for studying revision functions, which can handle noisy observations in a natural way while retaining the classical AGM model as a special case. We present a characterization theorem for our semantics, and describe a number of natural special cases that allow ease of specification and reasoning with revision functions. In particular, by making the Markov assumption, we can easily specify and reason about revision.
23622807
Time to publication: a progress report
The process of submitting a paper to a journal can be incredibly frustrating for authors. Practically everyone who has been active in research for more than a few years has either first-or secondhand experience with some real horror stories. One of my goals when I took over JACM was to ease some of these frustrations, by speeding up the time to publication. I'd like to give you a sense of our progress in reaching that goal. Traditionally, a paper submitted to JACM went through many steps: the paper was submitted to the editor-in-chief; the editor-in-chief sent it to an editor; the editor sent it to referees; the paper went through one or more iterations between the referees, editor, editor-in-chief, and author(s); if the paper was accepted, it went on to the publication queue; authors received galleys and corrected them; and the paper finally appeared. As a result, the median time from submission to final acceptance for papers published in 1997 was 20 months. I would like to cut this down to 12 months. Often the most frustrating experience for authors is to submit a paper and then, after more than a year of waiting, to discover that it has been rejected. I don't have reliable statistics yet for how long such papers were in the system, but I would like to see significant progress here too. I would expect that the median time in the system for papers that are ultimately rejected will be 4 months. My predecessor, Tom Leighton, focused on what was the major cause of delay—the amount of time an accepted paper waited in the publication queue before it appeared. This wait used to be measured in years. The fact that the mean time to publication for 1997 was 20 months already shows how significant the improvement has been here. Currently (April 1998) the JACM web site shows that there are 19 papers in the queue, which means that the wait is approximately 3 issues, or 6 months. Since it is considered dangerous for an editor-in-chief to have too small a backlog, this is about the best that can be expected as far as the publication queue, at least until JACM goes completely electronic. Note, however, that final papers submitted in postscript are posted on the web site within a few days of submission; the papers on the queue are available to the world almost immediately. What …
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.
8145017
Characterizing the Common Prior Assumption
Abstract Logical characterizations of the common prior assumption (CPA) are investigated. Two approaches are considered. The first is called frame distinguishability , and is similar in spirit to the approaches considered in the economics literature. Results similar to those obtained in the economics literature are proved here as well, namely, that we can distinguish finite spaces that satisfy the CPA from those that do not in terms of disagreements in expectation. However, it is shown that, for the language used here, no formulas can distinguish infinite spaces satisfying the CPA from those that do not. The second approach considered is that of finding a sound and complete axiomatization. Such an axiomatization is provided; again, the key axiom involves disagreements in expectation. The same axiom system is shown to be sound and complete both in the finite and the infinite case. Thus, the two approaches to characterizing the CPA behave quite differently in the case of infinite spaces. Journal of Economic Literature Classification Numbers: C70, D80.
1225089
Defining Explanation in Probabilistic Systems
As probabilistic systems gain popularity and are coming into wider use, the need for a mechanism that explains the system's findings and recommendations becomes more critical. The system will also need a mechanism for ordering competing explanations. We examine two representative approaches to explanation in the literature-- one due to Gardenfors and one due to Pearl--and show that both suffer from significant problems. We propose an approach to defining a notion of "better explanation" that combines some of the features of both together with more recent work by Pearl and others on causality.
29074646
A New Look at Fault-Tolerant Network Routing
Abstract We model a communication network as a graph in which a processor is a node and a communication link is an edge. A routing for such a network is a fixed path, or route, between each pair of nodes. Given a network with a predefined routing, we study the effects of faulty components on the routing. Of particular interest is the number of routes along which a message must travel between any two non-faulty nodes. This problem is analyzed for specific families of graphs and for classes of routings. We also give some bounds for general versions of the problem. Finally, we conclude with one of the most important contributions of this paper, a list of interesting and apparently difficult open problems.
5106791
A Knowledge-Based Analysis of Global Function Computation
Consider a distributed system N in which each agent has an input value and each communication link has a weight. Given a global function, that is, a function f whose value depends on the whole network, the goal is for every agent to eventually compute the value f(N). We call this problem global function computation. Various solutions for instances of this problem, such as Boolean function computation, leader election, (minimum) spanning tree construction, and network determination, have been proposed, each under particular assumptions about what processors know about the system and how this knowledge can be acquired. We give a necessary and sufficient condition for the problem to be solvable that generalizes a number of well-known results [3, 28, 29]. We then provide a knowledge-based (kb) program (like those of Fagin, Halpern, Moses, and Vardi [8,9]) that solves global function computation whenever possible. Finally, we improve the message overhead inherent in our initial kb program by giving a counterfactual belief-based program [15] that also solves the global function computation whenever possible, but where agents send messages only when they believe it is necessary to do so. The latter program is shown to be implemented by a number of well-known algorithms for solving leader election.
14477826
Reasoning about knowledge and time in asynchronous systems
We investigate the complexity of reasoning about knowledge and time, with emphasis on the case of asynchronous time. We show that in the case of no forgetting (Ladner and Reif's Tree Logic of Protocols, TLP) the validity problem is complete for nonelementary time. This settles the open problem of [HV86, LR86]. This result is somewhat surprising in light of Ladner and Reif's undecidability result for a similar logic, LLP. We show that the undecidability result for LLP is caused by two quite natural properties of models in that logic, which we call no learning and unique initial state. Both of these properties are necessary for the undecidability result in [LR86]. We completely characterize the complexity of all ninety-six logics that result by varying the relevant parameters. Many of the results are quite delicate, and require substantially new techniques.
52151232
Knowledge and common knowledge in a distributed environment
Reasoning about knowledge seems to play a fundamental role in distributed systems. Indeed, such reasoning is a central part of the informal intuitive arguments used in the design of distributed protocols. Communication in a distributed system can be viewed as the act of transforming the system's state of knowledge. This paper presents a general framework for formalizing and reasoning about knowledge in distributed systems. It is shown that states of knowledge of groups of processors are useful concepts for the design and analysis of distributed protocols. In particular, distributed knowledge corresponds to knowledge that is “distributed” among the members of the group, while common knowledge corresponds to a fact being “publicly known.” The relationship between common knowledge and a variety of desirable actions in a distributed system is illustrated. Furthermore, it is shown that, formally speaking, in practical systems common knowledge cannot be attained. A number of weaker variants of common knowledge that are attainable in many cases of interest are introduced and investigated.
10307056
Intransitivity and Vagueness
There are many examples in the literature that suggest that indistinguishability is intransitive, despite the fact that the indistinguishability relation is typically taken to be an equivalence relation (and thus transitive). It is shown that if the uncertainty perception and the question of when an agent reports that two things are indistinguishable are both carefully modeled, the problems disappear, and indistinguishability can indeed be taken to be an equivalence relation. Moreover, this model also suggests a logic of vagueness that seems to solve many of the problems related to vagueness discussed in the philosophical literature. In particular, it is shown here how the logic can handle the Sorites Paradox.