3 ms·

Leader election in distributed systems is still an unresolved problem AFAIK except for proof of work. The problem is what does the leader have to give up to be

Leader election in distributed systems is still an unresolved problem AFAIK except for proof of work. The problem is what does the leader have to give up to be a leader? The economic value of being the leader must be balanced by the work to become the leader otherwise there is an opportunity for arbitrage. For instance, if the value of leadership is X and the cost to do a Sybil or other attack is X/10 the network will be eventually attacked that way.

ketzu 9y ago
You seem to use a very narrow definition of "distributed system" compared to most people. Could you explicitly state your assumptions? Your "distributed system" seems to coontain assumtions such as trustlessness and openness towards new participants. (No sybil attacks with fixed entities)
- narrator 9y ago
  Yes, I was assuming a cryptocurrency situation in which the system is open, new participants can join, and it must work under byzantine fault-tolerant conditions. In a system such as RAFT or PAXOS this isn't the case and thus these systems can properly elect leaders.
alistproducer2 9y ago
In distributed ledgers, it doesn't matter who the leader is. The system only has to ensure that leadership is distributed in such a way that it is statistically infeasible or economically unprofitable to rewrite history. PoW distributes the leadership (block creation) via crypto puzzles. PoS tries to use economic incentives to make bad behavior more expensive than good. There's work being done (which I personally believe is the right way to go) in using a leader election-based system that works like a lottery (Algorand[0] is an example). The basis of such a system is going to be the creation of non-biasable pseudo-random number generation. Along these lines one of the more intriguing projects is called RandHound[1]. It's a way of creating distributed randomness (according to the paper's title). I think chains secured via lottery leader selection protocol has more promise than PoS. Edit: for clarity A lottery-based system works because the "winning numbers" (imagine a winner being a node whose public key when XOR'd with the winning number is below a certain value) are known to all (a protocol like randhound ensures that all nodes know the winning number). A winner's bundle of transactions are validated as his/her's by cryptograpic signature (which can be verified using the same public key that is used to confirm this person is truly a winner). Those are the broad strokes. Obviously there's a lot more to getting it to work. I've been working on it for months and still haven't gotten around to putting it down on paper. [0]: https://arxiv.org/abs/1607.01341 https://arxiv.org/abs/1607.01341 [1]: https://eprint.iacr.org/2016/1067.pdf https://eprint.iacr.org/2016/1067.pdf
- bradleyjg 9y ago
  Isn't the problem with random selection, that if there's very little cost to enter then a bad actor can flood lottery with entries?
  - avdempsey 9y ago
    My understanding is they try to mitigate this by having a minimum account balance to participate.
    - skinner_ 9y ago
      That's one way to introduce proof-of-stake.
- jcfrei 9y ago
  > There's work being done (which I personally believe is the right way to go) in using a leader election-based system that works like a lottery (Algorand[0] is an example). Probably what you meant but I still wanted to mention it: Bitcoin (or most PoW schemes) work like a lottery. Think of each attempt at generating a nonce below the required difficulty as a lottery ticket. The more nonces you generate (the more hashes per second you compute) the higher your chance of winning. The system works because people who spent lots of money on lottery tickets in the past (and maybe won one or two times) are incentivized to keep the lottery running in an honest manner (so their prize keeps its value - if they haven't spent it). > Along these lines one of the more intriguing projects is called RandHound[1]. It's a way of creating distributed randomness (according to the paper's title). I think chains secured via lottery leader selection protocol has more promise than PoS. Another notable mention is dfinity (dfinity.org). They have a very interesting technology stack and I'm hoping for discussions about it in the future on HN.
  - alistproducer2 9y ago
    Yes and no. A true lottery predictably periodic - it happens in rounds. PoW puzzles are async and so the chain can fork. The second property of the crypto puzzle kicks in here - the statistically predictable number of hashes necessary to solve the puzzle which can then be used to calculate an average time necessary to create a valid block. With a forking chain, it's this time gap that secures the chain against rewrites. So yes, PoW is used to distribute block creation among the network but it differs from a true lottery system in that it is not synchronized into rounds.
