Efficient Agreement Protocols in Asynchronous Distributed Systems

In an asynchronous distributed system prone to crash failures and message omissions, providing efficient solutions to agreement problems is a key issue when designing fault tolerant applications. The problem of making a unique and ever lasting sequence of decisions is crucial as it lies at the heart of important fault-tolerant techniques. The state machine approach [1] illustrates this concern. In this particular example, replicas of a critical server need to agree on a sequence of incoming requests. Such a sequence is usually constructed by repeatedly calling a Consensus service. Consensus is recognized as one of the most fundamental problems in distributed computing. We consider the context of asynchronous distributed systems in which processes can fail by crashing. By definition, a correct process is a process that never crashes. A process that deviates from its execution specification is considered to be faulty. The classical specification of the Consensus problem [2] requires that each participant proposes an initial value and, despite failures, all the correct processes decide on a single value selected out of these proposals.