New algorithm for message dissemination in decentralized networks faster than its predecessors and guarantees delivery

Jan 09, 2013 by Larry Hardesty
Credit: Christine Daniloff/News Office

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 and , won one of two best-student-paper prizes for a new 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, without 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."

If one node in a network maintains a map of the network as a whole, then it's relatively easy to devise a deterministic message-passing algorithm. But that kind of is impractical in ad hoc networks, for several reasons: Ad hoc networks are often deployed in , such as battle zones or the ocean's depths; a supervisor node could simply get knocked offline. Many ad hoc networks—like networks of wirelessly connected cars, or networks of swarming robots investigating an —are constantly changing, so a network map would quickly become obsolete. Finally, devices that form ad hoc networks usually run on batteries, so power is at a premium: Even if a supervisor node could keep up with the network's changing shape, doing so might drain its battery—and those of the nodes feeding it information.

Collective action

So researchers who study are generally looking for distributed algorithms, in which all the nodes perform the same simple, local task, from which the desired global behavior emerges.

As is typical in the field, Haeupler envisions communication in the network as a game that proceeds in a series of rounds, where a round is the time required for two adjacent nodes to exchange information. In the basic version of his algorithm, each node begins by selecting one neighbor and exchanging information with it for one round. Then it selects a second node, and it exchanges information with both of the nodes it's selected for two rounds each.

At this point, the node will have received information that was forwarded by its neighbors. So when it selects a third node, it chooses one from which it hasn't heard either directly or indirectly. Then it sends all its information to all three nodes, for three rounds each. The algorithm continues in this manner, selecting new nodes from which it hasn't heard and incrementing the number of rounds it uses to send information to each of them. It continues this process until it has heard, either directly or indirectly, from all of its neighbors.

Haeupler showed that the largest number of neighbors that a node will ever need to select is equivalent to the logarithm, base two, of the number of nodes in the . And in fact, he developed an even more efficient version of the algorithm, which reduces the number of rounds that a node must spend communicating with each of its neighbors, provided it addresses them in a prescribed order. "There are some indications that this might be as fast as you can do it, but I couldn't completely prove it," Haeupler adds.

Clear picture

"[Haeupler's] analysis is way simpler and much more elegant than what has been done in the past," says Rajmohan Rajaraman, a professor of computer and information science at Northeastern University. "I think it greatly enhances the understanding of processes of the kind that he's studying."

In order to prove that probabilistic information-passing algorithms don't incur exorbitant delays, Rajaraman explains, computer scientists will usually offer "delay-sequence" arguments. "You would use nontrivial probabilistic arguments to show that the probability of this happening is very small, and OK, this will not happen, and for this event to happen, some other event has to happen, and that likelihood is small," he says. "So it will be a chain of arguments which is not deep but certainly is more involved."

In Haeupler's case, however, "that delay-sequence argument basically comes to saying, for there to be an excess of delays, there must exist this large graph structure, which is impossible," Rajaraman says. "It's much easier to look at this argument, believe it, and keep it in your head."

"There are still a couple of gaps, I believe," Rajaraman adds. "The problem is not yet completely settled. But this is a nice almost-end to this line of work."

Explore further: Avatars make the Internet sign to deaf people

Related Stories

Researchers improve fast-moving mobile networks

May 21, 2012

Mobile ad hoc networks (MANETs) allow people in multiple, rapidly-moving vehicles to communicate with each other – such as in military or emergency-response situations. Researchers from North Carolina State University ...

Explained: Ad hoc networks

Mar 10, 2011

In recent years, many network scientists have turned their attention away from centralized networks — such as the Internet and the cell-phone network -- and toward ad hoc networks, wireless networks formed ...

Researchers boost efficiency of multi-hop wireless networks

Apr 19, 2012

Multi-hop wireless networks can provide data access for large and unconventional spaces, but they have long faced significant limits on the amount of data they can transmit. Now researchers from North Carolina State University ...

Explained: Graphs

Dec 17, 2012

When most people hear the word "graph," an image springs to mind: a pair of perpendicular lines overlaid with a line, a curve, or bars of different heights.

Recommended for you

Ride-sharing could cut cabs' road time by 30 percent

16 hours ago

Cellphone apps that find users car rides in real time are exploding in popularity: The car-service company Uber was recently valued at $18 billion, and even as it faces legal wrangles, a number of companies ...

Avatars make the Internet sign to deaf people

Aug 29, 2014

It is challenging for deaf people to learn a sound-based language, since they are physically not able to hear those sounds. Hence, most of them struggle with written language as well as with text reading ...

Chameleon: Cloud computing for computer science

Aug 26, 2014

Cloud computing has changed the way we work, the way we communicate online, even the way we relax at night with a movie. But even as "the cloud" starts to cross over into popular parlance, the full potential ...

User comments : 6

Adjust slider to filter visible comments by rank

Display comments: newest first

antialias_physorg
5 / 5 (3) Jan 09, 2013
That seems liek a great step forward for coordinating all kinds of distributed tasks.

I wonder how quickly it can adapt to a changing net topology (e.g. mobile robots working together), or how quickly it discovers netsplits/downed nodes.

Maybe this can even be used in an inverse manner to define an optimal network distribution given a number of (mobile) nodes and a minimum required redundancy in pathways (possibly given a number of boundary conditions like some individually fixed node, etc. )

This is seriously interesting. Excellent work.
Whydening Gyre
1 / 5 (2) Jan 09, 2013
I wonder... isn't this the way the way brain networking works? It IS excellent...
grondilu
not rated yet Jan 09, 2013
Could this be used for ToR, freenet, netsukuku, BATMAN, i2p, bitcoin, bittorrent and stuff like that?
tadchem
5 / 5 (1) Jan 09, 2013
This would work excellently in autonomous cars for better response to suddenly changing traffic conditions, allowing one vehicle to efficiently alert others around it to a need for braking/steering to avoid a collision due to a non-networked hazard (deer in the headlights).
Tausch
3 / 5 (2) Jan 09, 2013
@Whydening Gyre
What is the neurological anatomical equivalent to the 'node' of a network if the brain is view as a vast network?
Whydening Gyre
2 / 5 (4) Jan 09, 2013
@Whydening Gyre
What is the neurological anatomical equivalent to the 'node' of a network if the brain is view as a vast network?

Wait - this a trick question isn't it...:-)
The answer is - a locality based grouping of neurons and associated support cells (hardware) that is assigned a particular function (software) corresponding to the coordination of inputs. Different localities are quite capable of adapting to a different function should the original location be unable. The "Vast Network" (all nodes combined) determine this functionality. Specific autonomous functions generally work outside this amorphous network, but do maintain SOME (minor) flexibility.
Our brains are (so far) the ultimate analog "machines" produced by nature.
Anatomically speaking, of course...