Abortable Consensus and Its Application to Probabilistic Atomic Broadcast

This paper introduces the specification of abortable consensus in message passing systems with probabilistic message delivery behaviors to address the tradeoff between progress and agreement in asynchronous consensus. The paper presents an abortable consensus algorithm, proves its correctness, and shows how to configure the parameters of the algorithm to satisfy the explicit requirement on the tradeoff between progress and requirement. The probabilistic analysis to the algorithm is novel in that it covers all possible failures and asynchrony allowed by the system model rather than some simple case studies as conducted by most previous researches. The paper further shows how to apply abortable consensus to probabilistic atomic broadcast, and shows that abortable consensus provides stronger properties than probabilistic atomic broadcast.