5 ms·
New Proof Shows That ‘Expander’ Graphs Synchronize
- peterfirefly 3y agoThis might earn them the Dijkstra Prize -- or somebody else building on top of this will earn it.
- gipp 3y agoCan someone smarter than me explain whether this has implications in distributed consensus?
- aleph_minus_one 3y agoAs far as I understand it, this paper is about synchronization of oscillators, i.e. synchronization of (abstractions of) physical systems. In this sense, I doubt that there is a direct application to distributed consensus, though it is possible that some insanely clever person might get an inspiration from this paper concerning how one could apply ideas that were used to come up with this proof - to show how a specific type of protocol is able to reach consensus under weaker conditions - to build a new type of algorithm for distributed consensus.
- playingalong 3y agoDoes it apply to the turn indicators in a line of cars waiting to turn?
- aleph_minus_one 3y agoNo, since there is no coupling between the turn indicators (finding coupling conditions under which synchronization does(n't) occur is what this research area is about).