Distributed computing

SNAPSHOT PROTOCOL IS CORRECT

• Remember that we must prevent a node i from receiving a message before its snapshot time, ti, that was sent by a node j after its snapshot time, tj.
• But any message sent after the snapshot will follow the flagged token at the receiving site because of the FIFO discipline on links. So, bad case cannot happen.

SYNCHRONIZER

• It is often much easier to design a distributed protocol when the underlying system is synchronous.
• In synchronous systems, computation proceeds in “rounds”. Messages are sent at the beginning of the round and arrive before the end of the round. The beginning of each round is determined by a global clock.
• A synchronizer enables a protocol designed for a synchronous system to run an asynchronous one.

PROTOCOL FOR SYNCHRONIZER

• Round manager broadcasts “round n begin” Each node transmits the messages of the round.
• Each node then sends its flagged token to all neighbors and records that time as the snapshot time. (Flagged tokens are numbered to distinguish the different rounds.)
• Each node receives messages along each link until it receives the flagged token, meaning neighbor has sent everything.
• Nodes perform termination back to manager after they have received a token from all neighbors (not just children). Termination involves messages on spanning tree rooted at round manager.

MINIMUM-HOP PATHS

• Task is to obtain the paths with the smallest number of links from a given node s to each other node in the network.
• Suppose the network is synchronous. In the first round s sends to its neighbors. In the second round, the neighbors send to their neighbors. And so it continues.
• When node I receives id s, for the first time, it designates the link on which s has arrived as the first link on the shortest path to s.
• Use the synchronization protocol to simulate rounds.

• A

• B

• D

• S

• F

• E

• C

• A

• B

• D

• S

• F

• E

• C

• NETWORK

• ONE POSSIBLE RESULT