The Virtual Infrastructure Project Theory of Distributed Systems Group Computer Science and Artificial Intelligence Laboratory

Virtual Mobile Nodes

We propose designing distributed algorithms to run on virtual mobile nodes (VMNs), abstract nodes that move in a predetermined, predictable manner. In this new abstraction, VMNs are simulated by real nodes in the network. The motion of a VMN is determined in advance, and is known to the programs executing on the VMNs. For example, a VMN may traverse the plane in a regular pattern, or it may perform a pseudorandom walk. We allow the motion of the virtual nodes to be uncorrelated with the motion of the real nodes: even if all the real nodes are going in one direction, the virtual nodes are able to travel in the opposite direction. Consider, for example, an application to monitor traffic on a highway: even though all the cars are moving in one direction, a VMN could move in the opposite direction, notifying oncoming cars of the traffic ahead.

We present the Mobile Point algorithm, a new algorithm that implements robust virtual mobile nodes, thus demonstrating the feasibility of our approach. The main idea of the algorithm is to allow real nodes traveling near the location of a virtual node to emulate that VMN. In order to achieve robustness, the algorithm replicates the state of a virtual node at a number of real mobile nodes. As the execution proceeds, the algorithm continually modifies the set of replicas for each mobile node so that the replicas always remain near the desired path of the virtual node. We use a replicated state machine approach, augmented to support joins, leaves, and recovery, to maintain the consistency of the replicas.

A virtual node is prone to "crash-reboot" failures. As long as the path of the virtual node travels through dense areas of the network, the virtual node does not fail. If however, the VMN is directed to an empty spot, a failure may occur. The Mobile Point algorithm, however, allows the VMN to recover to an initial state, if it again reenters a dense area. In this way, the VMN abstraction takes advantage of dense regions of the network to perform arbitrary computation.

To summarize, this research contains three main contributions. First, we define the VMN abstraction. Second, we present selected algorithms based on VMNs that are quite simple compared to previous algorithms. Third, we present an algorithm to implement robust virtual mobile nodes.