# 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:

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

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.

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(n

^{2}) messages.

Total is O(diam) time and O(n*diam*|E| + n^{2}) = 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}...p_{0}...p_{k}, all starting with 1, plus an additional 2k+2 processes starting with 0. Here the majority value is 0, but we will show that p_{0} 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}..p_{k-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}..p_{k} 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}..p_{k-i} sends the same messages left and right as p in round i, each process in the range p_{-k+i+1}..p_{k-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 p_{0} performs the same action as p, i.e., it halts and decides 1.