* As others have pointed out, Paxos is leaderless. Electing a leader is a performance trick (reduce contention/retries), not a correctness trick - if you want to order your events.
* EPaxos appears to relax ordering as long as the clients can declare their event-dependencies.
Q1) If I withdraw from ATM 1 and someone else withdraws from ATM 2, we are independent consumers - so how do we possibly coordinate which withdrawal depends on the other?
Q2) Assuming that's not a problem, how do I get the ability to replay events? If the nodes don't care about order (beyond constraints), how can I re-read events 1-100, suffer a node outage, and resume reading events 101-200 from a replacement node?
“Classical state-machine replication protocols, such as Paxos, rely on a distinguished leader process to order commands.”
Isn’t that multi-Paxos? Paxos is leaderless.
Very odd opening sentence.
A cited paper's title is "There is more consensus in Egalitarian parliaments." Are terms like "democracy" and "parliament" common terms in distributed computing theory? Or are these intentionally clickbaity/humorous paper titles?
>Egalitarian Paxos introduced an alternative, leaderless approach, that allows replicas to order commands collaboratively.
This is exactly how bitcoin works.
Every 10 minutes the network elects a leader to assort & order transactions and also throw out fraudulent transactions.
If he fails to do this, he is not allow to claim his block reward (technically the "coinbase" transaction)
I keep telling people the future of politics is markets & Blockchains.
Its hard to explain comprehensively and what's strange is that no one has written a thorough book on the topic.
I am happy there are people actually writing such material on this topic.
Albeit its a bit too technical.
Computer science is the future of politics & governance. (I don't think AI is any useful but rather distributed systems)
There is a recurring trend of interpreting democracy to mean "leaderless consensus-based decision-making", which really doesn't work and never has. That's why Occupy and pretty much every other similar bottom-up movement failed: leaders are necessary. People follow other people, not algorithms or groups.
"Making democracy work" should be about training better leaders and getting them into the system.
otrack et al.: Thank you and congratulations! It's gratifying seeing the wheels of research make progress.
My appreciation of formal and machine-checked proofs has grown since we wrote the original EPaxos paper; I was delighted at the time at the degree to which Iulian was able to specify the protocol in TLA+, but now in hindsight wish we (or a later student) had made the push to get the recovery part formalized as well, so perhaps we'd have found these issues a decade ago. Kudos for finding and fixing it.
Have you yourselves considered formalizing your changes to the protocol in TLA+? I wonder if the advances the formal folks have made over the last decade or so would ease this task. Or, perhaps better yet -- one could imagine a joint protocol+implementation verification in a system like Ironfleet or Verus, which would be tremendously cool and also probably a person-year of work. :)
Edited to add: This would probably make a great masters thesis project. If y'all are not already planning on going there, I might drop the idea to Bryan Parno and see if we find someone one of these years who would be interested in verifying/implementing your fixed version in Verus. Let me know (or if we start down the path I'll reach out).