Sultanik04Service

From Evan Sultanik

With the SWAT up and running, my dream of having a fleet of networked, handheld computers had been fulfilled. One of the first problems I had hoped to solve with the testbed was that of service discovery: how can we figure out who has what information where? This problem is especially complicated given the fact that there is no central server in ad hoc networks; everyone essentially talks to everyone else directly.

Example: consider, for a moment, that you are piloting a car in a huge bumper car arena. You have some control over your own movement, but there are so many others driving around in the arena that there are constant, unavoidable collisions that throw you off course. From afar, everyone's movement seems random. The problem is that you need to know the time, but you do not have a watch. In fact, there are very few others that have a watch. How do you find the time?

I was essentially trying to solve an equivalent problem on wireless ad hoc networks.

The naïve solution is to simply yell out, "Who has the time‽" The problems with this are:

1. If everyone needs to know the time at once there will be very many yelling people.
2. What if no one with a watch can hear you?

A slightly more intelligent approach might be to:

1. Take a piece of paper and write a request on it for the current time.
2. Pass the piece of paper to the next person that bumps into you.
3. If one who is watch-less receives such a piece of paper, he or she passes it on to the next person that bumps into him or her.
4. When the note eventually reaches someone with a watch, he or she will write the current time on the piece of paper and send it back to you.

The obvious shortcomings to this approach, however, are that:

1. When the note eventually gets back to you, the time will be incorrect!
2. What if, in fact, no one has a watch? How long do you have to wait without receiving a response before you can be sure that no one has a watch?
3. What if not everyone speaks/reads English?

This paper gives a solution to such a problem.

In retrospect, it's not one of my most accessible papers; after reading it as a chapter in my Masters thesis, Moshe commented,

“

[It] reads like Tristram Shandy, but devoid of humor.

”

To what he was referring was the organization I took in writing the paper: first describing the overall technique, then proceeding to iteratively break the problem into successively smaller chunks (like taking apart a matryoshka doll). I can at least claim, however, that my ideas are "born" in the first volume.