The developers of Google’s Spanner database built an interesting system but chose to build their own clock synchronization technology instead of getting a more precise off the shelf solution and chose to make extensive use of the notoriously complex Paxos
Chang-Maxemchuk atomic broadcast
The Chang-Maxemchuk algorithm (US Patent 4,725,834 ) solves atomic broadcast (and in-order broadcast) problems for distributed networks in a far simpler and more efficient way than some popular alternatives. In fact, the obscurity of this method is hard to understand given the
Distributed consensus and network reliability
All of the distributed consensus algorithms I have been reviewing recently (Paxos, Raft, Zab, Chang Maxemchuck, Viewstamped, … ) are based on a number of assumptions about the network environment, including the assumption that messages may be lost but are
circularity problems in distributed consensus
Distributed consensus involves organizing a collection of independent agents – processes or network sites – to agree on some value or sequence of values. Many distributed consensus methods depend on a leader-follower scheme in which the leader is an agent
Making Paxos face facts
Replaced by Paxos Demystified. Lamport’s “Paxos Made Simple” paper is notoriously hard to understand but at least part of the difficulty is that the algorithm changes radically in the middle of the presentation. The first part of the paper presents a
Paxos and other consensus algorithms and the unaccountable love for asynchrony
I’ve been looking at Paxos and Raft and Zab and other algorithms that can loosely be called “consensus” algorithms because we want to see where we can improve distributed system operation with precision time synchronization or where we can offer novel features
More on Fischer, Lynch, Patterson and the parrot theorem.
I’m thinking about distributed consensus algorithms, timestamping, and databases and if you read that literature you will see many references to the Fischer, Lynch, Paterson “theorem”. Google Scholar tells me the paper has been cited more than 4500 times. The theorem