The stabilizing algorithms considered in this chapter achieve fault-tolerant behavior in a manner radically different from that of the robust algorithms studied in the previous chapters. Robust algorithms follow a pessimistic approach, suspecting all information received, and precede all steps by sufficient checks to guarantee the validity of all steps of correct processes. Validity must be guaranteed in the presence of faulty processes, which necessitates restriction of the number of faults and of the fault model.

Stabilizing algorithms are optimistic, which may cause correct processes to behave inconsistently, but guarantee a return to correct behavior within finite time after all faulty behavior ceases. That is, stabilizing algorithms protect against transient failures; eventual repair is assumed, and this assumption allows us to abandon failure models and a bound on the number of failures. Rather than considering processes to be faulty, it is assumed that all processes operate correctly, but the configuration can be corrupted arbitrarily during a transient failure. Ignoring the history of the computation during the failure, the configuration at which we start the analysis of the algorithm, is considered the initial one of the (correctly operating) algorithm. An algorithm is therefore called stabilizing if it eventually starts to behave correctly (i.e., according to the specification of the algorithm), regardless of the initial configuration.

The concept of stabilization was proposed by Dijkstra [Dij74], but little work on it was done until the late nineteen-eighties; hence the subject can be considered relatively new.

In this chapter we investigate how the theory of distributed computing is affected by the assumption that there exists a global time, to which processes have access. A global time frame is part of the physical reality that surrounds us; this reality includes the processes of a distributed system and the design of distributed algorithms may profit from exploiting time. The results of this chapter show that time can be exploited to reduce the communication complexity of distributed algorithms if processing and communication times are bounded.

However, problems that are unsolvable without using time remain unsolvable after its introduction; thus, introducing synchrony improves the compexity but not the computability of distributed systems. This situation differs from the impact of synchronism in networks that are subject to failures; in Chapters 14 and 15 it will be shown that larger classes of failures can be handled deterministically if synchronism is exploited. Synchronism has already been used in Section 3.2 to overcome transmission failures.

In this chapter global time will mainly be studied in an idealized form, namely, where the entire network operates in discrete steps called pulses, as explained in Subsection 12.1.1. Each process performs local computations in each pulse, and it is ensured that a message that is sent in one pulse is received before the next pulse. This globally synchronized operation is also referred to as a lockstep operation. Lockstep operation is fairly easy to implement if clocks are available and an upper bound on transmission delay is assumed; see Subsection 12.1.3.

The previous chapter has studied the degree of fault tolerance achievable in completely asynchronous systems. Although a reasonable robustness is attainable, reliable systems in practice are always synchronous in the sense of relying on the use of timers and upper bounds on the message-delivery time. In these systems a higher degree of robustness is attainable, the algorithms are simpler, and the algorithms guarantee an upper bound on the response time in most of the cases.

The synchrony of the system makes it impossible for faulty processes to confuse correct processes by not sending information; indeed, if a process does not receive a message when expected, a default value is used instead, and the sender becomes suspected of being faulty. Thus, crashed processes are detected immediately and pose no difficult problems in synchronous systems; we concentrate on Byzantine failures in this chapter.

In Section 15.1 the problem of performing a broadcast in synchronous networks is studied; we present an upper bound (t < N/3) on the resilience, as well as two algorithms with optimal resilience. The algorithms are deterministic and achieve consensus; it is assumed that all processes know at what time the broadcast is initiated. Because consensus is not deterministically achievable in asynchronous systems (Theorem 14.8), it follows that in the presence of failures (even a single crash), synchronous systems exhibit a strictly stronger computational power than asynchronous ones.

The control structure of an interactive program can be quite complex when implemented in a sequential language. This problem arises because interactive programs must be able to deal with asynchronous external events responsively, while also executing the application code. The usual solution to this problem is to structure the program around a central event loop, which dispatches control to parts of the application in reaction to external events. Often, the event-loop is part of a library, and applications are programmed using the so-called “inverted program structure.” This is not too bad when the application is purely reactive, that is, it only does something as a reaction to user input, but many interactive applications do not fit this model. In such cases, the application must define special call-backs to perform computation when the system is otherwise idle. In order to guarantee responsiveness, these call-backs must execute quickly and then pass control back to the event loop. In effect, the use of an event-loop is a “poor man's concurrency.” This structure makes programming computationally significant algorithms difficult, and leads to a bias towards reactive, or input-driven, systems.

