New Proof Shows That ‘Expander’ Graphs Synchronize

New Proof Shows That ‘Expander’ Graphs Synchronize(quantamagazine.org)

36 points by flying_sheep 2 years ago | 5 comments

gipp 2 years ago |

Can someone smarter than me explain whether this has implications in distributed consensus?

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

peterfirefly 2 years ago |

This might earn them the Dijkstra Prize -- or somebody else building on top of this will earn it.

playingalong 2 years ago |

Does it apply to the turn indicators in a line of cars waiting to turn?

aleph_minus_one 2 years ago | |

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