Why is distributed consensus so hard?

Second in a series describing Howard & Mortier’s generalization of distributed consensus, expressed in PlusCal. The first entry introduced the source papers.

Updated May 27, 2020 to incorporate points from Howard and Mortier (2020) and Santos and Schiper (2013).

I begin this series on distributed consensus by stepping back from the details, considering why the problem seems so hard and specifically why literature on the problem is so difficult to read. This ultimately results from the breadth of issues that must be addressed by any solution. “Distributed consensus” isn’t a single problem so much as a class of problems, with related but distinct solutions. Before describing the specific focus of Howard and Mortier’s paper, I want to set the broader context. This context will help readers who want to apply these results to different forms of consensus.

So why is distributed consensus so hard, not just to solve, but to even describe? Turns out there’s a lot of reasons.

Generalized distributed consensus in PlusCal: Introduction

First in a series describing Howard & Mortier’s generalization of distributed consensus, expressed in PlusCal. The next post describes why consensus is hard.

Simulation checks of the PlusCal version of Lamport's algorithm

Fifth in a series on using the TLA Toolbox to explore the failure tolerance of distributed algorithms. The previous post was a description of Lamport’s 1978 mutual exclusion algorithm.

Lamport's 1978 mutual exclusion algorithm in PlusCal

Fourth in a series on using the TLA Toolbox to explore the failure tolerance of distributed algorithms. The previous post was a specialized discussion of the fairness semantics of PlusCal. The post preceding that was a general discussion of writing distributed algorithms in PlusCal. The next post presents the results of simulation runs on the algorithm.

Fairness semantics of PlusCal

Third in a series on using the TLA Toolbox to explore the failure tolerance of distributed algorithms. The second post presented some PlusCal conventions for writing distributed algorithms. The next post presents Lamport’s (1978) mutual exclusion algorithm in PlusCal.