# 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, 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.)*