Click here for full text:
Probabilistic Atomic Broadcast
Felber, Pascal; Pedone, Fernando
Keyword(s): No keywords available.
Abstract: Reliable distributed protocols, such as consensus and atomic broadcast, are known to scale poorly with large number of processes. Recent research has shown that algorithms providing probabilistic guarantees are a promising alternative for such environments. in this paper, we propose a specification of atomic broadcast with probabilistic liveness and safety guarantees. We present an algorithm that implements this specification in a truly asynchronous system (i.e., without assumptions about process speeds and message transmission times). Our algorithm tolerates a configurable number of crash failures, and delivers messages reliably and in order with high probability. Furthermore, even though some messages may be delivered out of order, processes can determine when this happens.
Back to Index