They say that in the future, vehicles will be able to talk. Not in the way that those in the Pixar movie “Cars” do, but more in the sense of being able to relay and receive information from surrounding vehicles, buildings, traffic lights, and other infrastructure.
When this happens, it will be due in part to advances in wireless technology, says Haifeng Yu, an associate professor at the NUS School of Computing. Computer scientists like Yu call such settings dynamic wireless networks, because their topology changes with time as their components — cars in this case — are constantly on the move.
“This is a new area with emergent applications that people have been getting into over the past decade,” says Yu. And while work is largely theoretical at the moment, the field’s potential applications are wide-ranging. In addition to facilitating vehicle-to-vehicle and vehicle-to-infrastructure communications, dynamic wireless networks can aid disaster recovery efforts.
“After a tsunami or an earthquake, you don’t necessarily have the infrastructure anymore because base stations from the cell service provider might be destroyed by the disaster…but imagine that each survivor has a cell phone or tablet operating in wifi or bluetooth mode,” says Yu. The devices could form a dynamic network, allowing trapped individuals and rescue workers to communicate with one another.
But there are still many open research questions regarding such applications. One such question revolves around the unknown network diameter — an issue Yu began tackling a few years back, together with his students Yuda Zhao and Irvan Jahja.
Confirming the flooding
When we talk about the diameter of a network, Yu says, what we’re really asking is this: When you propagate a piece of information through the network, how long does it take to reach everyone? In the futuristic case of the cars, for example, how long would it take for a camera mounted on the side of a building to “tell” all the cars within a ten-mile radius about the traffic jam it’s spotted nearby? Since the camera’s radio communication range can be far below ten miles, the information will need to be relayed from car to car, via multiple intermediate hops — the smart car version of “Pass the message” or “Telephone.”
In computer speak, sending out a message or piece of information via multiple hops is known as “flooding” the system. In many instances, what we’d like to know is when the flooding has completed — in other words, when the message has reached all cars in the ten-miles radius. If the diameter is known, all we have to do is simply wait for a fixed amount of time, which is pre-determined by the diameter, after which we are sure that the message has reached all cars. But if the diameter is unknown, which is usually the case in practice, then it is much harder to confirm that the flooding has completed. One method, for example, would be to ask every car to “reply” to the camera once it has received the message — but in doing so, the camera might exceed its limited bandwidth.
“Given that’s the case…it becomes substantially harder to solve the confirmed flooding problem as compared to the case where you know the diameter beforehand,” says Yu.
A good estimation goes a long way
What Yu and his team gleaned from their research was that to determine a dynamic network’s diameter involves “non-trivial overheads.” And when you don’t know or can’t establish the diameter, the task at hand can become significantly more time consuming. This is especially true for certain tasks, such as the confirmed flooding problem, where the additional time incurred will be, at the very minimum, on the polynomial scale, which very roughly speaking is “n to the power of 0.25 rounds,” says Yu.
This is what Yu refers to as the lower bound of a problem, which “means that no matter how hard you try, with all our algorithms today and also all possible algorithms tomorrow…it’s impossible to solve a certain problem with less than a certain amount of time or overhead.”
But it isn’t all doom and gloom, and sometimes there is a way around, Yu says. “We noticed that if you have a reasonable estimate of n (the total number of nodes), then for some problems (though not the confirmed flooding problem earlier), you can avoid that overhead, and end up solving them more efficiently.”
In other words, the lack of knowledge about a dynamic network’s diameter can sometimes be compensated for by a good estimate of the size of the system in question. And when that happens, the time needed to solve those problems reduces to the logarithmic scale — one that is much smaller than the polynomial scale.
The team’s findings, reported last year in premier computer science publication Journal of the ACM, stands apart from earlier studies in one key way — they take into consideration the notion of congestion. This means that the theoretical models used account for the fact that messages sent through networks are limited in size and not “arbitrarily large,” explains Yu, which makes the models more realistic.
The team also took their research one step further, by examining if their findings could be applied to a range of “important fundamental problems in distributed computing.” These problems include leader election and consensus, among others.
“What we show is that for all these problems, if you don’t know the diameter, then solving them in dynamic networks is going to take a large amount of time and incur a fundamental overhead,” says Yu. “But if you know the diameter, then it becomes much easier to solve these problems.”
