Democratrizing the Parliament

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.


Year:
2001
Laboratories:




 Record created 2005-07-13, last modified 2018-06-22

n/a:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)