Virtual Mobile Nodes for Mobile Ad Hoc Networks

Shlomi Dolev, Seth Gilbert, Nancy A. Lynch, Elad Schiller, Alexander A. Shvartsman, Jennifer L. Welch

Abstract
One of the most significant challenges introduced by mobile networks is the unpredictable motion of the mobile nodes. If, instead, the mobile nodes could be programmed to move in a predictable and useful manner, the task of designing algorithms would be significantly simplified. Alas, users of mobile devices in the real world are not amenable to following instructions as to where their devices may travel. We propose executing algorithms on virtual mobile nodes that move in a predetermined, predictable, manner. We formally define the Virtual Mobile Node abstraction, and then present the Mobile Point Emulator, a new algorithm that implements robust virtual mobile nodes. We show that the Mobile Point algorithm correctly implements a virtual mobile node, and that it is robust as long as the virtual node travels through well-populated areas of the network.

The Join Problem in Dynamic Network Algorithms

Kishori M. Konwar, Dariusz R. Kowalski, Alexander A. Shvartsman

Abstract
Distributed algorithms in dynamic networks often employ communication patterns whose purpose is to disseminate information among the participants. Gossiping is one form of such communication pattern. In dynamic settings the set of participants can change substantially as new participants join, and as failures and voluntary departures remove those who have joined previously. A natural question for such settings is: how soon can newly joined nodes discover each other by means of gossiping? This paper abstracts and studies the Join Problem for dynamic systems that use all-to-all gossip. The problem is studied in terms of join-connectivity graphs where vertices represent the participants and where each edge represents one participant's knowledge about another. Ideally, such a graph has diameter one, i.e., all participants know each other. The diameter can grow as new participants join, and as failures remove edges from the graph. Gossip helps participants discover one another, decreasing the diameter. The results describe the lower and upper bounds on the number of communication rounds such that the participants who have previously joined discover one another, under a variety of assumptions about the joining and failures. For example, in the case when new participants join at multiple participants and participants may crash, the number of rounds cannot be bounded. In the more benign cases when the failures can be controlled or when new participants join at only one participant, the bound on rounds is shown to be logarithmic in the diameter of the initial configuration.

Implementing a Reconfigurable Atomic Memory Service for Dynamic Networks

Peter M. Musial, Alexander A. Shvartsman

Abstract
Transforming abstract algorithm specifications into executable code is an error-prone process in the absence of sophisticated compilers that can automatically translate such specifications into the target distributed system. This paper presents a framework that was developed for translating algorithms specified as Input/Output Automata (IOA) to distributed programs. The framework consists of a methodology that guides the software development process and a core set of functions needed in target implementations that reduce unnecessary software development. As a proof of concept, this work also presents a distributed implementation of a reconfigurable atomic memory service for dynamic networks. The service emulates atomic read/write shared objects in the dynamic setting where processors can arbitrarily crash, or join and leave the computation. The algorithm implementing the service is given in terms of IOA. The system is implemented in Java and runs on a network of workstations. Empirical data illustrates the behavior of the system.

Brief announcement: virtual mobile nodes for mobile ad hoc networks

Shlomi Dolev, Seth Gilbert, Nancy A. Lynch, Elad Schiller, Alexander A. Shvartsman, Jennifer L. Welch

Abstract
One of the most significant challenges introduced by mobile networks is the unpredictable motion of the mobile nodes. If, instead, the mobile nodes could be programmed to move in a predictable and useful manner, the task of designing algorithms would be significantly simplified. Alas, users of mobile devices in the real world are not amenable to following instructions as to where their devices may travel. We propose executing algorithms on virtual mobile nodes that move in a predetermined, predictable, manner. We formally define the Virtual Mobile Node abstraction, and then present the Mobile Point Emulator, a new algorithm that implements robust virtual mobile nodes. We show that the Mobile Point algorithm correctly implements a virtual mobile node, and that it is robust as long as the virtual node travels through well-populated areas of the network.

Long-Lived Rambo: Trading Knowledge for Communication

Chryssis Georgiou, Peter M. Musial, Alexander A. Shvartsman

Abstract
Shareable data services providing consistency guarantees, such as atomicity (linearizability), make building distributed systems easier. However, combining linearizability with efficiency in practical algorithms is difficult. A reconfigurable linearizable data service, called RAMBO, was developed by Lynch and Shvartsman. This service guarantees consistency under dynamic conditions involving asynchrony, message loss, node crashes, and new node arrivals. The specification of the original algorithm is given at an abstract level aimed at concise presentation and formal reasoning about correctness. The algorithm propagates information by means of gossip messages. If the service is in use for a long time, the size and the number of gossip messages may grow without bound. This paper presents a consistent data service for long-lived objects that improves on RAMBO in two ways: it includes an incremental communication protocol and a leave service. The new protocol takes advantage of the local knowledge, and carefully manages the size of messages by removing redundant information, while the leave service allows the nodes to leave the system gracefully. The new algorithm is formally proved correct by forward simulation using levels of abstraction. An experimental implementation of the system was developed for networks-of-workstations. The paper also includes analytical and preliminary empirical results that illustrate the advantages of the new algorithm.

Writing-all deterministically and optimally using a non-trivial number of asynchronous processors

Dariusz R. Kowalski, Alexander A. Shvartsman

