4 ms·
I read through the paper when the first draft was published on Arxiv a few weeks ago. It's a very neat algorithm and there seems to be a cool underlying concept
by judofyr 5y ago
I read through the paper when the first draft was published on Arxiv a few weeks ago. It's a very neat algorithm and there seems to be a cool underlying concept here, but I wasn't quite able to make it practical.
This algorithm requires a lot of messages. E.g. if you have four nodes positioned in a line and an action is starting at the end, it will need in total 15 messages (A sends 4 messages to B; B sends 3 messages to both A+C; C sends 2 messages to both B+D; D sends one message to C). And in general what happens is that as the action is being propagated to the boundary of the graph, the current nodes keep "heart beating" to each other: They continue sending messages to each other which doesn't contribute to any specific exchange of information (other than staying in sync).
In addition this is heavily round-based (the nodes only progress once they've received responses from all neighbors) which means that one slow node ("straggler") can stall everything.
I'm super interested if it's possible to expand on the ideas in the paper though!
- gritzko 5y agoThanks, we will address that.
- DarylZero 5y agoHave you looked at Stellar at all? https://www.stellar.org/papers/stellar-consensus-protocol https://www.stellar.org/papers/stellar-consensus-protocol https://medium.com/interstellar/understanding-the-stellar-consensus-protocol-423409aad32e https://medium.com/interstellar/understanding-the-stellar-co...
- gritzko 5y agoActually, I may address it here. > This algorithm requires a lot of messages The algorithm requires (1) data propagation (proposal) messages and (2) heartbeat messages that confirm progress similar to TCP ACKs. The amount of heartbeat messages is not dependent on the presence/absence/number of proposals. Both types of messages are more or less unavoidable. > one slow node ("straggler") can stall everything In fully asynchronous systems, consensus is impossible anyway. Hence, there is always some turn duration/timeout value.