Distributed computing

MODEL

• Links are bidirectional. A message traverses a single link.
• All nodes have distinct ids. Each node knows immediate neighbors
• Messages incur arbitrary but finite delay.
• FIFO discipline on links, i.e., messages are received in the order they are sent.

PRELIMINARY: ESTABLISH A SPANNING TREE

• Some node establishes itself as the leader (e.g. node x establishes a spanning tree for its broadcasts, so x is root).
• That node sends out a “request for children” to its neighbors in the graph.
• When a node n receives “request for children” from node m

• if m is the first node that sent n this message, then n responds “ACK and you’re my parent”; sends request for children to its other neighbors else n responds “ACK”

• Each node except the root has one parent, and every node is
• in the tree. A leaf is a node that only received ACKs from
• neighbors to which it sent requests.

TERMINATING THE SPANNING TREE

• A node that determines that it is a leaf sends up an “I’m all done” message to its parent.
• Each non-root parent sends an “I’m all done” message to its parent once it has received such message from all its children.
• When the root receives “I’m all done” from its children, then it is done.

BROADCAST WITH FEEDBACK

• A given node s would like to pass message X to all other nodes in the network and be informed that all nodes have received the message.
• Algorithm:
• Construct the spanning tree and then send X along the tree.
• Have each node send an acknowledgement to its parent after it has received an acknowledgement from its children.

PROCESS TERMINATION

• Def: Detect the completion of a collection of non-interacting tasks, each of which is performed on a distinct processor.
• When a leaf finishes its computation, it sends an “I am terminated” message to its parent.
• When an internal node completes it has received an “I am terminated” message from all of its children, it sends such a message to its parent.
• When the root completes and has received an “I am terminated” message from all of its children, all tasks have been completed.

• 5

• 4

• 3

• 2

• 4

• 1

• 4