1 Introduction
What can be computed in a distributed system? This is a very broad question. There are many di erent models of distributed systems that reect di erent system architectures and di erent levels of fault-tolerance. Unlike the situation in sequential models of computation, small changes in the model of a distributed system can radically alter the class of problems that can be solved. Another important goal in the theory of distributed computing is to understand how eciently a distributed system can solve those problems that are solvable. There are a variety of resources to consider, including time, contention, and the number and sizes of messages and shared data structures.
This paper discusses unsolvability results, which show that problems are unsolvable in certain environments, and lower bound results, which show that problems cannot be solved when insucient resources are available. We refer to these two types of theorems collectively as impossibility results. A comprehensive survey of impossibility results in distributed computing would require an entire book; consequently, we have focused on the models and problems that we feel are most central to distributed computing. Our aim is to give you the avour of this research area and an outline of the most important techniques that have been used. There are, however, some important topics that we decided lie outside the scope of this survey, including self-stabilization [121], failure detectors [89], and uses of cryptography in distributed computing [150].
Why are impossibility results important for distributed computing? They help us understand the nature of distributed computing: what makes certain problems hard, what makes a model powerful, and how di erent models compare. They tell us when to stop looking for better solutions or, at least, which approaches will not work. If we have a problem that we need to solve, despite an impossibility result, the impossibility proof may indicate ways to adjust the problem speci cation or the modelling of the environment to allow reasonable solutions. Impossibility results have also inuenced real systems, for example, the design of network le systems [84], the architecture of fault tolerant systems for safety-critical applications [275], the design of programming languages [59], the speci cations of group membership services [97], and the de nition and study of failure detectors and systems based on them [88]. Finally, trying to prove impossibility results can suggest new and di erent algorithms, especially when attempts to prove impossibility fail. As John Cage wrote, \If someone says `can’t’, that shows you what to do” [82].
We begin in Sections 2 and 3 with brief descriptions of the models, terminology, and problems that are discussed throughout the paper. Section 4 discusses how to approach impossibility results and gives an overview of the major proof techniques for impossibility results in distributed computing. The rest of the paper presents a wide variety of results. Section 5 describes unsolvability results for the consensus problem and some similar process-coordination tasks. The use of impossibility results to study relationships between di erent models is addressed in Section 6. A systematic approach to studying computability for distributed systems is to characterize the models that can solve a particular problem. Alternatively, one can characterize the set of problems solvable in a given model. Results of both these types are described in Section 7. Further characterizations of problems solvable in speci c models appear in Section 8, which discusses applications of topology to proving impossibility results in distributed computing. Section 9 examines the question of whether weak shared object types can become more powerful when they are used in combination with other weak types. The next three sections consider complexity results. Each focuses on a di erent complexity measure: space, time, and the number of messages. Section 13 discusses impossibility results for randomized algorithms. An index of problems and proof techniques appears at the end of the paper.
This survey builds on Lynch’s excellent survey paper, \A Hundred Impossibility Proofs for Distributed Computing” [233], which covers results up to 1989. A shorter, preliminary version of our survey, emphasizing results from 1990 onwards, appeared in [137].
Complete text here.
