6 ms·

Are there consensus algorithms that don't require changes go through a leader? In many distributed systems, you want to distribute intake as well.

dboreham 3y ago
Blockchains
- Rhapso 3y ago
  No, those only allow 1 leader and 1 intake at a time. They just pick the leader by proof of waste first.
  - lucb1e 3y ago
    I think you may be confusing proof of work with blockchain as a general principle. (I'm not a fan of this cryptocurrency tech anymore either, my comment is purely about the technical properties which can be interesting to study.)
    - Detrytus 3y ago
      No, GP is right. Without Proof of Work blockchains have no leader - think about Git repo with multiple branches: which one is main? Nothing in blockchain itself determines this, only we, humans chose to name one of them "main" (formerly "master").
      - lucb1e 3y ago
        > Without Proof of Work blockchains have no leader But, proof of stake?
      - Vervious 3y ago
        proof of stake blockchains certainly have leaders. MEV doesn't exist if there aren't designated block proposers
darkmarmot 3y ago
Many systems have lots of leaders to handle concurrency. Ours has millions of them for instance.
User23 3y ago
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/EWD687a.html https://www.cs.utexas.edu/users/EWD/transcriptions/EWD06xx/E...
vhiremath4 3y ago
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) 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.
mrkeen 3y ago
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.
havnagiggle 3y ago
There's a sharded paxos with a shardmaster. Essentially each shard has its own paxos consensus.
toast0 3y ago
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.
- lostcolony 3y ago
  Or more succinctly - a quorum agreeing to a leader to serialize writes through is both less work than trying to get a quorum to agree on every individual write, and equally as consistent.
LAC-Tech 3y ago
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.
Racing0461 3y ago
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)
Vervious 3y ago
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.
_benedict 3y ago
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.

dboreham 3y ago

Blockchains

Rhapso 3y ago
No, those only allow 1 leader and 1 intake at a time. They just pick the leader by proof of waste first.
- lucb1e 3y ago
  I think you may be confusing proof of work with blockchain as a general principle. (I'm not a fan of this cryptocurrency tech anymore either, my comment is purely about the technical properties which can be interesting to study.)
  - Detrytus 3y ago
    No, GP is right. Without Proof of Work blockchains have no leader - think about Git repo with multiple branches: which one is main? Nothing in blockchain itself determines this, only we, humans chose to name one of them "main" (formerly "master").
    - lucb1e 3y ago
      > Without Proof of Work blockchains have no leader But, proof of stake?
    - Vervious 3y ago
      proof of stake blockchains certainly have leaders. MEV doesn't exist if there aren't designated block proposers

darkmarmot 3y ago

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

User23 3y ago

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/EWD687a.html https://www.cs.utexas.edu/users/EWD/transcriptions/EWD06xx/E...

vhiremath4 3y ago

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

mrkeen 3y ago

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.

havnagiggle 3y ago

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

toast0 3y ago

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.

lostcolony 3y ago
Or more succinctly - a quorum agreeing to a leader to serialize writes through is both less work than trying to get a quorum to agree on every individual write, and equally as consistent.

LAC-Tech 3y ago

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.

Racing0461 3y ago

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)

Vervious 3y ago

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.

_benedict 3y ago

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.