Abstract
The problem of performing n tasks on p asynchronous or undependable processors is a basic problem in distributed computing. This paper considers an abstraction of this problem called Write-All : using p processors write 1’s into all locations of an array of size n. In this problem writing 1 abstracts the notion of performing a simple task. Despite substantial research, there is a dearth of efficient deterministic asynchronous algorithms for Write-All . Efficiency of algorithms is measured in terms of work that accounts for all local steps performed by the processors in solving the problem. Thus an optimal algorithm would have work Θ(n), however it is known that optimality cannot be achieved when p = Ω(n). The quest then is to obtain work-optimal solutions for this problem using a non-trivial, compared to n, number of processors p. Recently it was shown that optimality can be achieved using a non-trivial number M of processors, where M = 4
n/ log n. The new result in this paper significantly extends the range of processors for which optimality is achieved. The result shows that optimality can be achieved using close to M2 processors; more precisely, using (M logM)2−ε processors, for any ε > 0. Additionally, the new result uses only the atomic read/write memory, without resorting to using the test-and-set primitive that was necessary in the previous solution. This paper presents the algorithm and gives its analysis showing that the work complexity of the algorithm is O(n + p2+ε), which is optimal when p = O(n^(1/(2+ε))), while all prior deterministic algorithms require super-linear work when p = Ω(n1/4).

Collective asynchronous reading with polylogarithmic worst-case overhead

Bogdan S. Chlebus, Dariusz R. Kowalski, Alexander A. Shvartsman

Abstract
The Collect problem for an asynchronous shared-memory system has the objective for the processors to learn
all values of a collection of shared registers, while minimizing the total number of read and write operations. First
abstracted by Saks, Shavit, and Woll [37], Collect is among the standard problems in distributed computing. The
model consists of n asynchronous processes, each with a single-writer multi-reader register of a polynomial capacity.
The best previously known deterministic solution performs O(n3/2 log n) reads and writes, and it is due to
Ajtai, Aspnes, Dwork, and Waarts [3]. This paper presents a new deterministic algorithm that performs O(n log7 n)
read/write operations, thus substantially improving the best previous upper bound. Using an approach based on epidemic
rumor-spreading, the novelty of the new algorithm is in using a family of expander graphs and ensuring that
each of the successive groups of processes collect and propagate sufficiently many rumors to the next group. The
algorithm is adapted to the Repeatable Collect problem, which is an on-line version. The competitive latency of the
new algorithm is O(log7 n) vs. the much higher competitive latency O(pn log n) given in [3]. A result of independent
interest in this paper abstracts a gossiping game that is played on a graph and that gives its payoff in terms of
expansion.

Approximation Algorithms for Minimum PCR Primer Set Selection with Amplification Length and Uniqueness Constraints

Kishori M. Konwar, Ion I. Mandoiu, Alexander Russell, Alexander A. Shvartsman

Abstract
A critical problem in the emerging high-throughput genotyping protocols is to minimize the number of polymerase chain reaction (PCR) primers required to amplify the single nucleotide polymorphism loci of interest. In this paper we study PCR primer set selection with amplification length and uniqueness constraints from both theoretical and practical perspectives. We give a greedy algorithm that achieves a logarithmic approximation factor for the problem of minimizing the number of primers subject to a given upperbound on the length of PCR amplification products. We also give, using randomized rounding, the first non-trivial approximation algorithm for a version of the problem that requires unique amplification of each amplification target. Empirical results on randomly generated testcases as well as testcases extracted from the from the National Center for Biotechnology Information’s genomic databases show that our algorithms are highly scalable and produce better results compared to previous heuristics.

The complexity of synchronous iterative Do-All with crashes

Chryssis Georgiou, Alexander Russell, Alexander A. Shvartsman

Abstract
The ability to cooperate on common tasks in a distributed setting is key to solving a broad range of computation problems ranging from distributed search such as SETI to distributed simulation and multi-agent collaboration. Do- All, an abstraction of such cooperative activity, is the problem of performing N tasks in a distributed system of P failureprone processors. Many distributed and parallel algorithms have been developed for this problem and several algorithm simulations have been developed by iterating Do-All algorithms. The efficiency of the solutions for Do-All is measured in terms of work complexity where all processing steps taken by all processors are counted. Work is ideally expressed as a function of N, P, and f, the number of processor crashes. However the known lower bounds and the upper bounds for extant algorithms do not adequately show how work depends on f.We present the first non-trivial lower bounds for Do-All that capture the dependence of work on N, P and f. For the model of computation where processors are able to make perfect load-balancing decisions locally, we also present matching upper bounds. We define the r-iterative Do-All problem that abstracts the repeated use of Do-All such as found in typical algorithm simulations. Our f-sensitive analysis enables us to derive tight bounds for r-iterative Do-All work (that are stronger than the r-fold work complexity of a single Do-All). Our approach that models perfect load-balancing allows for the analysis of specific algorithms to be divided into two parts: (i) the analysis of the cost of tolerating failures while performing work under “free” load-balancing, and (ii) the analysis of the cost of implementing load-balancing.We demonstrate the utility and generality of this approach by improving the analysis of two known efficient algorithms.We give an improved analysis of an efficient message-passing algorithm. We also derive a tight and complete analysis of the best known Do-All algorithm for the synchronous shared-memory model. Finally we present a new upper bound on simulations of synchronous shared-memory algorithms on crash-prone processors.