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₀> to all of its neighbors for some initial time-to-live t₀. 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₀> to all neighbors.

• Upon receiving <M, t>:

  • If seen-message = false,

    • seen-message ← true

    • If 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₀+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₀, 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.