[FrontPage] [TitleIndex] [WordIndex

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.


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:

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

2014-06-17 11:58