Guide to Reliable Distributed Systems by Kenneth P. Birman

Author:Kenneth P. Birman
Language: eng
Format: epub
Publisher: Springer London, London

11.3 The Impossibility of Asynchronous Consensus (FLP)

We now turn to the second of the two “tangential” topics mentioned at the start of Sect. 11.2, namely the “impossibility” of achieving agreement in asynchronous distributed systems. Even before tackling the topic, it may be appropriate to remind the reader that this section of the book is covering some rather theoretical material, and that the theory community sometimes defines terms in unexpected ways. In particular, as we will use it below, the term “impossible” does not mean “never possible.” Rather, it means “is not always possible.”

To illustrate this definition, consider the challenge of reaching the author of this book by telephone during a busy day filled with meetings, talks by students, classes to teach, and so forth. Perhaps, over the eight hours of an academic working day, I am actually at my telephone for just four hours. Is it “possible” to reach me? A pragmatic answer is that of course it is: just keep trying. If your call is timed at random, with probability roughly 1/2 you will reach me. If you make n calls at random times, the likelihood of reaching me will be 1–1/2 n . These sound like pretty good odds. But a theoretician might not be satisfied with such an analysis. He or she would reason as follows: suppose that the caller makes n extremely brief calls at times specified by a clever adversary who is keeping one eye on my desk through the door. It will not be difficult for that adversary to steer the caller towards times when I am not at my desk. Indeed, one could formalize a model in which it is provably impossible to reach me; such a result might hold even if I am “almost always” at my desk. The impossibility result considered below is of such a nature: it has limited practical importance yet the result matters because it tells us that there are certain properties our distributed systems simply cannot be shown to possess—notably, liveness guarantees. We will be able to build systems that are safe, in the sense of “not doing bad things,” and that are probabilistically live, in the sense of being “very likely to do a good thing.” But we will not be able to build systems that are guaranteed to “always do a good thing.” Such a goal would violate the theory.

Recall that in Sect. 11.2, we focused on the synchronous computing model. At the other side of the spectrum is what we call the asynchronous computing model (see Fig. 11.3), in which a set of processes cooperate by exchanging messages over communication links that are arbitrarily slow and balky. The assumption here is that the messages sent on the links eventually get through, but that there is no meaningful way to measure progress except by the reception of messages. Clearly such a model is overly pessimistic, but in a way that is different from the pessimism of the Byzantine model, which extended primarily to failures—here we

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.