The Feasibility of Partial Synchrony — Epoche C2
Introduction: The Distributed Consensus Problem and its Apparent Limits The problem of achieving consensus in distributed systems is fundamental to reliable computing, underpinning crucial functionalities such as atomic commitment, replicated state machines, and blockchain technologies. It requires a set of processes to agree on a single data value, even in the presence of faults. Historically, the feasibility of consensus has been largely bifurcated along the lines of network synchronicity. Synchronous networks, characterised by known upper bounds on message delay and processing speeds, have long been considered the ideal environment for consensus algorithms. In such systems, protocols like Paxos or Raft can guarantee termination and agreement. Conversely, purely asynchronous networks, where no such bounds exist, were famously proven to preclude deterministic consensus even with a single process crash, as articulated by the Fischer, Lynch, and Paterson (FLP) impossibility result from 1985. This landmark theorem suggested a stringent limitation, fostering a common belief that consensus is inherently impossible outside of perfectly synchronous settings, or at least highly impractical. The Nuance of Partial Synchrony: Overcoming Impossibility However, real-world distributed systems rarely conform perfectly to either extreme of the synchronous-asynchronous spectrum. Network delays fluctuate, and process speeds vary, but typically within some bounds that are sometimes known, sometimes unknown, and sometimes temporarily violated. This observation led to the development of the partially synchronous model, first formally introduced by Dwork, Lynch, and Stockmeyer (1988). This model offers a more realistic abstraction of practical network environments and, crucially, demonstrates that consensus is indeed achievable under specific, well-defined conditions within these systems, thus refining the implications of the FLP theorem. The core insight is that while full synchrony is not strictly necessary, some degree of synchrony is eventually required for progress. Key Conditions for Consensus in Partially Synchronous Networks The achievability of consensus in partially synchronous networks hinges on several critical conditions, which collectively allow protocols to make progress despite periods of asynchrony. These conditions effectively introduce enough 'synchrony' into the system to circumvent the FLP impossibility result, which strictly applies only to purely asynchronous systems. The Global Stabilisation Time (GST): This is perhaps the most pivotal concept. GST refers to a point in time, $T_{GST}$, after which the network behaves synchronously. Specifically, after $T_{GST}$, all messages sent are delivered within some bounded delay $\Delta$, and process speeds are within a known factor. Before $T_{GST}$, the network can be arbitrarily asynchronous. The critical aspect is that $T_{GST}$ itself is unknown to the processes. While processes do not know when synchrony begins, its eventual arrival is guaranteed. This eventual synchrony is what allows for termination. Bounded Message Delay ($\Delta$): Once $T_{GST}$ has passed, messages are guaranteed to be delivered within a known upper bound $\Delta$. This bound is crucial for protocol designers, as it allows for the use of timeouts. For instance, if a process sends a message and expects a reply, it can set a timeout of $2\Delta$ (round-trip time) and infer a fault or message loss if no reply is received within this period. Without such a bound, timeouts are meaningless, and distinguishing between a slow process/network and a crashed process becomes impossible. A Majority of Correct Processes: Similar to synchronous systems, consensus in partially synchronous systems typically requires that a majority of processes remain non-faulty. If $n$ is the total number of processes and $f$ is the number of faulty processes, then $f Consider a simplified protocol where processes propose values and try to commit one. In an asynchronous phase (before $T_{GST}$), messages might be arbitrarily delayed, leading to endless rounds of proposals and re-proposals without convergence. However, once $T_{GST}$ is reached, and assuming a majority of correct processes, a leader can be elected, and its proposals can propagate reliably within time $\Delta$. For example, if a leader proposes a value $v$ and sends it to all processes, it expects acknowledgements. If a process receives $v$ and sends an acknowledgement, it knows this will arrive at the leader within $\Delta$. The leader, upon receiving acknowledgements from a majority, can then commit $v$. The eventual synchrony guarantees that such a majority can be formed and communicated. The existence of $T_{GST}$ and $\Delta$ fundamentally changes the landscape from purely asynchronous systems. While the FLP result holds that any deterministic consensus protocol requires three rounds in the worst-case and is impossible with one crash in an asynchronous system, the partially synchronous model allows for protocols that can eventually reach consensus. This is often achieved by employing techniques like rotating leaders or phase-based commitment, where progress is guaranteed once the system enters its synchronous phase, even if that phase's onset is unknown. For instance, the minimum number of rounds for consensus in a partially synchronous system with $f$ crash failures and $n$ processes, where $n > 2f$, is often characterised by phases of communication that converge once synchrony is established. The ability to distinguish between a crashed process and a slow process after $T_{GST}$ via timeouts is key to this convergence. Mathematical Formalisation and Implications The formalisation of partially synchronous systems often involves defining a system execution as a sequence of events. Let $M$ be the set of messages, $P$ the set of processes, and $S$ the set of states. An execution is a sequence of configurations $C_0, C_1, \dots$ wh