In the design of distributed algorithms for various applications several very general problems for process networks appear frequently as subtasks. These elementary tasks include the broadcasting of information (e.g., a start or terminate message), achieving a global synchronization between processes, triggering the execution of some event in each process, or computing a function of which each process holds part of the input. These tasks are always performed by passing messages according to some prescribed, topology-dependent scheme that ensures the participation of all processes. Indeed, as will become more evident to the reader in later chapters, these tasks are so fundamental that solutions to more complicated problems such as election (Chapter 7), termination detection (Chapter 8), or mutual exclusion can be given in which communication between processes occurs only via these message passing schemes.

The importance of message-passing schemes, called wave algorithms from now on, justifies a separate treatment of them in isolation from a particular application algorithm in which the schemes can be embedded. This chapter formally defines wave algorithms (Subsection 6.1.1) and proves some general results about them (Subsection 6.1.2). The observation that the same algorithms can be used for all of the fundamental tasks listed above, i.e., broadcasting, synchronization, and computing global functions, will be made rigorous (Subsections 6.1.3 through 6.1.5). Section 6.2 presents some widely used wave algorithms. Section 6.3 considers traversal algorithms, which are wave algorithms with the additional property that the events of a computation of the algorithm are totally ordered by causality.

Distributed systems and distributed information processing have received considerable attention in the past few years, and almost every university offers at least one course on the design of distributed algorithms. There exist a large number of books about principles of distributed systems; see for example Tanenbaum [Tan96] or Sloman and Kramer [SK87], but these concentrate on architectural aspects rather than on algorithms. Since the first edition of this book, other texts on distributed algorithms have been published by Barbosa [Bar96], Lynch [Lyn96], and Attiya and Welch [AW98].

It has been remarked that algorithms are the backbone of every computer application; therefore a text devoted solely to distributed algorithms seems to be justified. The aim of this book is to present a large body of theory about distributed algorithms, which has been developed over the past twenty years or so. This book can be used as a textbook for a one- or two-semester course on distributed algorithms; the teacher of a one-semester course may select topics to his own liking.

The book will also provide useful background and reference information for professional engineers and researchers working with distributed systems.

Exercises. Each chapter (with the exception of Chapters 1 and 13) ends with a list of exercises and small projects. The projects usually require the reader to develop a small but non-trivial extension or application of the material treated in the chapter, and in most cases I do not have a “solution”.

In earlier chapters the assumption was usually made that unique identities are available to distinguish the processes of a distributed system. This assumption is valid in most of the existing distributed systems; the identity of a process is often taken as the address used to send messages to the process. For the latter purpose, however, it is also possible for processes to be identified via indirect addressing (Subsection 2.4.4), where each process distinguishes between its neighbors by locally known channel names.

A different use of identities was made in Chapter 7, where the identities of processes were employed to break the symmetry between processes. A typical example of this phenomenon is already found in a simple algorithm like that of Chang and Roberts (Algorithm 7.3), when it is initiated by two processes, p and q. In this computation, p receives q's token and q receives p's token; the situation would be completely symmetric if no ordering on process identities were available. The symmetry is broken by this ordering; the smaller of the two processes survives, the larger becomes defeated. More complicated examples of symmetry breaking by means of identity comparisons are found in other algorithms in Chapter 7.

Globally unique identities have also been used to detect termination, e.g., in Finn's algorithm (Algorithm 6.9). A process detects that it has indirectly received information about all processes if two collections of names coincide, where collection Inc includes the names of all neighbors of processes in NInc (for details, see Subsection 6.2.6).

The earlier parts of this book studied the coordinated behavior that can be achieved in distributed systems where processes are reliable. For several reasons it is attractive to study what coordinated behavior of processes is possible under the assumption that processes may fail; this study is the subject of the last part of the book. Many solutions for fault tolerance are ad hoc and, also, in the large collection of impossibility proofs structure and underlying theory are sometimes hard to find. On the other hand, some problems have elegant and well-established theory and simple solutions whose presentation fits well in this introductory textbook.

This chapter serves as a general introduction to the later chapters. We illustrate the reasons for using fault-tolerant algorithms (Section 13.1), and subsequently introduce two main types of fault-tolerant algorithms, namely robust algorithms (Section 13.2) and stabilizing algorithms (Section 13.3).

Reasons for Using Fault-tolerant Algorithms

