/Solutions

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₀> 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.)