Developing a Consistent Domain-Oriented Distributed Object Service.

C. Georgiou, P.M. Musial, and A.A. Shvartsman.

Abstract
This paper presents a new algorithm for a reconfigurable distributed domain-oriented atomic object service, called DO-RAMBO, which stands for Domain-Oriented Reconfigurable Atomic Memory for Basic Objects. The new implementation substantially extends the abstract RAMBO, algorithm for individual atomic reconfigurable objects developed by Lynch and Shvartsman. Domains are introduced to allow the users to group related atomic objects. The implementation manages configurations on the basis of domains, which significantly improves the utility and the performance of the resulting service. DO-RAMBO, guarantees consistency under asynchrony, message loss, node crashes, new node arrivals, and node departures. Input/Output Automata are used to specify the algorithms and show correctness. A complete implementation of the DO-RAMBO, service was developed on a network of workstations. The software is engineered under a methodology where formal algorithm design is followed by a disciplined translation of the abstract algorithm specification to distributed Java code. This substantially reduces the human error associated with informal mapping of high-level specifications to detailed design, and with the intuitive design interpretation when producing running code. The extended abstract presents the formal algorithm development for DO-RAMBO, and includes analytical and preliminary empirical results that illustrate the advantages of the new algorithm.

Reconfigurable Distributed Storage for Dynamic Networks.

G. Chockler, S. Gilbert, V.C. Gramoli, P.M. Musial, and A.A. Shvartsman.

Abstract
This paper presents a new algorithm for implementing a reconfigurable distributed shared memory in an asynchronous dynamic network. The algorithm guarantees atomic consistency (linearizability) in all executions in the presence of arbitrary crash failures of processors and message loss and delays. The algorithm incorporates a classic quorum-based read/write algorithm and an optimized consensus protocol, based on Paxos, and achieves the design goals of: (i) allowing read and write operations to complete rapidly, as in the basic read/write protocol that can tolerate crash failures and asynchrony, and (ii) providing long-term fault tolerance through reconfiguration, a process that evolves the quorum configurations used by the read and write operations. The resulting algorithm is fault tolerant, using replication to ensure that data can survive node failures, and reconfigurable, tolerating continuous changed in the set of participating processors. The new algorithm improves on previously developed alternatives by using a more efficient reconfiguration protocol, thus guaranteeing better fault tolerance and faster recovery from network instability. This paper presents the new algorithm, a formal proof of correctness, and conditional performance analysis.

Improved algorithms for multiplex PCR primer set selection with amplification length constraints.

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

Abstract
Numerous high-throughput genomics assays require the amplification of a large number of genomic
loci of interest. Amplification is cost-effectively achieved using several short single-stranded DNA
sequences called primers and polymerase enzyme in a reaction called multiplex polymerase chain reaction
(MP-PCR). Amplification of each locus requires that two of the primers bind to the forward
and reverse DNA strands flanking the locus. Since the efficiency of PCR amplification falls off exponentially
as the length of the amplification product increases, an important practical requirement is
that the distance between the binding sites of the two primers should not exceed a certain threshold.
In this paper we study MP-PCR primer set selection with amplification length constraints from both
theoretical and practical perspectives. Our contributions include an improved analysis of a simple yet
effective greedy algorithm for the problem, and a comprehensive experimental study comparing our
greedy algorithm with other published heuristics on both synthetic and genomic database test cases.

Explicit Combinatorial Structures for Cooperative Distributed Algorithms.

Dariusz R. Kowalski, Peter M. Musial, Alexander A. Shvartsman

Abstract
Cooperation in distributed settings often involves activities that must be performed at least once by the participating processors. When processor failures or delays occur, it becomes unavoidable that some tasks are done redundantly. To make efficient use of the available processors, several distributed algorithms schedule the activities of the processors in terms of permutations of tasks that need to be performed at least once. This paper presents the first explicit practical deterministic construction of sets of permutations with certain combinatorial properties that immediately make practical several deterministic distributed algorithms. These algorithms solve a variety of problems, for example, cooperation in shared-memory and message-passing settings, and the gossip problem. Prior to this work, the most efficient algorithms for some of these problems were primarily of theoretical interest — they relied on permutations that are known to exist, but very expensive to construct, with the cost of construction being at least exponential in the size of the permutations. In this paper, the explicitly constructed permutations are ultimately used directly to produce practical instances of several classes of efficient deterministic algorithms. Most importantly, for all of these algorithms, the schedule construction cost is reduced from exponential to polynomial, at the expense of slight detuning, at most polylogarithmic, of the efficiency of these algorithms.

