# 1. From the book

Do Exercises 2.15 and 3.10 from AttiyaWelch.

## 1.1. Solutions

We won't give detailed solutions, because we don't want to prevent anybody else from using these exercises again. But we will give a rough sketch of the solution or where to find it.

- 2.15
Instead of sending

**explore**immediately, send a message**probe**to all neighbors; each neighbor responds with**already**or**not-yet**depending on whether it has been explored already. Send**explore**to the first neighbor that responds with**not-yet**, or send**parent**if all neighbors respond with**already**. The running time is easily bounded by O(n). For each edge in the tree, it costs 3 message delays for the probe messages to go out, the already/not-yet messages to come back, and the explore message to go out, plus 1 message delay (later) for the parent message; this gives 4(n-1) time. There is an additional delay of 2 time units per leaf node, for the useless probes and their responses. This gives a total of at most 4n-4+2n = 6n-4 = O(n) time. (It is probably possible to get better constants by more carefully analyzing the behavior at leaves.)- 3.10
See this paper.

# 2. Not from the book

Suppose that we modify the stock Flooding algorithm by adding a time-to-live field t, so that when a process p receives a message <M,t>, it sends to its neighbors the message <M, t-1> provided (a) it hasn't seen M before, and (b) t > 0. Initially, the root sends <M, t_{0}> to all of its neighbors for some initial time-to-live t_{0}. The resulting algorithm looks like this:

Each process maintains a single bit of state:

*seen-message*.At time 0, root sets

*seen-message*to true and sends <M, t_{0}> to all neighbors.Upon receiving <M, t>:

If

*seen-message*= false,*seen-message*← trueIf t > 0,

send <M, t-1> to all neighbors

Prove or disprove: In any execution of the above algorithm in an *asynchronous* undirected network, every process p at distance t_{0}+1 or less from the root eventually receives M. *("Asynchronous" added 2008-01-31.)*

## 2.1. Solution

Disproof: consider a graph in which the root node 0 is connected to nodes 1..k, where k = t_{0}, and node k is also connected to node k+1. Route a sequence of messages 0→1→2→...→k before allowing any other message to be delivered. Then k doesn't send this message to k+1 (because the TTL field expires), and any subsequence messages from 0 are discarded (because *seen-message* is true at all possible recipients). So k+1 doesn't see the message even though it is only at distance 2.