The Consensus problem is recognized as a central paradigm of fault-tolerant distributed computing. In a purely asynchronous system, consensus is impossible to solve in a deterministic manner. By enriching the system with some synchrony assumptions, several solutions were proposed in order to circumvent the impossibility result, among which the Paxos protocol. This work represents a contribution to the construction of efficient consensus protocols in asynchronous distributed systems. The algorithmic contribution of the thesis consists of an efficient framework, called the Paxos-MIC protocol, that follows the Paxos approach and integrates two existing optimizations. Paxos-MIC generates a sequence of consensus instances and guarantees the persistence of all decision values. The main feature of the protocol is its adaptability. As one of the optimizations may be counterproductive, Paxos-MIC incorporates a triggering mechanism that dynamically enables the optimization. The mechanism relies on several triggering criteria able to predict if the use of the optimization will be beneficial. Extensive experiments on the Grid'5000 testbed were carried out with the purpose of evaluating the protocol and the efficiency of the triggering criteria. A second part of the work focuses on the use of consensus as a building-block for higher-level applications. We consider the particular context of transactional mobile agents and we propose a solution to support the execution of transactions in an ad-hoc network. This solution relies on an everlasting sequence of decision values generated by repeatedly invoking a consensus building-block. This service is provided by the Paxos-MIC framework.
