Service Discovery on Dynamic Peer-to-Peer Networks Using Mobile Agents

The absurd realization that it has almost exactly been a decade since I defended my master’s thesis took me by surprise. It seems like yesterday. That work has had some decent exposure over the years, but, like most creative works produced toward the beginning of one’s career, I do not look back on it as a paragon.

Moshe Kam, upon reading a preliminary draft, summarized it very well:

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

He was referring to my organization of one particular chapter: First I described the overall technique, then I proceeded to iteratively break the problem into successively smaller chunks. A bit like taking apart a matryoshka doll. Or maybe a more apt analogy would be: peeling away the layers of a rotten onion only to find a miniscule, barely salvageable core, calling into question the cost/benefit of the whole excavation. Moshe was right. With that said—and unlike the eponymous biographee of the aforementioned book—I think I can at least claim that my ideas are fully “born” in the first volume.

Despite somehow managing to get that chapter of my thesis published in a book, I feel like it always suffered from my cumbersome presentation. Therefore, perhaps inspired by Stetson hats and hip flasks, I have since devised an analogy that I hope at least makes the problem (if not my solution) more accessible. That’s what I am going to describe in the remainder of this post.

Consider, for a moment, that you are piloting a car in a huge bumper car arena.

CC BY 2.0, adapted from here

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 challenge 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?

The naïve solution is to simply yell out, “Who has the time‽” The problems with this solution 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? Bumper car arenas tend to be loud.

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 who 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 and/or reads English?

My realization is that: If one roughly knows the topology of the network (i.e., the locations of all of the cars), and if the messages are truly passed randomly through the network, one can use ergodic theory and random graph theory to accurately predict the frequency of message arrivals. Assuming knowledge of the network topology is reasonable, since many ad hoc networking algorithms already provide it. Even if it is not available, an approximation of the topological properties is often sufficient. So, what this provides is a model for predicting how long it will take for one’s message to eventually reach someone with a watch and, subsequently, how long it will take for the response to be returned. What I discovered was that the variance is often small enough such that this estimate can be used to correctly adjust for the delay in returning the time. Furthermore, this model provides a probability distribution for how likely it is that one would have received at least one response as a function of waiting time. Therefore, if n seconds have passed and the model says that with probability 0.99 one should have received a response to the time query, yet no response has been received, one can conclude with 99% certainty that there is no one in the network with a watch!

The last challenge question, “What if not everyone speaks and/or reads English?” will have to wait for another post…