Increasing the number of components in a distributed system means increasing the probability that some of these components will be subject to failure during the execution of a distributed algorithm. Computers in a network may fail, processes in a system can be erroneously killed by switching off a workstation, or a machine may produce an incorrect result due to, e.g., memory malfunctioning. Modern computers are becoming more and more reliable, thereby decreasing the chance of the occurrence of such failures in any individual Computer.

A process (a node in a computer network) is in general not connected directly to every other process by a channel. A node can send packets of information directly only to a subset of the nodes called the neighbors of the node. Routing is the term used to describe the decision procedure by which a node selects one (or, sometimes, more) of its neighbors to forward a packet on its way to an ultimate destination. The objective in designing a routing algorithm is to generate (for each node) a decision-making procedure to perform this function and guarantee delivery of each packet.

It will be clear that some information about the topology of the network must be stored in each node as a working basis for the (local) decision procedure; we shall refer to this information as the routing tables. With the introduction of these tables the routing problem can be algorithmically divided into two parts; the definition of the table structure is of course related to the algorithmical design.

1. Table computation. The routing tables must be computed when the network is initialized and must be brought up to date if the topology of the network changes.

2. Packet forwarding. When a packet is to be sent through the network it must be forwarded using the routing tables.

Criteria for “good” routing methods include the following.

1. Correctness. The algorithm must deliver every packet offered to the network to its ultimate destination.

Rather than presenting the algorithms in this book as programs written in an existing programming language, a pseudocode is used for the formal description of algorithms. Pseudocode is concise and “user-friendly”, where a real program is often obscured by details concerning a rigid syntax.

Pascal-like pseudocode. The pseudocode used in this book very much resembles the language Pascal. An algorithm is usually given as the local algorithm of a process of the system, whose name is used as a subscript to the variables of the program. Process names can be used as array indices, and set variables are used. The variable Neighp is the set of processes to which p is connected (the neighbors of p).

Assignment (“a := expression”), conditional statement (“if conditionthenstatement”, with an optional “elsestatement” part), and loop (“whileconditiondostatement”) are used with the same meaning as in Pascal. The forall statement has the form “forallx ∈ Xdostatement”, where x is a formal parameter and X a set, and means that statement will be executed for each element x of X in turn. The order in which the elements get their turn is not specified, but the s atement is only used where the order does not matter.

In this chapter the problem of election, also called leader finding, will be discussed. The election problem was first posed by LeLann [LeL77], who also proposed the first solution; see Subsection 7.2.1. The problem is to start from a configuration where all processes are in the same state, and arrive at a configuration where exactly one process is in state leader and all other processes are in the state lost.

An election under the processes must be held if a centralized algorithm is to be executed and there is no a priori candidate to serve as the initiator of this algorithm. For example, this could be the case for an initialization procedure that must be executed initially or after a crash of the system. Because the set of active processes may not be known in advance it is not possible to assign one process once and for all to the role of leader.

A large number of results about the election problem (algorithms as well as more general theorems) exist. The results in this chapter were selected for inclusion with the following criteria in mind.

1. Synchronous systems, anonymous processes, and fault tolerant algorithms are discussed in other chapters. In this chapter it is always assumed that processes and channels are reliable, the system is fully asynchronous, and the processes are distinguished by unique identities.

2. The election problem has taken the role of a “benchmarking problem” to compare the efficiency of different computation models.

The impossibility of solving consensus in asynchronous systems (Section 14.1) has led to weaker problem formulations and stronger models. Examples of the former include weaker coordinations and randomization, and examples of the latter include introducing synchrony. Failure detectors are now widely recognized as an alternative way to strengthen the computation model.

Studying synchronous models is practically motivated because most distributed programming environments do provide clocks and timers in some way. Theoretical studies reveal for what tasks the use of these primitives is necessary and to what degree they must be used. With failure detectors, the situation is similar: quite often the run-time support system will return error messages upon an attempt to communicate with a crashed process. However, these error messages are not always absolutely reliable. It is therefore useful to study how reliable they must be to allow a solution for the consensus problem (or other problems).

In contrast to synchrony (implemented using physical clocks), failure detectors have no straightforward intuitive implementation. This implies that non-trivial solutions must be found in order to implement them in the runtime system or as a module in the application. The implementations more often than not rely on the use of timers (see Section 16.4) and this has led to some serious critiques of the failure detector approach. It was argued that “failure detectors” as such do not solve any problems, because their implementation requires the same resources (time) that can be used to solve consensus directly.

