Distributed leader election algorithms

I’m still reading through the docs, so apologies if this question is answered somewhere in some doc already.

I understand that you make an interesting use of PoW (with the difficulty per member achieving overall good efficiency), but have you considered alternative algorithms, such as those involving commitment schemes (normally used in distributed coin flipping).

If so I’d be interested in knowing what are the pros & cons of using PoW vs commitment-scheme based approaches.

We use PoW only as a P2P communication protocol, as it offers a good way to have only one speaker at a time, randomly choosed, with a good resistancy to failures (there is not only one potential speaker, so we always have someone who can speak).

Also, I don’t really get what is commitment scheme useful for. Can you explain it a bit?

Sure, commitment scheme is a strategy for achieving provably fair lotteries in distributed scenarios. In other words, the active nodes cooperate to select the next speaker, without resorting to PoW.

Think of it as every node doing a secret random dice roll, and then combining all the results to compute a combined dice roll. The combined dice roll dictates which of the nodes is the next speaker (possibly selecting also 1 or 2 backup speakers, in case the selected speaker becomes inactive).

A good explanation of a commitment scheme in practice: Crypto Lottery

If this kind of strategy has not been looked into is there any interest in exploring it? I would not mind to devote some time to explore it, especially if it can be turned into an academic paper :slight_smile:

I don’t know at all, but for sure Duniter is already behaving quite well with a low level PoW. And speaking is quite linear: we don’t need to have backup speakers neither check if the main speaker actually speak in due time, because we have 2/3 of the network which for sure will speak at some point, and on average it is 5 minutes.

So currently the interest is not quite obvious for Duniter.

Note: here is our current network state:

I’ve just added a new node to that list! (duniter.ktorn.com)

I suppose the main advantage of using the commitment scheme would be that the network can achieve the same speaking rate with a cpu usage of 0% (each node just needs to generate one single random number per block).

To be honest I have never implemented such a scheme either, but I think similar schemes are used by PoS coins like NXT. I’ll investigate more and report back my findings.

I’ve been the witness of your very first block, few seconds ago. Congrats! You will automatically receive some money from Remuniter for this.

1 « J'aime »

Great! :slight_smile: