Guaranteed delivery -- in ad hoc networks

A new algorithm for message dissemination in decentralized networks is faster than its predecessors but, unlike them, guarantees delivery. Ad hoc networks - communication networks set up on the fly by mobile sensors - pose problems that ordinary office networks don't. Ad hoc networks are usually decentralized, meaning that no one node knows what the network as a whole looks like. One of the questions raised by decentralized networks is how to relay messages so that they will reliably reach all the nodes, even when the network's shape is unknown. At the ACM-SIAM Symposium on Discrete Algorithms this month, Bernhard Haeupler, a graduate student in MIT's Department of Electrical Engineering and Computer Science, won one of two best-student-paper prizes for a new algorithm that answers that question. Haeupler's algorithm is faster than previous algorithms. But its real interest, he believes, is that it's deterministic, meaning that it will provably relay messages to every node in a network.