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. Previous algorithms, he explains, were probabilistic: No matter how long they were allowed to run, there would always be some minuscule chance that a message didn’t reach some nodes.
“In the distributed community, solving problems without randomization is often a completely different problem, and deterministic algorithms are often drastically slower,” Haeupler explains. “I don’t think that anyone really believed that you can do anything deterministically in this setting.”
