Bounded Synchrony

This is a network assumption, also referred to as the synchronous model. In this model, there is a known fixed upper bound \(\Delta\) on message delivery time such that if an honest node \(p\) sends a message \(m\) to another honest node \(q\) at time \(t\), then \(q\) receives \(m\) by time \(t+\Delta\). Additionally, there is a known fixed upper bound \(\Phi\) on the relative speeds of different processors.

History

The synchronous round-based model was first used prominently by [1] and the follow-up [2]. Their algorithms operated in explicit synchronous rounds of message exchange, but the model itself was more of an implicit assumption than a standalone formal definition. According to Lamport, "I think it also contains the first precise statement of the consensus problem." 1

Variants of Synchrony

Dolev, Dwork, and Stockmeyer [4] were the first to formally decompose synchrony into two independent axes:

  1. Processor synchrony – parameterized by \(\Phi\), bounding relative processor speeds. When \(\Phi = 1\), processors operate in lock-step rounds.
  2. Communication synchrony – parameterized by \(\Delta\), bounding message delivery time. When \(\Delta\) is bounded, communication is synchronous; when unbounded, it is asynchronous.

Lock-step Synchrony

In lock-step synchrony, all processors advance through rounds in unison (\(\Phi = 1\)). A processor sends messages at the start of a round, receives all messages from that round, performs local computation, and then advances to the next round. Latency is expressed in terms of rounds. This is the model used by [1] and most classical consensus protocols.

Non-lock-step (Bounded-delay) Synchrony

In non-lock-step synchrony, message delivery is bounded by \(\Delta\) but processors may run at different speeds (\(\Phi > 1\)). Latency is expressed in terms of \(\Delta\) rather than rounds. This is strictly weaker than lock-step synchrony – one can obtain lock-step execution from bounded-delay synchrony by running a clock synchronization protocol (e.g., [5]), but the converse is immediate.

Either form of synchrony alone suffices for Byzantine consensus with optimal \(t < n/3\) resilience [4]. Only when both axes are asynchronous does consensus become impossible [6].

References

[1] Marshall Pease, Robert Shostak, and Leslie Lamport. 1980. “Reaching Agreement in the Presence of Faults.” https://dl.acm.org/doi/10.1145/322186.322188.
[2] Leslie Lamport, Robert Shostak, and Marshall Pease. 1982. “The Byzantine Generals Problem.” https://dl.acm.org/doi/10.1145/357172.357176.
[3] Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. 1988. “Consensus in the presence of partial synchrony.” https://dl.acm.org/doi/10.1145/42282.42283.
[4] Danny Dolev, Cynthia Dwork, and Larry Stockmeyer. 1987. “On the minimal synchronism needed for distributed consensus.” https://dl.acm.org/doi/10.1145/7531.7533.
[5] T. K. Srikanth, and Sam Toueg. 1987. “Optimal clock synchronization.” https://dl.acm.org/doi/10.1145/28869.28876.
[6] Michael J Fischer, Nancy A Lynch, and Michael S Paterson. 1985. “Impossibility of Distributed Consensus with One Faulty Process.” https://dl.acm.org/doi/10.1145/3149.214121.

Footnotes:

1

Lamport's commentary on his publications, https://lamport.azurewebsites.net/pubs/pubs.html, entry [41].

The clean, explicit formalization of the synchronous model – as one defined by a known fixed upper bound \(\Delta\) on message delivery time and a known fixed upper bound \(\Phi\) on relative processor speeds – is most commonly attributed to [3]. The DLS paper needed a crisp definition of synchrony precisely so it could define partial synchrony as a relaxation of it, which gave the synchronous model its precise modern definition.