Keywords

BG simulation; Reduction; Simulation

7.1 Motivation

Modern distributed systems are highly complex yet reliable and efficient, thanks to heavy use of abstraction layers in their construction. At the hardware level processes may communicate through low-level shared-register operations, but a programmer uses complex shared objects to manage concurrent threads. Also from the theoretical perspective, researchers have devised algorithms to implement higher-level-of-abstraction shared objects from lower-level-of-abstraction objects. We have already encountered this technique to build larger set agreement boxes from smaller ones (Exercise 5.6) or to implement snapshots from single-writer/multireader registers (Exercise 4.12). We say snapshots can be simulated in a wait-free system where processes communicate using single-writer/single-reader registers. Simulations are useful also to deduce the relative power of abstractions; in this case, snapshots are as powerful as single-writer/single-reader registers, but not more powerful. In contrast, a consensus shared black box cannot be simulated in a wait-free system where processes communicate using only read-write registers, as we have already seen.

Software systems are built in a modular fashion using this simulation technique, assuming a black box for a problem has been constructed and using it to further extend the system. However, this technique is also useful to prove impossibility results. In complexity theory, it is common to prove results by reduction from one problem to another. For example, to prove that there is not likely to exist a polynomial algorithm for a problem, one may try to show that the problem is NP-complete. Textbooks typically prove from first principles that satisfiability (SAT) is NP-complete. To show that another problem is also NP-complete, it is enough to show that SAT (or some other problem known to be NP-complete) reduces to the problem in question. Reductions are appealing because they are often technically simpler than proving NP completeness directly.

Reductions can also be applied in distributed computing for impossibility results. For example, suppose we know that a colorless task has no wait-free layered immediate snapshot protocol, and we want to know whether it has a -resilient protocol for some . One way to answer this question is to assume that an -process, -resilient protocol exists and devise a wait-free protocol where processes “simulate” the -resilient -process protocol execution in the following sense: The -processes use the code for the protocol to simulate an execution of the -processes. They assemble mutually consistent final views of an -process protocol execution during which at most processes may fail. Each process halts after choosing the output value that would have been chosen by one of the simulated processes. Because the task is colorless, any process can choose any simulated process’s output, so this simulation yields a wait-free -process layered protocol, contradicting the hypothesis that no such protocol exists. Instead of proving directly that no -resilient protocol exists, we reduce the -resilient problem to the previously solved wait-free problem.

In general, we can use simulations and reductions to translate impossibility results from one model of computation to another. As in complexity theory, once one has proved an impossibility result in one model, one can avoid reproving that result in related models by relying on reductions. One possible problem with this approach is that known simulation techniques, such as the BG-simulation protocol presented in Section 7.4, are model-specific, and a new, specialized simulation protocol must be crafted for each pair of models. Moreover, given two models, how do we know if there is a simulation before we start to try to design one?

The key insight behind this chapter is that there is often no need to construct explicit simulations. Instead, we can treat simulation as a task like any other and apply the computability conditions of Chapter 5 to show when a simulation protocol exists. These existence conditions are given in terms of the topological properties of the models’ protocol complexes and are likely to be easier to determine in general than devising pair-wise simulations. Once it is known that a simulation exists, one may then concentrate on finding an efficient one that might be of practical interest.

7.2 Combinatorial setting

So far we have considered several models of computation. Each one is given by a set of process names, ; a communication medium, such as shared memory or message-passing; a timing model, such as synchronous or asynchronous; and a failure model, given by an adversary, . For each model of computation, once we fix a colorless input complex , we may consider the set of final views of a protocol. We have the combinatorial definition of a protocol (Definition 4.2.2), as a triple where is an input complex, is a protocol complex (of final views), and is an execution map. For each , a model of computation may be represented by all the protocols on .

