This paper presents a replication algorithm that implements a highly-available, non-deterministic state machine. Our algorithm generalizes the Paxos parliament algorithm of Lamport to cope with non-deterministic computations, while preserving its nice resilience and efficiency properties. The algorithm is surprisingly simple, thanks to the use of two powerful underlying abstractions: weak consensus and weak leader election, together with a generic data structure: consensus bag. As a side-effect of our work, we discuss some similarities and differences between replicating deterministic and non-deterministic state machines. Indirectly, we revisit the traditional classification between state-machine replication and primary-backup.
IC_TECH_REPORT_200107.pdf
openaccess
337.52 KB
Adobe PDF
a00de40822d258f01b15ac2dcbed6dcf