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.

For more up-to-date notes see http://www.cs.yale.edu/homes/aspnes/classes/465/notes.pdf.

1. Old notes on synchronous BFS algorithms

These are based on LynchBook Section 4.2.

1.1. Easy case: network is undirected

Here for every edge uv there is a reverse edge vu. So we can send acknowledgments.

State of the algorithm qi consists of

• parent pointer qi.parent, initially nil.

• list of children, initially empty
• active, initially false

Initiator has same algorithm as other nodes, and same state except that its parent pointer starts out holding its own ID and its active field starts out true.

Send function:

• if q.active
• if q.parent <> myID

• send child(myID) to q.parent
for each neighbor
• send recruit(myID)

Update function:

• if q.parent = nil and there is at least one recruit message in the buffer
• pick some msg recruit(x) q.parent := x q.active := true
else
• q.active := nil
for each message child(x), add x to q.children
• Running time is max(d(root, u)) + 1, since we need to wait for the wave of recruit messages to get all the way out and the last set of child responses to come back. Total messages is |E| + |V| - 1 = O(|E|).
• Proof of correctness: show by induction that after r rounds, first r levels of tree have correct parent pointers, first r-1 levels have correct child lists, r-th level is the only one active. Pretty much a standard "and then this happens" argument.

If we rip out the child messages and parent pointers, we get a protocol for broadcast. Formally, the states look like (msg, state) where state is one of (waiting, active, done). Initial state of initiator is (msg, active), everybody else is (null, waiting).

Send function is

• if q.active
• send q.msg to everybody

Update function is

• if q.waiting and we received msg
• q.msg := msg q.state := active
else if q.active
• q.state := done

To prove correctness, adapt BFS proof. Note that since we aren't sending back child acknowledgments, we don't need to assume an undirected network.

If we are broadcasting many messages, it may be more efficient to build a BFS tree first and then use a modified broadcast algorithm that only sends to children in the BFS tree (this gets the number of messages down from |E|+|V|-1 to just |V|-1). Note that we can also start a new broadcast each round without overloading the network, since the wave of messages carrying broadcast k+1 is always one step behind broadcast k.

1.2. Hard case: directed network

For a directed network, we can't send child messages back to the parent. So instead we use broadcast on every child message to spam it to the entire system (with an extra To field to identify the intended recipient). This requires substantial expansion in the state space and the message length, since we have to track every message we've ever seen to know whether to forward a new copy. However, the time cost doesn't go up by much: since both the initial propagation of the recruit messages and the subsequent child broadcasts take rounds linear in the diameter, the total is just 2*diameter in the worst case.

1.2.1. Termination testing

One problem with a simple modification of the BFS algorithm using broadcast child messages is that a node can't tell if it has any unacknowledged children out there it hasn't heard about yet. So an additional modification is to have each node broadcast a no-child message for each rejected potential parent. A node can then declare itself done precisely when it's received either child or no-child from every neighbor it sent recruit to.

This doesn't quite allow the initiator to detect when when the tree is done being built, since it may be that its own children can acknowledge it fairly quickly. But this can be handled by adding a neighbor count to the child messages (since the initiator gets spammed with all child messages just like anybody else); when the total number of child or no-child messages received equals the total neighbor count (including the initiator's own neighbor count), the initiator can conclude that all recruit messages have been processed and acknowledged.