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 …
7572747
Set-theoretic completeness for epistemic and conditional logic
The standard approach to logic in the literature in philosophy and mathematics, which has also been adopted in computer science, is to define a language (the syntax), an appropriate class of models together with an interpretation of formulas in the language (the semantics), a collection of axioms and rules of inference characterizing reasoning (the proof theory), and then relate the proof theory to the semantics via soundness and completeness results. Here we consider an approach that is more common in the economics literature, which works purely at the semantic, set-theoretic level. We provide set-theoretic completeness results for a number of epistemic and conditional logics, and contrast the expressive power of the syntactic and set-theoretic approaches.
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.
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.
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.
61049720
Knowledge-Based Synthesis of Distributed Systems Using Event Structures
To produce a program guaranteed to satisfy a given specification one can synthesize it from a formal constructive proof that a computation satisfying that specification exists. This process is particularly effective if the specifications are written in a high-level language that makes it easy for designers to specify their goals. We consider a high-level specification language that results from adding knowledge to a fragment of Nuprl specifically tailored for specifying distributed protocols, called event theory. We then show how high-level knowledge-based programs can be synthesized from the knowledge-based specifications using a proof development system such as Nuprl. Methods of Halpern and Zuck [15] then apply to convert these knowledge-based protocols to ordinary protocols. These methods can be expressed as heuristic transformation tactics in Nuprl.
45012843
Reasoning about common knowledge with infinitely many agents
Complete axiomatizations and exponential-time decision procedures are provided for reasoning about knowledge and common knowledge when there are infinitely many agents. The results show that reasoning about knowledge and common knowledge with infinitely many agents is no harder than when there are finitely many agents, provided that we can check the cardinality of certain set differences G G' where G and G' are sets of agents. Since our complexity results are independent of the cardinality of the sets G involved, they represent improvements over the previous results even with the sets of agents involved are finite. Moreover, our results make clear the extent to which issues of complexity and completeness depend on how the sets of agents involved are represented.
1183840
Evidence with uncertain likelihoods
An agent often has a number of hypotheses, and must choose among them based on observations, or outcomes of experiments. Each of these observations can be viewed as providing evidence for or against various hypotheses. All the attempts to formalize this intuition up to now have assumed that associated with each hypothesis h there is a likelihood function μh, which is a probability measure that intuitively describes how likely each observation is, conditional on h being the correct hypothesis. We consider an extension of this framework where there is uncertainty as to which of a number of likelihood functions is appropriate, and discuss how one formal approach to defining evidence, which views evidence as a function from priors to posteriors, can be generalized to accommodate this uncertainty.
205008749
The Complexity of Reasoning about Knowledge and Time. I. Lower Bounds
Abstract We study the propositional model logic of knowledge and time for distributed systems. We consider a number of logics (ninety-six in all!), which vary according to the choice of language and the assumptions made on the underlying system. The major parameters in the language are whether there is a common knowledge operator, whether we reason about the knowledge of one or more than one processor, and whether our temporal operators are branching or linear. The assumptions on distributed systems that we consider are: whether or not processors forget, whether or not processors learn, whether or not time is synchronous, and whether or not there is a unique initial state in the system. We completely characterize the complexity of the validity problem for all the logics we consider. This paper focuses on lower bounds; a sequel will deal with the corresponding upper bounds. Typical results include a ∏-completeness result for the language with common knowledge with respect to systems where processors do not forget, and a corresponding non-elementary-time result for the language without common knowledge. It is shown that, in general, the assumption that processors do not forget or do not learn greatly increases the complexity of reasoning about knowledge and time.
806901
Forming Beliefs about a Changing World
The situation calculus is a popular technique for reasoning about action and change. However, its restriction to a first-order syntax and pure deductive reasoning makes it unsuitable in many contexts. In particular, we often face uncertainty, due either to lack of knowledge or to some probabilistic aspects of the world. While attempts have been made to address aspects of this problem, most notably using nonmonotonic reasoning formalisms, the general problem of uncertainty in reasoning about action has not been fully dealt with in a logical framework. In this paper we present a theory of action that extends the situation calculus to deal with uncertainty. Our framework is based on applying the random-worlds approach of [BGHK94] to a situation calculus ontology, enriched to allow the expression of probabilistic action effects. Our approach is able to solve many of the problems imposed by incomplete and probabilistic knowledge within a unified framework. In particular, we obtain a default Markov property for chains of actions, a derivation of conditional independence from irrelevance, and a simple solution to the frame problem.