New Proof Shows That ‘Expander’ Graphs Synchronize

#1

Post by flying_sheep » Tue, Jul 25, 2023, 1:53 AM UTC

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

Re: New Proof Shows That ‘Expander’ Graphs Synchronize

#2

Post by peterfirefly » Tue, Jul 25, 2023, 3:40 PM UTC

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

Re: New Proof Shows That ‘Expander’ Graphs Synchronize

#3

Post by gipp » Tue, Jul 25, 2023, 4:08 PM UTC

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

Re: New Proof Shows That ‘Expander’ Graphs Synchronize

#4

Post by playingalong » Tue, Jul 25, 2023, 5:56 PM UTC

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

Re: New Proof Shows That ‘Expander’ Graphs Synchronize

#5

Post by aleph_minus_one » Tue, Jul 25, 2023, 5:57 PM UTC

gipp wrote: post #3

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.

Re: New Proof Shows That ‘Expander’ Graphs Synchronize

#6

Post by aleph_minus_one » Tue, Jul 25, 2023, 5:59 PM UTC

playingalong wrote: post #4

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

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