Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Making Democracy Work: Fixing and Simplifying Egalitarian Paxos

arxiv.org

Post reply on HN
Print view View original

11–20 of 59 posts

Re: Making Democracy Work: Fixing and Simplifying Egalitarian Paxos

#11

Post by keiferski »

kachapopopow wrote: post #9
keiferski wrote: post #7

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.

The EU is pretty good at its intended purpose, which is to tie together European countries in a non-hostile and economically-productive way.

But it seems pretty obviously not very good at any real executive action. Which is, again, by design.

Re: Making Democracy Work: Fixing and Simplifying Egalitarian Paxos

#12

Post by mariusor »

max_ wrote: 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…

> I keep telling people the future of politics is markets & Blockchains.

I hope that you don't mean just things related to cryptocurrencies, because as soon as you demand monetary investment for something, it ceases to be democratic.

Re: Making Democracy Work: Fixing and Simplifying Egalitarian Paxos

#13

Post by dandanua »

kachapopopow wrote: post #9
keiferski wrote: post #7

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.

I wouldn't say so. The first years of the largest war in Europe since WWII have shown that a leaderless EU is incapable of making important decisions crucial to its own survival, as a fallen Ukraine would have led to a divided EU where many countries would be governed by authoritarian fascist regimes, such as the one in Hungary led by Orban.

Re: Making Democracy Work: Fixing and Simplifying Egalitarian Paxos

#14

Post by nathias »

RobotToaster wrote: post #3
max_ wrote: 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. That just sounds like robber barons with extra steps?

you don't understand why technology of public ledgers would benefit public ledgers?

Re: Making Democracy Work: Fixing and Simplifying Egalitarian Paxos

#15

Post by paulryanrogers »

nathias wrote: post #14
RobotToaster wrote: post #3

Earlier quoted context omitted.

> the future of politics is markets & Blockchains. That just sounds like robber barons with extra steps?

you don't understand why technology of public ledgers would benefit public ledgers?

Please go on

Re: Making Democracy Work: Fixing and Simplifying Egalitarian Paxos

#17

Post by dgacmu »

lovelearning wrote: post #16

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 that. So yeah, it's a bit of a thing specifically in the paxos literature.

And wait until I tell you about the Byzantine Generals Problem. :-)

Re: Making Democracy Work: Fixing and Simplifying Egalitarian Paxos

#18

Post by dgacmu »

arielweisberg wrote: post #10

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

In practice, almost every implementation of Paxos uses multi-paxos. Even the "Paxos Made Simple" paper notes:

> In normal operation, a single server is elected to be the leader, which acts as the distinguished proposer (the only one that tries to issue proposals) in all instances of the consensus algorithm.

because otherwise you don't have a mechanism for ordering; the more basic Paxos protocol only discusses how to arrive at consensus for a single proposal, not how to assign numbers to them in a reasonable way that preserves ordering.

Re: Making Democracy Work: Fixing and Simplifying Egalitarian Paxos

#19

Post by dgacmu »

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

Re: Making Democracy Work: Fixing and Simplifying Egalitarian Paxos

#20

Post by _benedict »

arielweisberg wrote: post #10

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

“Paxos” is a term that can mean many different things, so it’s better not to get too attached to any one meaning especially in different contexts.

Multi Paxos is commonly used (especially in industry) as short hand for multi decree Paxos (in contrast to single decree Paxos), but “Paxos” most often refers to the family of protocols, all of which are typically implemented with a leader. It is confusing of course because single decree Paxos is used to implement EPaxos (and its derivatives).

It’s worth noting also that Lamport is (supposedly) on the record as having intended “Paxos” to refer to the protocol incorporating the leader optimisation.

Post reply on HN