RAMBO: A Reconfigurable Atomic Memory Service

N. Lynch and A.A. Shvartsman

Abstract
This paper presents an algorithm that emulates atomic read/write shared objects in a dynamic network setting. To ensure availability and fault-tolerance, the objects are replicated. To ensure atomicity, reads and writes are performed using quorum configurations, each of which consists of a set of members plus sets of read-quorums and write-quorums. The algorithm is reconfigurable: the quorum configurations may change during computation, and such changes do not cause violations of atomicity. Any quorum configuration may be installed at any time. The algorithm tolerates processor stopping failure and message loss. The algorithm performs three major tasks, all concurrently: reading and writing objects, introducing new configurations, and garbage-collecting obsolete configurations. The algorithm guarantees atomicity for arbitrary patterns of asynchrony and failure. The algorithm satisfies a variety of conditional performance properties, based on timing and failure assumptions. In the normal case, the latency of read and write operations is at most 8d, where d is the maximum message delay.

Failure-Sensitive Analysis of Parallel Algorithms with Controlled Memory Access Concurrency

Ch. Georgiou, A. Russell and A.A. Shvartsman

Abstract
This work considers the problem of performing a set of N tasks on a set of P cooperating message-passing processors (P ≤ N). The processors use a group communication service (GCS) to coordinate their activity in the setting where dynamic changes in the underlying network topology cause the processor groups to change over time. GCSs have been recognized as effective building blocks for fault-tolerant applications in such settings. Our results explore the efficiency of fault-tolerant cooperative computation using GCSs. The original investigation of this area by (Dolev et al., Dynamic load balancing with group communication, in: Proc. of the 6th International Colloquium on Structural Information and Communication Complexity, 1999) focused on competitive lower bounds, non-redundant task allocation schemes and work-efficient algorithms in the presence of fragmentation regroupings. In this work we investigate work-efficient and message-efficient algorithms for fragmentation and merge regroupings. We present an algorithm that uses GCSs and implements a coordinator-based strategy. For the analysis of our algorithm we introduce the notion of view-graphs that represent the partially-ordered view evolution history witnessed by the processors. For fragmentations and merges, the work of the algorithm (defined as the worst case total number of task executions counting multiplicities) is not more than min{N ċ f + N, N ċ P}, and the message complexity is no worse than 4(N ċ f + N + P ċ m), where f and m denote the number of new groups created by fragmentations and merges, respectively. Note that the constants are very small and that, interestingly, while the work efficiency depends on the number of groups f created as the result of fragmentations, work does not depend on the number of groups m created as the result of merges.

Establishing Wireless Conference Calls Under Delay Constraints

A. Bar-Noy and G. Malewicz

Abstract
A prevailing feature of mobile telephony systems is that the cell where a mobile user is located may be unknown. Therefore when the system is to establish a call between users it may need to search, or page, all the cells that it suspects the users are located in, to find the cells where the users currently reside. The search consumes expensive wireless links and so it is desirable to develop search techniques that page as few cells as possible.
We consider cellular systems with c cells and m mobile users roaming among the cells. The location of the users
is uncertain as given by probability distribution vectors. Whenever the system needs to find specific users, it conducts
a search operation lasting some number of rounds (the delay constraint). In each round the system may check an arbitrary subset of cells to see which users are located there. In this setting the problem of finding one user with minimum expected number of cells searched is known to be solved optimally in polynomial time.
In this paper we address the problem of finding several users with the same optimization goal. This task is motivated
by the problem of establishing a conference call between mobile users. We first show that the problem is NPhard.
Then we prove that a natural and simple heuristic is a e/e−1 approximation solution.

Optimally Work-Competitive Scheduling for Cooperative Computing with Merging Groups

Ch. Georgiou, A. Russell and A.A. Shvartsman

Abstract
The problem of cooperatively performing a set of N tasks in a decentralized setting where the computing medium is subject to failures is one of the fundamental problems in distributed computing.  The setting with partitionable networks is especially challenging. This is because no amount of algorithmic sophistication can compensate for the possibility of groups of processors or even individual processors becoming disconnected during the computation. In general, an adversary that is able to partition the network into g components will cause any task-performing algorithm to have work Ω(N·g) even if each group of processors performs no more than the optimal number of Θ(N) tasks.

Given the pessimistic lower bounds, and inorder to understand better the practical implications of performingwork in partitionable settings, and especially in the settings where initiallythere may be several disconnected groups, we study distributed work-schedulingand pursue competitive analysis of algorithms. This paper presentsthe following. (1) A formalization of an adversary model that forces processorsto start in isolation and be subjected to a pattern of merges. (2) Lower bounds on competitiveness showing that any α-competitive deterministicor randomized algorithm has α > ; 1 + 1/e. (3) A natural and practical randomizedalgorithm, achieving  the optimal competitive ratio of (1+1/e). We also consider feasible implementations of the algorithm using group communication services. 

An Inheritance-Based Technique for Building Simulation Proofs Incrementally

I. Keidar, R. Khazan, N. Lynch and A.A Shvartsman

Abstract
This paper presents a technique for incrementally constructing safety specifications, abstract algorithm descriptions, and simulation proofs showing that algorithms meet their specifications.

The technique for building specifications (and algorithms) allows a child specification (or algorithm) to inherit from its parent by two forms of incremental modification: (a) interface extension, where new forms of interaction are added to the parent's interface, and (b) specialization (subtyping), where new data, restrictions, and effects are added to the parent's behavior description. The combination of interface extension and specialization constitutes a powerful and expressive incremental modification mechanism for describing changes that do not override the behavior of the parent, although it may introduce new behavior.

Consider the case when incremental modification is applied to both a parent specification S and a parent algorithm A. A proof that the child algorithm A' implements the child specification S' can be built incrementally upon a simulation proof that algorithm A implements specification S. The new work required involves reasoning about the modifications, but does not require repetition of the reasoning in the original simulation proof.

The paper presents the technique mathematically, in terms of automata. The technique has already been used to model and validate a full-fledged group communication system (see [Keidar and Khazan,2000]); the methodology and results of that experiment are summarized in this paper.