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.

/Solutions are available

1. 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.

2. 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.

3. 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.

Anonymous = no ids. (1)