A Paxos based algorithm to minimize the overhead of process recovery in consensus (Q2422778)

The paper presents a novel consensus algorithm for distributed system that oscillates between periods of synchrony and asynchrony and that consists of processes which communicate through bi-directional links between each pair of them. The authors extend an existing model by allowing process recovery in the case when all process failures are initial. The proposed algorithm solves consensus with an upper bound that is reduced to a third from the latest known upper bound in the case where a recovered process participates for the first time in an instance of consensus, and reduced by more than thirty percent when a recovered process could have already participated and failed before recovering to participate again in the same instance of consensus.