A more natural way to program these systems is as a set of communicating processes. Some window systems, such as the X Window System, provide concurrency between applications by using multiple system processes, but the individual applications are sequential and suffer from the problems mentioned above.

This book is about the union of two important paradigms in programming languages, namely, higher-order languages and concurrent languages. Higher-order programming languages, often referred to as “functional programming” languages, are languages that support functions as first-class values. The language used here is the popular higher-order language Standard ML (SML) [MTH90, MTHM97], which is the most prominent member of the ML family of languages. In particular, the bulk of this book focuses on concurrent programming using the language Concurrent ML (CML), which extends SML with independent processes and higher-order communication and synchronization primitives. The power of CML is that a wide range of communication and synchronization abstractions can be programmed using a small collection of primitives.

A concurrent program is composed from two or more sequential programs, called processes, that execute (at least conceptually) in parallel. The sequential part of the execution of these processes is independent, but they also must interact via shared resources in order to collaborate on achieving their common purpose. In this book, we are concerned with the situation in which the concurrency and process interaction are explicit. This is in contrast with implicitly parallel languages, such as parallel functional languages [Hud89, Nik91, PvE93] and concurrent logic programming languages [Sha89]. The choice of language mechanisms used for process interaction is the key issue in concurrent programming language design.

A natural application of concurrency is the management of multiple independent tasks. For example, building a large C program involves a number of individual compilations, each of which is run as a separate UNIX command. Since these compilations are independent, they may be run at the same time (possibly on different machines). In this chapter, we describe the implementation of a “parallel” build system using CML.

The problem

The basic problem is that we are given a set of objects, and a set of dependencies between the objects. Associated with some objects is an action that describes how to build the object; other objects (e.g., source files) do not have associated actions. Taken together, they form an acyclic dependency graph, whose topological order defines the order in which objects should be built. We use the term antecedents to denote the nodes that a node depends on, and successors to denote the nodes that depend on it. The nodes of the graph are classified into internal nodes (those that have non-zero in-degree), leaf nodes (those with no antecedents), and the root node (which has no successors). We restrict ourselves to graphs with exactly one root. For the graph to be well formed, any internal node should have an associated action. Leaf nodes may also have actions.

Also associated with each object is a timestamp that tells when the object was last built or modified.

The design of CML has been driven by practical experience. In particular, the mechanism of first-class synchronous operations is motivated by the fundamental conflict between selective communication and abstraction. This chapter explains the rationale for the design of CML, and especially for first-class synchronous operations. It is aimed at people interested in language design, and is not required to understand the remainder of the book. In this chapter, we focus on coreCML — synchronous message passing plus the event combinators — the other synchronization mechanisms found in CML, such as mailboxes, I-variables, and M-variables, can be viewed as derived forms. Some of the discussion here repeats earlier arguments, but is included for coherence.

Basic design choices

As surveyed in Chapter 2, there are many possible choices for the design of a concurrent language. CML chooses message passing over shared memory, synchronous communication over asynchronous, and simple rendezvous over extended rendezvous. This section argues in favor of these choices.

While SML is an imperative language, its design greatly encourages a mostly functional style of programming. Mutable values must be declared explicitly as such, and there is syntactic overhead on their use. For these reasons, extending SML with sharedmemory concurrency primitives is not true to the “spirit” of the language. Message passing, on the other hand, encourages a mostly functional programming style that fits well with ML. As we have seen, much of the state in typical CML programs is represented as immutable arguments to the tail-recursive functions that implement threads.

Concurrent programming is the task of writing programs consisting of multiple independent threads of control, called processes. Conceptually, we view these processes as executing in parallel, but in practice their execution may be interleaved on a single processor. For this reason, we distinguish between concurrency in a programming language, and parallelism in hardware. We say that operations in a program are concurrent if they can be executed in parallel, and we say that operations in hardware are parallel if they overlap in time.

Operating systems, where there is a need to allow useful computation to be done in parallel with relatively slow input/output (I/O) operations, provide one of the earliest examples of concurrency. For example, during its execution, a program P might write a line of text to a printer by calling the operating system. Since this operation takes a relatively long time, the operating system initiates it, suspends P, and starts running another program Q. Eventually, the output operation completes and an interrupt is received by the operating system, at which point it can resume executing P. In addition to introducing parallelism and hiding latency, as in the case of slow I/O devices, there are other important uses of concurrency in operating systems. Using interrupts from a hardware interval timer, the operating system can multiplex the processor among a collection of user programs, which is called time-sharing. Most time-sharing operating systems allow user programs to interact, which provides a form of user-level concurrency.