Distributed Algorithms

Chapter 25 Consensus with Partial Synchrony

In this, the final chapter, we visit consensus problems for the fourth time, this time in the partially synchronous network setting. We consider only stopping failures. It turns out that the results for consensus in the partially synchronous setting are quite different from those in either the synchronous or asynchronous setting. We first present a basic algorithm and a basic lower bound, both derived from corresponding results for the synchronous setting; there is a gap in time complexity between these two results, based on the timing uncertainty. Then we give a more difficult algorithm and a more difficult lower bound result that mostly close this gap. We finish with some results for weaker timing ...