Live data from Hacker News

Making Democracy Work: Fixing and Simplifying Egalitarian Paxos

arxiv.org

21–30 of 59 posts

Re: Making Democracy Work: Fixing and Simplifying Egalitarian Paxos

#21

“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.

Author here.

Lamport simply calls his protocol "Paxos" to refer to both the single‑decree and multi‑decree versions. This is also the case in his other works, e.g., "Fast Paxos" and "Generalized Paxos." The term "Multi‑Paxos" is a later community/industry shorthand for the repeated or optimized use of single‑decree Paxos.

Re: Making Democracy Work: Fixing and Simplifying Egalitarian Paxos

#22

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.

Occupy did not fail, it successfully shifted the entire national political conversation of the United States toward considerations of the class warfare being waged by the wealthy against the general population in ways that are continuing to publicly echo in campaigns and policy discussion ever since

Re: Making Democracy Work: Fixing and Simplifying Egalitarian Paxos

#23
post #19

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 w…

I can’t speak for the authors, but I have been lucky enough to be collaborating with them on behalf of the Apache Cassandra project, to refine and prove the correctness of the Accord protocol - a derivative of EPaxos we have integrated into the database.

It would be fantastic if such a project could be pursued for this variant, which has the distinction of being the only “real world” implementation.

Either way, thank you for the original EPaxos paper - it has been a privilege to convert its intuitions into a practical system.

Re: Making Democracy Work: Fixing and Simplifying Egalitarian Paxos

#24
post #2

>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…

> the future of politics is markets & Blockchains. “Hi everyone, I’m here to excitedly talk about the hyper-capitalist-hellscape I’d like to sell you all! Wait, why are you all leaving?”

I wish for a talk about market failures and possible solutions instead.

Re: Making Democracy Work: Fixing and Simplifying Egalitarian Paxos

#25
* 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?

Re: Making Democracy Work: Fixing and Simplifying Egalitarian Paxos

#26

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.

[deleted]

Re: Making Democracy Work: Fixing and Simplifying Egalitarian Paxos

#27
post #17

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?

The original Paxos paper was termed "The Part-Time Parliament", and was explained -- I'm serious here -- not as a distributed systems protocol, but as a discussion about how electors on a Greek island could vote despite wandering in and out of the room. (Lamport). It set the stage for a series of papers using that theme. We continued on that theme when picking the title for the EPaxos paper, and these folks built on…

https://lamport.azurewebsites.net/pubs/byz.pdf , for those who lack patience.

Re: Making Democracy Work: Fixing and Simplifying Egalitarian Paxos

#28
post #25

* 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 withd…

I'm not sure I understand Q1 - that's exactly the point: If you withdraw _from your account_ and customer B withdraws from _their_ account, then the two events are unrelated and can be executed in either order (and, in fact, replicas would still have the same state even if some executed AB and some BA).

The replay is part of what the authors fixed in the original protocol. I believe but need to read their protocol in more detail on Monday that the intuition for this is that when there's an outage and you bring a new node online, the system commits a Nop operation that conflicts with everything. This effectively creates a synchronization barrier that that forces re-reading all of the previous commits.

But I'm confused about the phrasing of your question because the actor isn't clear here when you say "I re-read events 1-100" -- which actor is "I"? Remember that a client of the system doesn't read "events", it performs operations, such as "read the value of variable X". In other words, clients perform operations that observe _state_, and the goal of the algorithm is to ensure that the state at the nodes is consistent according to a specific definition of consistency.

So if a client is performing operations that involve a replacement node, the client contacts the node to read the state, and the node is responsible for synchronizing with the state as defined by the graph of operations conflicting with the part of the state requested by the client, which will include _all_ operations prior to the replacement of the node due to the no-op.

Re: Making Democracy Work: Fixing and Simplifying Egalitarian Paxos

#29

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.

I think EU federation is pretty good, but I feel very dumbfounded every time dumb decisions that do not benefit member states are made, too much empathy too early I guess.

How do you think the EU (con)federation is pretty good given the remaining of your comment?

Re: Making Democracy Work: Fixing and Simplifying Egalitarian Paxos

#30
post #28
post #25

* 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 withd…

I'm not sure I understand Q1 - that's exactly the point: If you withdraw _from your account_ and customer B withdraws from _their_ account, then the two events are unrelated and can be executed in either order (and, in fact, replicas would still have the same state even if some executed AB and some BA). The replay is part of what the authors fixed in the original protocol. I believe but need to read their protocol in…

I forget the term, it might be Dependency Graph.

Hypothetically lets say there's a synchronized quantum every 60 seconds. Order of operations might not matter if transactions within that window do not touch any account referenced by other transactions.

However every withdrawal is also a deposit. If Z withdraws from Y, and Y withdraws from X, and X also withdraws from Z there's a related path.

Order also matters if any account along the chain would reach an 'overdraft' state. The profitable thing for banks to do would be to synchronously deduct the withdrawals first, then apply them to maximize the overdraft fees. A kind thing would be the inverse, assume all payments succeed and then go after the sources. Specifying the order of applied operations, including aborts, in the case of failures is important.

Post reply on HN