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

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

The convergecast algorithm is the inverse of a broadcast in a message-passing system (see Flooding)â€”instead of a message propagating down from a single root to all nodes, data is collected from outlying nodes through a direct spanning tree to the root. Typically some function is applied to the incoming data at each node to summarize it, with the goal being that eventually the root obtains this function of all the data in the entire system. (Examples would be counting all the nodes or taking an average of input values at all the nodes.)

The basic convergecast algorithm looks like this:

• Initially, if I am a leaf: send input to parent.
• Upon receiving M from child c:
• Append (c, M) to buffer.
• If I am not the root and buffer contains messages from all my children:
• Send f(messages in buffer + my input) to parent

The details of what is being computed depend on the choice of f:

• If input = 1 for all nodes and f is sum, then we count the number of nodes in the system.
• If input is arbitrary and f is sum, then we get a total of all the input values.
• Combining the above lets us compute averages, by dividing the total of all the inputs by the node count.
• If f just concatenates its input, the root ends up with a vector of all input values.

Running time is bounded by the depth of the tree: we can prove by induction that any node at height h (height is length of the longest path from this node to some leaf) sends a message by time h at the latest. Message complexity is exactly n-1, where n is the number of nodes; this is easily shown by observing that each node except the root sends exactly one message.

2014-06-17 11:58