Highly Scalable Algorithms for Robust String Barcoding.

B. DasGupta, Kishori M. Konwar, Ion I. Mandoiu, Alexander A. Shvartsman

Abstract
String barcoding is a recently introduced technique for genomic
based identification of microorganisms. In this paper we describe the
engineering of highly scalable algorithms for robust string barcoding. Our
methods enable distinguisher selection based on whole genomic sequences of
hundreds of microorganisms of up to bacterial size, on a well equipped
workstation. Experimental results on both randomly generated and NCBI
genomic data show that whole-genome based selection results in a number of
distinguishers nearly matching the information theoretic lower bounds for the
problem.

Autonomous virtual mobile nodes.

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

Abstract
This paper presents a new abstraction for virtual infrastructure in mobile ad hoc networks. An Autonomous Virtual
Mobile Node (AVMN) is a robust and reliable entity that is designed to cope with the inherent di±culties caused by
processors arriving, leaving, and moving according to their own agendas, as well as with failures and energy limitations.
There are many types of applications that may make use of the AVMN infrastructure: tracking, supporting mobile
users, or searching for energy sources.
The AVMN extends the focal point abstraction in [9] and the virtual mobile node abstraction in [10]. The new abstraction
is that of a virtual general-purpose computing entity, an automaton that can make autonomous on-line decisions
concerning its own movement. We describe a selfstabilizing implementation of this new abstraction that is resilient to the chaotic behavior of the physical processors and provides automatic recovery from any corrupted state of the system.

DNA-BAR: distinguisher selection for DNA barcoding.

B. DasGupta, Kishori M. Konwar, Ion I. Mandoiu, Alexander A. Shvartsman:

Abstract
Summary: DNA-BAR is a software package for selecting DNA probes
(henceforth referred to as distinguishers) that can be used in
genomic-based identification of microorganisms. Given the genomic
sequences of the microorganisms, DNA-BAR finds a near-minimum
number of distinguishers yielding a distinct hybridization pattern for
each microorganism. Selected distinguishers satisfy user specified
bounds on length, melting temperature, and GC content, as well as
redundancy and cross-hybridization constraints.
Availability: DNA-BAR can be used online through the web interface
provided at http://dna.engr.uconn.edu/˜software/DNA-BAR/. The
open source C code, released under the GNU General Public
License, is also available at the above address.

GeoQuorums: implementing atomic memory in mobile ad hoc networks.

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

Abstract
We present a new approach, the GeoQuorums approach, for implementing atomic read/write shared memory
in mobile ad hoc networks. Our approach is based on associating abstract atomic objects with certain geographic
locations. We assume the existence of focal points, geographic areas that are normally “populated” by mobile nodes.
For example, a focal point may be a road junction, a scenic observation point, or a water resource in the desert. Mobile
nodes that happen to populate a focal point participate in implementing a shared atomic object, using a replicated state
machine approach. These objects, which we call focal point objects, are then used to implement atomic read/write
operations on a virtual shared object, using our new GeoQuorums algorithm. The GeoQuorums algorithm uses a
quorum-based strategy in which each each quorum consists of a set of focal point objects. The quorums are used to
maintain the consistency of the shared memory and to tolerate limited failures of the focal point objects, caused by
depopulation of the corresponding geographic areas. We present a mechanism for changing the set of quorums on
the fly, thus improving efficiency. Overall, the new GeoQuorums algorithm efficiently implements read and write
operations in a highly dynamic, mobile network.

Performing work with asynchronous processors: Message-delay-sensitive bounds.

Dariusz R. Kowalski, Alexander A. Shvartsman