Consider for instance the -process, colorless layered immediate snapshot protocol of Chapter 4. If we take the wait-free adversary and any input complex , the model obtained consists of all protocols , corresponding to having the layered immediate snapshot protocol execute layers, where is the complex of final configurations and the corresponding carrier map. Similarly, taking the -resilient layered immediate snapshot protocol of Figure 5.1 for processes and input complex consists of all protocols , corresponding to executing the protocol for layers.

Recall that a protocol solves a colorless task if there is a simplicial map carried by . Operationally, in each execution, processes end up with final views that are vertices of the same simplex of . Moreover, if the input simplex of the execution is , then . Each process finishes the protocol in a local state that is a vertex of and then applies to choose an output value. These output values form a simplex in .

For example, the model solves the iterated barycentric agreement task for any . To see this, we must verify that there is some such that the protocol solves .

A reduction is defined in terms of two models of computation: a model (called the real model) and a model (called the virtual model). They have the same input complex , but their process names, protocol complexes, and adversaries may differ. The real model reduces to the virtual model if the existence of a protocol in the virtual model implies the existence of a protocol in the real model.

For example, the -resilient layered immediate snapshot model for processes trivially reduces to the wait-free model . Operationally it is clear why. If a wait-free -process protocol solves a task it tolerates failures by processes. The same protocol solves the task if only out of the may crash. Combinatorially, the definition of reduction is as follows.

We typically demonstrate reduction using simulation.

The operational intuition is that each process executing the real protocol chooses a simulated execution in the virtual protocol, where each virtual process has the same input as some real process. However, from a combinatorial perspective, it is sufficient to show that there exists a simplicial map as above. Note that may be collapsing: Real processes with distinct views may choose the same view of the simulated execution.

The left-hand diagram of Figure 7.1 illustrates how a protocol solves a task. Along the horizontal arrow, carries each input simplex of to a subcomplex of . Along the diagonal arrow, a protocol execution, here denoted , carries each to a subcomplex of its protocol complex, denoted by , which is mapped to a subcomplex of along the vertical arrow by the simplicial map . The diagram semi-commutes: The subcomplex of reached through the diagonal and vertical arrows is contained in the subcomplex reached through the horizontal arrow.

Simulation is illustrated in the middle diagram of Figure 7.1. Along the diagonal arrow, carries each input simplex of to a subcomplex of its protocol complex . Along the vertical arrow, carries each input simplex of to a subcomplex of its own protocol complex , which is carried to a subcomplex of by the simplicial map . The diagram semi-commutes: The subcomplex of reached through the vertical and horizontal arrows is contained in the subcomplex reached through the diagonal arrow. Thus, we may view simulation as solving a task. If we consider as a task, where is input complex and is output complex, then solves this task with decision map carried by .

Theorem 7.2.5 depends only on the existence of a simplicial map. Our focus in the first part of this chapter is to establish conditions under which such maps exist. In the second part, we will construct one operationally.

7.3 Applications

In Chapters 5 and 6, we gave necessary and sufficient conditions for solving colorless tasks in a variety of computational models. Table 7.1 lists these models, parameterized by an integer . We proved that the colorless tasks that can be solved by these models are the same and those colorless tasks for which there is a continuous map

carried by . Another way of proving this result is showing that these protocols are equivalent in the simulation sense of Definition 7.2.4.

Here are some of the implications of this lemma, together with Theorem 7.2.5:

7.4 BG simulation

In this section, we construct an explicit shared-memory protocol by which processes running against adversary can simulate processes running against adversary , where and have the same minimum core size. We call this protocol BG simulation after its inventors, Elizabeth Borowsky and Eli Gafni. As noted, the results of the previous section imply that this simulation exists, but the simulation itself is an interesting example of a concurrent protocol.

7.5 Conclusions

