Abstract
This paper presents the abstraction of lazy consensus and argues for its use as an effective component for building distributed agreement protocols in practical asynchronous systems where processes and links can crash and recover. Lazy consensus looks like consensus, is equivalent to consensus, but is not consensus. The specification of lazy consensus has an on-demand and a re-entrant flavors that makes its use very efficient, especially in terms of forced logs, which are known to be major sources of overhead in distributed systems. We illustrate the use of lazy consensus as a building block to develop efficient atomic broadcast and atomic commitment protocols: two central abstractions in our DACE middleware environment.
Introduction
In distributed computing, achieving consensus—agreement on a single value among multiple computers—is essential for reliability. However, implementing consensus in practical environments where processes can crash and recover often incurs a significant "modularity tax." Traditional protocols require frequent "forced logs" (synchronous disk writes) to ensure state is preserved across failures. Since disk I/O is significantly slower than network communication, these logs become a primary performance bottleneck, often leading developers to abandon clean abstractions for ad-hoc, optimized code.
To address this, we introduce Lazy Consensus, a redesigned agreement abstraction optimized for the crash-recovery model. By relaxing certain properties of standard consensus, we can eliminate unnecessary overhead while maintaining mathematical equivalence, allowing for modular yet high-performance distributed protocols.
The Lazy Consensus Abstraction
Lazy Consensus improves upon standard consensus through two key "flavors":
- On-demand: Unlike traditional consensus where every correct process is expected to eventually decide, lazy consensus only guarantees a decision for processes that actively propose a value. Other processes can serve as "witnesses," avoiding the overhead of receiving or logging final results they do not need.
- Re-entrant: This flavor allows a process to crash and recover, then propose a different value for the same consensus instance. This idempotency removes the need to log initial proposals to disk; if a process fails before its proposal is accepted, it simply restarts the attempt upon recovery.
Efficiency and Recovery
The primary goal of Lazy Consensus is to minimize forced logs during "normal" execution (when no crashes occur). In such cases, the algorithm requires only one forced log per process to store the estimate during the coordinator's attempt, as shown in Figure 1.
When failures do occur, the protocol handles them gracefully without compromising safety. A process that crashes can recover its state from stable storage and rejoin the protocol. The re-entrant property ensures that the recovery process is lightweight, as the system does not need to maintain a perfect history of every initial proposal.
Evaluation
We evaluated Lazy Consensus within the DACE middleware framework using a cluster of 60 UltraSUN 10 machines connected via Fast Ethernet. Performance was compared against the ACT98 protocol, a then-standard for consensus in crash-recovery models.
Key results include:
- Throughput: In a 2-process configuration, Lazy Consensus achieved approximately 8 operations per second, compared to roughly 1.5 for ACT98.
- Scalability: Lazy Consensus maintained a significant performance lead as the number of processes increased, outperforming ACT98 by a factor of four in a 10-process setup (approx. 2 ops/sec vs <0.5 ops/sec).
- Message Efficiency: By relaxing termination requirements for non-proposers, the protocol can save up to $2n - 2$ messages in specific configurations.
Conclusion
Lazy Consensus demonstrates that modularity in distributed systems does not have to come at the cost of performance. By optimizing for the common case and leveraging "on-demand" and "re-entrant" properties, we provide a building block that makes protocols like Atomic Broadcast and Atomic Commitment practical for real-world asynchronous systems. Future work will explore applying these "lazy" principles to other distributed agreement abstractions beyond consensus.
Summary updated