There are algos which prioritize high fault tolerance and do so by increasing the number of leaders (or the minimum number of nodes that must have a copy of the lookup data).

One such algo is Chord:

https://en.m.wikipedia.org/wiki/Chord_(peer-to-peer)

It’s a peer-to-peer ring of nodes which have their values consistently hashed between them. The network leverages these things called “finger tables” which essentially store replication information in the form of a table. This table can have information which is incorrect or outdated and the peer you go to can tell you to go to another peer (usually the “next”/“successor”) until you find the value (or don’t).

Reason this algo can be used with no “leader” is because it can also work by just going to a node and doing a linear scan across all nodes. You don’t need a thumb table to speed up queries.

Leaderless protocols exist in the literature (EPaxos, Caesar, Tempo, ...). These systems usually have a "leader" per transaction, but the leader role is uncontested in normal operation, as it is self-declared by the coordinator of the transaction, so an election only takes place if the coordinator of that transaction fails for whatever reason. Multiple leaders may exist concurrently for any given datum/key the operation involves.

Cassandra is currently developing a leaderless protocol in this vein called Accord. In fact, Cassandra is already using a leaderless protocol for its LWTs; an optimised variant of classic (single-decree) Paxos, but this has significant overheads when competing transactions are declared for the same key at the same time.

Electing a leader and sending changes through the leader simplifies the system and improves throughput and predictability in the presence of contention.

If your transactions are on independent topics, you can distribute the load by sharding leaders: assign ranges of the key space to different leaders and manipulate the elections so each node has a reasonable share of leadership.

You can go leaderless and structure each write as essentially an election: broadcast the tenative transaction (or a request to transact, if the transaction is large enough) to all nodes, if you get a quorum of acceptance, you win and can commit the transaction. But if multiple nodes attempt transactions near the same time, consensus may be time consuming. If you have many nodes, and they all have pending transactions for the same topic, electing a leader and sending all transactions through the leader is going to be a lot faster than establishing consensus on every transaction individually.

Paxos doesn't favour any node above any other node.

That said, if you're trying to distribute for the purpose of throughput, then it might be more efficient to only need one leader rather than the quorum that Paxos requires. Only speculating though.

Paxos is also more efficient if calls go to the same place each time - you avoid contention and revotes, etc.

There's a sharded paxos with a shardmaster. Essentially each shard has its own paxos consensus.

I think in this case there's no longer a 'consensus' - since any node can accept any write immediately.

Look into CRDTs, which are essentially algebraic laws for systems that do this and are guaranteed to eventually converge.

This paper[1] discusses “termination detection” which consensus can directly be built on with trivial proof. It assumes a single environment, and while mathematically that is a kind of graph node it really maps to all outside sources of input and not a cluster member.

[1] https://www.cs.utexas.edu/users/EWD/transcriptions/EWD06xx/E...

Not really; there are algorithms where many nodes propose proposals in parallel, but eventually only one of those proposals gets finalized (or they maintain only a partial ordering, not a full ordering). (See Bullshark and redbelly iirc)

The main issue is that someone has got to pick a final ordering. If there’s a universe of millions of possible orderings it seems that the most efficient way is to have a single node pick a single one.

Many systems have lots of leaders to handle concurrency. Ours has millions of them for instance.

The original dynamo paper (not dynamodb, its predecessor) didn't use leader election. it used quorom with some speed hacks (hinted handoffs and sloppy quorom)

Blockchains