  Atomic broadcast is an important communication primitive often used to
implement state-machine replication. Despite the large number of atomic
broadcast algorithms proposed in the literature, few papers have discussed how
to turn these algorithms into efficient executable protocols. This paper
focuses on a class of atomic broadcast algorithms based on Paxos, with its
corresponding desirable properties: safety under asynchrony assumptions,
liveness under weak synchrony assumptions, and resiliency-optimality. The paper
presents two protocols, M-Ring Paxos and U-Ring Paxos, derived from Paxos. The
protocols inherit the properties of Paxos and can be implemented very
efficiently. We report a detailed performance analysis of M-Ring Paxos and
U-Ring Paxos and compare them to other atomic broadcast protocols.

Distributed, Parallel, and Cluster Computing