Several different models of distributed information processing are used frequently in the study of distributed algorithms. The choice of a particular model usually depends on what problem from the area of distributed computing is studied and what type of algorithm or impossibility proof is presented. In this book, although it covers a wide range of distributed algorithms and theory about them, an attempt is made to work in a single, general model, described in this chapter, as much as possible.

In order to admit impossibility results (the proof of the non-existence of an algorithm for some task) the model must be very precise. An impossibility result is a statement about all possible algorithms allowed in a system, hence the model must be precise enough to describe the relevant properties of all admitted algorithms. Yet a computational model is more than the detailed description of a particular computer system or programming language. There are many different computing systems, and we desire that the model is applicable to a class of related systems sharing the essential properties that make them “distributed”. Finally, the model must be reasonably compact, because one may expect that all aspects of a model must be considered in proofs. Summarizing, the model must describe precisely and concisely the relevant aspects of a class of computing systems.

A distributed computation is usually considered as a collection of discrete events, each event being an atomic change in the configuration (the state of the entire system).

This chapter studies the solvability of decision problems in asynchronous distributed systems. The results are arranged around a fundamental result by Fischer, Lynch, and Paterson [FLP85], presented in Section 14.1. Formulated as an impossibility proof for a class of decision algorithms, the result can also be read as a list of assumptions that together exclude solutions for decision problems. Relaxing the assumptions makes it possible to obtain practical solutions for various problems, as is shown in the subsequent sections. See also Subsection 14.1.3 for a further discussion.

Impossibility of Consensus

In this section the fundamental theorem of Fischer, Lynch, and Paterson [FLP85], stating that there are no asynchronous, deterministic 1-crash robust consensus protocols, is proved. The result is shown by reasoning involving fair execution sequences of the algorithms. We first introduce some notation (in addition to that introduced in Section 2.1) and give elementary results that are useful also in later sections.

Notation, Definitions, Elementary Results

The sequence σ = (e1, …, ek) of events is applicable in configuration γ if e1 is applicable in γ, e2 in e1(γ), and so on. If the resulting configuration is δ, we write γ ⇝σ δ or σ(γ) = δ, to make the events leading from γ to δ explicit. If S ⊆ ℙ and σ contains only events in processes of S we also write γ ⇝ s δ.

A computation of a distributed algorithm terminates when the algorithm has reached a terminal configuration; that is, a configuration in which no further steps of the algorithm are applicable. It is not always the case that in a terminal configuration each process is in a terminal state; that is, a process state in which there is no event of the process applicable. Consider a configuration where each process is in a state that allows the receipt of messages, and all channels are empty. Such a configuration is terminal, but the processes' states could also occur as intermediate states in the computation. In this case, the processes are not aware that the computation has terminated; and the termination of the computation is said to be implicit. Termination is said to be explicit in a process if the state of that process in the terminal configuration is a terminal state of the process. Implicit termination of the computation is also called message termination because no more messages are exchanged when a terminal configuration has been reached. Explicit termination is also called process termination because the processes have terminated if an algorithm explicitly terminates.

It is usually easier to design an algorithm that terminates implicitly than one that terminates explicitly. Indeed, during the design of an algorithm all aspects regarding the proper termination of processes can be ignored; the design concentrates on bounding the overall number of events that can take place.

This chapter gives reasons for the study of distributed algorithms by briefly introducing the types of hardware and software systems for which distributed algorithms have been developed. By a distributed system we mean all computer applications where several computers or processors cooperate in some way. This definition includes wide-area computer communication networks, but also local-area networks, multiprocessor computers in which each processor has its own control unit, and systems of cooperating processes.

The different types of distributed system and the reasons why distributed systems are used are discussed in Section 1.1. Some examples of existing systems will be given. The main topic of this book, however, is not what these systems look like, or how they are used, but how they can be made to work. And even that topic will be further specialized towards the treatment of the algorithms used in the systems.

Of course, the entire structure and operation of a distributed system is not fully understood by a study of its algorithms alone. To understand such a system fully one must also study the complete architecture of its hardware and software, that is, the partition of the entire functionality into modules. Also, there are many important questions related to properties of the programming languages used to build the software of distributed systems. These subjects will be discussed in Section 1.2.

It is the case, however, that there are already in existence excellent books about distributed systems, which concentrate on the architectural and language aspects; see, e.g., Tanenbaum [Tan96], Sloman and Kramer [SK87], Bal [Bal90], Coulouris and Dollimore [CD88] or Goscinski [Gos91].