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.