Making Democracy Work: Fixing and Simplifying Egalitarian Paxos

> the future of politics is markets & Blockchains.

That just sounds like robber barons with extra steps?

> 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?”

The network does not elect a leader. that is a mischaracterization of the PoW process.

It's not like you are hashing based on your public key or something and then you get to sign a block afterwards. You have to commit to a block template before every hash. And also the miner is decided randomly by a weighted hashrate.

Imagine applying this to anything else. The group with the most (extremely specialized) computer power just gets to decide everything?

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

>> Egalitarian Paxos introduced an alternative, leaderless approach...

> Every 10 minutes the network elects a leader to...

From that it sounds like it is completely different to how Bitcoin works. Bitcoin "elects" a leader node once every so often and this paper claims its protocol does not have a leader node. It is pretty easy to imagine a day passing in the Bitcoin world where one node is in control of all the transactions for that day with no ability for any other peer miner to have any influence at all in what transactions end up in the blockchain.

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.

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

Democracy which is all about "leaders" is not democracy. Find another word.

> "Making democracy work" should be about training better leaders and getting them into the system.

AND fixing the (fundamentally broken) system by reducing the influence of money.

You are confusing "democracy as used colloquially for government" and "democracy as used by computer scientists to design systems that still work on failure prone networks"

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.

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

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.

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

msc thesis only left. happy to do it with a twist. training an ml model to speed up proof generation and verification.

can you share more?

Thank you, dgacmu! We are currently working on a TLA+ specification with master's students, and we plan to verify it with TLC and Apalache. I discovered that Iulian's TLA+ specification was missing a ballot variable [1] by injecting a trace, because exhaustive exploration was not tractable. Therefore, state-space explosion is likely to become a problem (systems of interest contain 7–9 processes with non‑transitive conflicts). In that case, intermediate abstractions will be necessary, which may naturally lead us to theorem proving.

Once the specification is ready, I'll post about it here. :)

[1] https://arxiv.org/abs/1906.10917

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.

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.

The two commands affect the same account balance, so they don't commute, so these commands conflict. Every EPaxos worker is required to be able to determine whether any two commands are conflicting, in this case it would be something like:

def do_commands_conflict(c1): return len(write(c1) & read(c2)) > 0 or len(write(c2) & read(c1)) > 0 or len(write(c1) & write(c2)) > 0

Whenever an EPaxos node learns about a new command, it compares it to the commands that it already knows about. If it conflicts with any current commands, then it gains a dependency on them (see Figure 3, "received PreAccept"). So the commands race; the first node to learn about both of them is going to determine the dependency order [in some cases, two nodes will disagree on the order that the conflicting commands were received -- this is what the "Slow Path" is for].

The clients don't coordinate this; the EPaxos nodes choose the order. The cluster as a whole guarantees linearity. This just means that there's at least one possible ordering of client requests that would produce the observed behavior; if two clients send requests concurrently, there's no guarantee of who goes first.

(in particular, the committed dependency graph is durable, even though it's arbitrary, so in the event of a failure/restart, all of the nodes will agree on the dependency graph, which means that they'll always apply non-commuting commands in the same order)

If a node thinks it's better suited as leader, it can always force an election immediately for the next term. Things could go badly if you're wrong though