Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

1. Big floods

Prove or disprove: If we run the unmodified basic Flooding algorithm with more than one initiator in a connected, undirected, asynchronous network, every node still receives at least one message.

1.1. Solution

Proof: Essentially just do the original Flooding proof but use induction on distance from the nearest initiator. The induction hypothesis is that any node at distance k from some initiator receives the message for the first time (and thus retransmits it) by time k at the latest. For k=0 this just says they transmit the message initially at time 0. For greater k, I must have some neighbor at distance k-1 who transmits the message to me no later than time k-1, so I receive it no later than k.

2. Network diameter

Give a distributed algorithm for computing the diameter of an (undirected) asynchronous network, i.e., the maximum number of hops between any two nodes. Your algorithm may assume a single initiator, and should report the diameter to the initiator when it finishes; you may also assume each process has a unique id. Compute the time and message complexity of your algorithm.

2.1. Solution

The easiest way to do this is by combining pre-existing tools. One approach:

1. Use DistributedBreadthFirstSearch from the initiator to build a spanning tree (cost: O(diam) time and O(diam*|E|) messages).

2. Upon entry into the spanning tree, each node runs another copy of DistributedBreadthFirstSearch to find the distance from it to all the other nodes in the graph (this is where we need id's, so we can run these in parallel without interference). Cost: O(diam) time and O(n*diam*|E|) messages.

3. Run ConvergeCast within each node's BFS tree to report the maximum distance back to the root, then run ConvergeCast within the initiator's BFS tree to report the maximum of all these values back to the initiator. Cost: O(diam) time and O(n2) messages.

Total is O(diam) time and O(n*diam*|E| + n2) = O(n*diam*|E|) messages.

3. A democratic election algorithm

Suppose you have an anonymous synchronous ring with an odd (but unknown) number of nodes. Initially, each node is given an input from the set {0,1}. Give an algorithm in which every process eventually halts and outputs the majority value, and compute its time and message complexity, or show that no such algorithm is possible.

3.1. Solution

We give an impossibility proof. Consider the case where n=1, and suppose the unique process p has input 1. Suppose we have an algorithm that works in this case. Let k be the number of steps that the algorithm runs before the process halts.

Now construct a new ring with (a) a central region of 2k+1 processes p-k...p0...pk, all starting with 1, plus an additional 2k+2 processes starting with 0. Here the majority value is 0, but we will show that p0 eventually halts and outputs 1.

We do so by induction on the round number i, claiming that in each round i, all processes p-k+i..pk-i have the same state and send the same messages as process p does in the n=1 case. The base case is that in round 0, each process p-k..pk has the same input as p, so performs the same actions. For the induction step, observe that because each process in the range p-k+i..pk-i sends the same messages left and right as p in round i, each process in the range p-k+i+1..pk-i-1 receives the same messages as p in round i, and thus updates its state to the same value in round i+1; this proves the claim. Finally, at round k, we have that p0 performs the same action as p, i.e., it halts and decides 1.

2014-06-17 11:58