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