mazieres 9y ago
What's interesting is that SCP implements consensus without electing a leader. There are, of course, numerous asynchronous protocols that do this, like Ben Or, Rabin, Mostéfaoui, and most recently HoneyBadger, but is rarer for synchronous protocols like SCP. However, it is necessary for SCP's setting, because if you don't even have agreement among nodes over what nodes do and don't exist in the system, how could you hope to elect a leader. One way to view how SCP avoids leader election is to consider that it is effectively emulating the leader. SCP has two phases, a nomination and a balloting phase. The nomination phase is effectively like one or more instances of an asynchronous broadcast protocol (which don't require a leader since multiple nodes can choose to broadcast). The balloting phase is like Paxos, except that the value to propose is embedded in the ballot number so nodes don't require a leader to tell them what is being proposed--they can each emulate the leader themselves.

ketzu 9y ago

You seem to use a very narrow definition of "distributed system" compared to most people. Could you explicitly state your assumptions? Your "distributed system" seems to coontain assumtions such as trustlessness and openness towards new participants. (No sybil attacks with fixed entities)

narrator 9y ago
Yes, I was assuming a cryptocurrency situation in which the system is open, new participants can join, and it must work under byzantine fault-tolerant conditions. In a system such as RAFT or PAXOS this isn't the case and thus these systems can properly elect leaders.

alistproducer2 9y ago

In distributed ledgers, it doesn't matter who the leader is. The system only has to ensure that leadership is distributed in such a way that it is statistically infeasible or economically unprofitable to rewrite history. PoW distributes the leadership (block creation) via crypto puzzles. PoS tries to use economic incentives to make bad behavior more expensive than good. There's work being done (which I personally believe is the right way to go) in using a leader election-based system that works like a lottery (Algorand[0] is an example). The basis of such a system is going to be the creation of non-biasable pseudo-random number generation. Along these lines one of the more intriguing projects is called RandHound[1]. It's a way of creating distributed randomness (according to the paper's title). I think chains secured via lottery leader selection protocol has more promise than PoS. Edit: for clarity A lottery-based system works because the "winning numbers" (imagine a winner being a node whose public key when XOR'd with the winning number is below a certain value) are known to all (a protocol like randhound ensures that all nodes know the winning number). A winner's bundle of transactions are validated as his/her's by cryptograpic signature (which can be verified using the same public key that is used to confirm this person is truly a winner). Those are the broad strokes. Obviously there's a lot more to getting it to work. I've been working on it for months and still haven't gotten around to putting it down on paper. [0]: https://arxiv.org/abs/1607.01341 https://arxiv.org/abs/1607.01341 [1]: https://eprint.iacr.org/2016/1067.pdf https://eprint.iacr.org/2016/1067.pdf

bradleyjg 9y ago
Isn't the problem with random selection, that if there's very little cost to enter then a bad actor can flood lottery with entries?
- avdempsey 9y ago
  My understanding is they try to mitigate this by having a minimum account balance to participate.
  - skinner_ 9y ago
    That's one way to introduce proof-of-stake.
jcfrei 9y ago
> There's work being done (which I personally believe is the right way to go) in using a leader election-based system that works like a lottery (Algorand[0] is an example). Probably what you meant but I still wanted to mention it: Bitcoin (or most PoW schemes) work like a lottery. Think of each attempt at generating a nonce below the required difficulty as a lottery ticket. The more nonces you generate (the more hashes per second you compute) the higher your chance of winning. The system works because people who spent lots of money on lottery tickets in the past (and maybe won one or two times) are incentivized to keep the lottery running in an honest manner (so their prize keeps its value - if they haven't spent it). > Along these lines one of the more intriguing projects is called RandHound[1]. It's a way of creating distributed randomness (according to the paper's title). I think chains secured via lottery leader selection protocol has more promise than PoS. Another notable mention is dfinity (dfinity.org). They have a very interesting technology stack and I'm hoping for discussions about it in the future on HN.
- alistproducer2 9y ago
  Yes and no. A true lottery predictably periodic - it happens in rounds. PoW puzzles are async and so the chain can fork. The second property of the crypto puzzle kicks in here - the statistically predictable number of hashes necessary to solve the puzzle which can then be used to calculate an average time necessary to create a valid block. With a forking chain, it's this time gap that secures the chain against rewrites. So yes, PoW is used to distribute block creation among the network but it differs from a true lottery system in that it is not synchronized into rounds.

mazieres 9y ago

What's interesting is that SCP implements consensus without electing a leader. There are, of course, numerous asynchronous protocols that do this, like Ben Or, Rabin, Mostéfaoui, and most recently HoneyBadger, but is rarer for synchronous protocols like SCP. However, it is necessary for SCP's setting, because if you don't even have agreement among nodes over what nodes do and don't exist in the system, how could you hope to elect a leader. One way to view how SCP avoids leader election is to consider that it is effectively emulating the leader. SCP has two phases, a nomination and a balloting phase. The nomination phase is effectively like one or more instances of an asynchronous broadcast protocol (which don't require a leader since multiple nodes can choose to broadcast). The balloting phase is like Paxos, except that the value to propose is embedded in the ballot number so nodes don't require a leader to tell them what is being proposed--they can each emulate the leader themselves.