INTRODUCTION

In Chapter 5, we saw why and how to build generic user interfaces. The two types of interfaces that dominate computing today are Graphical User Interfaces (GUIs) and Voice User Interfaces (VUIs). So, when we specialize a generic user interface, we are typically specializing it to either a GUI (of which we will consider text-only user interfaces to be a subset) or a VUI. In this chapter, we will look at GUIs, in Chapter 7 we will look at VUIs, and in Chapter 8 we will see how to build multimodal user interfaces that use multiple channels to reach the user.

Let us remember our final goal: building mobile user interfaces. Mobile user interfaces inherently have different requirements than their stationary counterparts because of the dimensions of mobility and the mobile condition of the user. The dimensions of mobility affect design and implementation of user interfaces in two fundamental ways. The first is that the user interface has to accommodate functionality that relates to the dimensions of mobility. For example, user interfaces must be available on all of those devices through which the user of an application may access a system. Second, the dimensions of mobility create various concerns that require further separation of concerns when building user interfaces.

Networks of regular structure, such as the torus or the hypercube, usually have the links labeled with their direction. We now discuss some recent research evaluating the benefits of such a labeling, called Sense of Direction or SoD. The availability of sense of direction strengthens the model and allows processors to communicate more efficiently with each other, and to exploit topological properties of the network algorithmically.

Sense of direction has been shown to reduce the complexity of some problems, but the number of problems for which this applies is surprisingly small. Indeed, for many problems, more efficient or easier algorithms are known if the edge labeling can be exploited. However, in many non-trivial cases good lower bounds for the unlabeled case are not available, and moreover some surprisingly efficient algorithms exist in unlabeled graphs.

The chapter attempts to follow the scientific struggle, started by Santoro [San84], to establish cases in favor of sense of direction in two areas: broadcasting and election.

We shall define sense of direction for several specific classes of network, and show how the election problem on rings can be solved more efficiently if chords and a sense of direction are available. We shall show that elections can be performed with linear complexity in hypercubes and cliques if SoD is available, but also that a randomized algorithm can achieve the same complexity without using SoD. Algorithms to compute an SoD in networks where none is given will also be discussed.

This chapter discusses two protocols that are used for the reliable exchange of data between two computing stations. In the ideal case, data would simply be exchanged by sending and receiving messages. Unfortunately, the possibility of communication errors cannot always be ignored; the messages must be transported via a physical medium, which may lose, duplicate, reorder, or garble messages transmitted through it. These errors must be detected and corrected by supplementary mechanisms, traditionally referred to as protocols, implemented in the computing stations.

The main function of these protocols is data transmission, i.e., the accepting of the information at one station and its delivery at the other station. Reliable data transmission includes the repeated sending of messages that are lost, rejecting or correcting messages that are garbled, and discarding duplicates of messages. To do so the protocol maintains state information, recording which data has already been sent, which data has been certified to be received, and so on. The necessity of using state information raises the issue of connection management, i.e., the initialization and discarding of state information. The initialization is called opening the connection and its discarding is called closing the connection. The difficulty of connection management is due to the possibility that a message remains in the communication channels when the connection is closed. Such a message could be received when no connection exists or during a later connection, and its receipt must not disturb the correct operation of the current connection.

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).