1. From the book
Do Exercises 2.15 and 3.10 from AttiyaWelch.
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, t0> to all of its neighbors for some initial time-to-live t0. 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, t0> 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 t0+1 or less from the root eventually receives M. ("Asynchronous" added 2008-01-31.)