In this chapter we have once more seen the two faces of distributed computing: algorithmic and combinatorial. If we know a task is unsolvable in a certain model and we want to show it is unsolvable in another model , then it is natural to try to reduce model to model instead of proving the impossibility result from scratch in , especially if model seems more difficult to analyze than model . The end result of a reduction is a simplicial map from protocols in to protocols in . We can produce such a simplicial map operationally using a protocol in , or we can show it exists, reasoning about the topological properties of the two models.

The first reduction studied was for -set agreement. It was known that it is unsolvable in a (real) wait-free model even when for processes. Proving directly that -set agreement is unsolvable in a (virtual) -resilient model, , when seemed more complicated. Operationally, one assumes (for contradiction) that there is a -set agreement protocol in . Then a generic protocol in is used to simulate one by one the instructions of the protocol to obtain a solution for -set agreement in .

This operational approach has several benefits, including the algorithmic insights discovered while designing a simulation protocol, and its potential applicability for transforming solutions from one model of computation to another. However, to understand the possible reductions among a set of models of computation, we would have to devise explicit pair-wise simulations, each simulation intimately connected with the detailed structure of two models. Each simulation is likely to be a protocol of nontrivial complexity requiring a nontrivial operational proof.

By contrast, the combinatorial approach described in this chapter requires analyzing the topological properties of the protocol complexes for each of the models. Each such computation is a combinatorial exercise of the kind that has already been undertaken for many different models of computation. This approach is more systematic and, arguably, reveals more about the underlying structure of the models than explicit simulation algorithms. Indeed, in the operational approach, once a simulation is found, we also learn why it existed, but this new knowledge is not easy to formalize; it is hidden inside the correctness proof of the simulation protocol.

We note that the definitions and constructions of this chapter, both the combinatorial and the operational, work only for colorless tasks. For arbitrary tasks, we can also define simulation in terms of maps between protocol complexes, but these maps require additional structure (they must be color-preserving, mapping real to virtual processes in a one-to-one way). See Chapter 14.

7.6 Chapter notes

Borowsky and Gafni [23] introduced the BG simulation to extend the wait-free set agreement impossibility result to the -resilient case. Later, Borowsky, Gafni, Lynch, and Rajsbaum [27] formalized and studied the simulation in more detail.

Borowsky, Gafni, Lynch, and Rajsbaum [27] identified the tasks for which the BG simulation can be used as the colorless tasks. This class of tasks was introduced in Herlihy and Rajsbaum [80,81], under the name convergence tasks, to study questions of decidability.

Borowsky and Gafni [25] and later Chaudhuri and Reiners [41] used the BG simulation to define and study the set agreement partial order [79]. Gafni and Kuznetsov [65] used the simulation to reduce solvability of colorless tasks under adversaries to wait-free solvability (see Exercise 7.3). Imbs and Raynal [97] consider a variant of the BG simulation where processes communicate through objects that can be used by at most processes to solve consensus as well as read-write registers. More broadly, BG simulation can be used to relate the power of different models to solve colorless tasks (see Exercise 7.10). Gafni, Guerraoui, and Pochon [60] use BG simulation to derive a lower bound on the round complexity of -set agreement in synchronous message-passing systems.

Gafni [62] extends the BG simulation to certain colored tasks, and Imbs and Raynal [96] discuss this simulation further.

The BG-simulation protocol we described is not layered (though the simulated protocol is layered). This protocol can be transformed into a layered protocol (see Chapter 14 and the next paragraph). Herlihy, Rajsbaum, and Raynal [87] present a layered safe agreement protocol (see Exercise 7.6).

Other simulations [26,67] address the computational power of layered models, where each shared object can be accessed only once. In Chapter 14 we consider such simulations between models with the same sets of processes, but different communication mechanisms.

Chandra [35] uses a simulation argument to prove the equivalence of -resilient and wait-free consensus protocols using shared objects.

Exercise 7.1 is based on Afek, Gafni, Rajsbaum, Raynal, and Travers [4], where reductions between simultaneous consensus and set agreement are described.

7.7 Exercises