Starting and Terminating options for Distributed algorithms

For distributed algorithms you need a way to let your distributed system know when it is time to start or terminate the computation.

Start Options

  • Single source/ Centralised/ Diffusing. Echo is a typical diffuing algorithm, starting from one single source.
  • Many source/ Decentralised

    Terminate Options

  • Sometimes one node (often the initiator) takes the final decision and can notify the rest (usually omitted phase)
  • In general, this can be very challenging and requires sophisticated control algorithms for termination detection.

Echo Algorithm

Echo is a fundamental diffusing algorithm.

Two phases

Echo combines two phases:

  • A broadcast: “top-down”, builds child-to-parent links in a spanning tree
  • ConvergeCast: “bottom-down”/echo phase, confirms that the node has finished its part.

Child-to-parent links built at broadcast. Parent-to-child links built either at convergecast or by additional confirmation messages immediately after the broadcast.

Termination

After receiving echo tokens from all its neighbours, the source node decides the termination. Optionally, the source node can start a third phase to broadcast this termination to other nodes.

Sync Mode

In Sync mode, you get a BFS spanning tree in broadcast phase (Echo also known as SyncBFS)

Time complexity analysis

Time complexity:
Time Units <= 2D + 1

D is the depth of the BFS spanning tree.

  • In the broadcast stage, in each time unit, the messages go deeper into the tree by 1. It takes at most D time units to reach all nodes.
  • For the leaf nodes to know that their neighbours have all received a message, it takes 1 extra time unit for all leaf nodes to send messages to neighbours. Now all leaf nodes are ready to ConvergeCast.
  • For the root node to receive message for neighbours, nodes at different lengths will need to ConvergeCast back, coming one level up the depth at each time unit. This process takes at most D time units too.

Message complexity analysis

Messages = 2|E|

Because each node will expect to receive from all its neighbours, each edge will have two messages (-> and <-) going through it.

Async Mode

In async mode, you get a spanning tree, but not necessarily a BFS spanning tree.

Time complexity

Time complexity:
Time Units = O(|V|)

There are fast and slow messages.
Each slow message takes 1 (normalised) time unit. Each fast message only takes Epsilon.

Async is a kind of an eager process.

  • You build a spanning tree eagerly, taking whichever path is fast for you - the spanning tree gets built pretty fast, ~ |V|*Epsilon time.
  • Now what is left for you is the slow edges. To finalise the echo, each node will need to finish their ConvergeCast on a slower node.

Message complexity

The message number remains the same as sync model,
message number = 2E = O(|E|)

Time complexity: Async v.s Sync

  • Sync is a special case of Async.
    • Async’s time complexity is a supremum over all possible normalised executions (delivery time in [0; 1]), inclusing sync.
  • In Sync, all edges takes 1 time unit to travel.
    • Waiting for all messages to arrive before making a decision and proceed to the next step helps us build the optimised BFS tree.
    • With a BFS tree, we can ensure that echo finishes in 2|D| + 1 time.
  • In Async, the eager broadcast means we might not choose the overall efficient tree. All graphs could behave like a line.
    • Actually, with a line, |V| = |D| and O(|V|)=O(|D|), async and sync has the same complexity.

What is supremum?

For set (0,1), the supremum is 1. There is no maximum.
For set [0,1], the supremum and the maximum are both 1.