Distributed computing

MINIMUM-HOP PATHS

• The round by round approach takes a long time. Can you think of an asynchronous approach that takes less time?
• How do you know when you’re done?

• A

• B

• D

• S

• F

• E

• C

• A

• B

• D

• S

• F

• E

• C

• NETWORK

• ONE POSSIBLE RESULT

Group Protocol

• All nodes start at distance infinity except S which is at distance 0.
• S sends a message. All receivers of S’s message are at distance 1.
• When a node receives a message that it is at distance k and k < that node’s current distance, the node sends k+1 to all its neighbors.

Group Protocol Termination

• Invariant: If for all nodes n the neighbors of n have distance at least dist(n) – 1, then we’re done.

Anna’s Group Protocol Termination

• Each time a node x receives a message m from y, it acks. Now x sends messages to all its neighbors (if distance has gone down). When x receives a reply from all its neighbors, then it replies to y that x is done updating. When s receives all replies, it should broadcast everyone is done.
• Dennis doesn’t think this is done.

Group Protocol Termination

• A node will terminate if it gets a message from all its neighbors

CLUSTERING

• K-means clustering:
• Choose k centroids from the set of points at random.
• Then assign each point to the cluster of the nearest centroid.
• Then recompute the centroid of each cluster and start over.
• Why does this converge?
• A Lyapunov function is a function of the state of an algorithm that decreases whenever the state changes and that is bounded from below.
• With sequential k-means the sum of the distances always decreases.
• Can't get lower than zero.