Abstract
This paper considers the problem of performing tasks in asynchronous distributed settings. This problem, called Do-
All, has been substantially studied in synchronous models, but there is a dearth of effcient algorithms for asynchronous
message-passing processors. Do-All can be trivially solved without any communication by an algorithm where each
processor performs all tasks. Assuming p processors and t tasks, this requires work Theta(p.t). Thus it is important to
develop subquadratic solutions (when p and t are comparable) by trading computation for communication. Following
the observation that it is not possible to obtain subquadratic work when the message delay d is substantial, e.g., d = Theta(t), this work pursues a message-delay-sensitive approach. Here the upper bounds on work and communication are given as functions of p, t, and d, the upper bound on message delays, however algorithms have no knowledge of d and they cannot rely on the existence of an upper bound on d. This paper presents two families of asynchronous algorithms achieving, for the rst time, subquadratic work as long as d = o(t). The rst family uses as its basis a shared-memory algorithm without having to emulate atomic registers assumed by that algorithm. The second family uses specic permutations of tasks, with certain combinatorial properties, to sequence the work of the processors. Another important contribution in this work is the rst delay-sensitive lower bound for this problem that helps explain the behavior of our algorithms.

Work-Competitive Scheduling for Cooperative Computing with Dynamic Groups.

Chryssis Georgiou, Alexander Russell, Alexander A. Shvartsman

Abstract
The problem of cooperatively performing a set of t tasks in a decentralized computing environment subject to failures is one of the fundamental problems in distributed computing. The setting with partitionable networks is especially challenging, as algorithmic solutions must accommodate the possibility that groups of processors become disconnected (and, perhaps, reconnected) during the computation. The efficiency of task-performing algorithms is often assessed in terms of work: the total number of tasks, counting multiplicities, performed by all of the processors during the computation. In general, the scenario where the processors are partitioned into g disconnected components causes any task-performing algorithm to have work $\Omega(t\cdot g)$ even if each group of processors performs no more than the optimal number of $\Theta(t)$ tasks. Given that such pessimistic lower bounds apply to any scheduling algorithm, we pursue a competitive analysis. Specifically, this paper studies a simple randomized scheduling algorithm for p asynchronous processors, connected by a dynamically changing communication medium, to complete t known tasks. The performance of this algorithm is compared against that of an omniscient off-line algorithm with full knowledge of the future changes in the communication medium. The paper describes a notion of computation width, which associates a natural number with a history of changes in the communication medium, and shows both upper and lower bounds on work-competitiveness in terms of this quantity. Specifically, it is shown that the simple randomized algorithm obtains the competitive ratio $(1+\mathbf{cw}/e)$, where $\mathbf{cw}$ is the computation width and $e$ is the base of the natural logarithm ($e=2.7182\ldots$); this competitive ratio is then shown to be tight.

The Do-All problem with Byzantine processor failures.

Antonio Fernández, Chryssis Georgiou, Alexander Russell, Alexander A. Shvartsman

Abstract
Do-All is the abstract problem of using n processors to cooperatively perform m independent tasks in the presence of failures. This problem and its derivatives have been a centerpiece in the study of trade-offs between efficiency and fault-tolerance in cooperative computing environments. Many algorithms have been developed for Do-All in various models of computation, including message-passing, partitionable networks, and shared-memory models under a variety of failure models.

This work initiates the study of the Do-All problem for synchronous message-passing processors prone to Byzantine failures. In particular, upper and lower bounds are given on the complexity of Do-All for several cases: (a) the case where the maximum number of faulty processors f is known a priori, (b) the case where f is not known, (c) the case where a task execution can be verified (without re-executing the task), and (d) the case where task executions cannot be verified. The efficiency of algorithms is evaluated in terms of work and message complexities. The work complexity accounts for all computational steps taken by the processors and the message complexity accounts for all messages sent by the processors during the computation. The work and messages of a faulty processor are counted only until the processor fails to follow the algorithm. It is shown that in some cases obtaining work T(mn) is the best one can do. It is also shown that in certain cases communication cannot help improve work efficiency.