Linearizability is a well-known consistency condition for shared objects in concurrent systems. We focus on the problem of implementing linearizable objects of arbitrary data types in message-passing systems with bounded, but uncertain, message delay and bounded, but non-zero, clock skew. We present an algorithm that exploits axiomatic properties of different operations to reduce the running time of each operation below that obtainable with previously known algorithms. We also prove lower bounds on the time complexity of various kinds of operations, specified by the axioms they satisfy, resulting in reduced gaps in some cases and tight bounds in others.

Dynamic distributed systems allow processes to join and leave the system, so the number of processes participating in a computation varies over time. Examples of dynamic distributed systems include peer-to-peer networks, sensor networks, mobile ad-hoc networks, and many more. A fundamental problem in any distributed system is to find consensus among the processes on a common input value. For dynamic distributed systems, it is not entirely clear how the problem should be formulated, as processes can join and leave before consensus is reached. We formulate and solve a strong version of the consensus problem in dynamic distributed systems in the presence of Byzantine faulty processes. We show that one cannot improve upon our algorithm in terms of the bound on the number of processes. For stochastic dynamic distributed systems, we determine the probability that a set of processes can reach strong consensus.

Shared objects are a key component in today's large distributed systems. Linearizability is a popular consistency condition for such shared objects which gives the illusion of sequential execution of operations. The time bound of an operation is the worst-case time complexity from the operation invocation to its response. Some time bounds have been proved for certain operations on linearizable shared objects in partially synchronous systems but there are some gaps between time upper bound and lower bound for each operation. In this work, the goal is to narrow or eliminate the gaps and find optimally fast implementations.\n\nTo reach this goal, we prove larger lower bounds and show smaller upper bounds (compared to 2d for all operations in previous folklore implementations) by proposing an implementation for a shared object with an arbitrary data type in distributed systems of n processes in which every message delay is bounded within [d-u, d] and the maximum skew between processes' clocks is epsilon.\n\nConsidering any operation for which there exist two instances such that individually, each instance is legal but in sequence they are not, we prove a lower bound of d + min{epsilon, u, d/3}, improving from d, and show this bound is tight when epsilon < d/3 and epsilon < u.\n\nConsidering any operation for which there exist k instances such that each instance separately is legal and any sequence of them is legal, but the state of the object is different after different sequences, we prove a lower bound of (1-1/k)u, improving from u/2, and show this bound is tight when k = n.\n\nA pure mutator only modifies the object but does not return anything about the object. A pure accessor does not modify the object. For a pure mutator OP1 and a pure accessor OP2, if given a set of instances of OP1, the state of the object reflects the order in which the instances occur and an instance of OP2 can detect whether an instance of OP1 occurs, we prove the sum of the time bound for OP1 and OP2 is at least d + min{epsilon, u, d/3}, improving from d. The upper bound is d + 2*epsilon from our implementation.

Regularity is a shared memory consistency condition that has received considerable attention. Lamport's original definition of regularity assumed a single-writer model, however, and is not well defined when the shared register may have multiple writers. In this paper, we consider four possible definitions of multiwriter regularity. The definitions are motivated by variations on a quorum-based algorithm schema for implementing them. We study the relationships between these definitions and a number of other well-known consistency conditions, and we give a partial order describing the relative strengths of these consistency conditions. Finally, we provide a practical context for our results by studying the correctness of two well-known algorithms for mutual exclusion under each of our proposed consistency conditions.

The genetic algorithm (GA) paradigm is a well-known heuristic for solving many problems in science and engineering. As problem sizes increase, a natural question is how to exploit advances in distributed and parallel computing to speed up the execution of GAs. This paper proposes a new distributed architecture for GAs, based on distributed storage of the individuals in a persistent pool. Processors extract individuals from the pool in order to perform the computations and then insert the resulting individuals back into the pool. Unlike previously proposed approaches, the new approach is tailored for distributed systems in which processors are loosely coupled, failure-prone and can run at different speeds. Proof-of-concept simulation results are presented indicating that the approach can deliver improved performance due to the distribution and tolerates a large fraction of crash failures.

Distributed storage systems have become popular for handling the enormous amounts of data in network-centric systems. A distributed storage system provides client processes with the abstraction of a shared variable that satisfies some consistency and reliability properties. Typically the properties are ensured through a replication-based implementation. This paper presents an algorithm for a replicated read-write register that can tolerate Byzantine failures of some of the replica servers. The targeted consistency condition is a version of regularity that supports multiple writers. Although regularity is weaker than the more frequently supported condition of atomicity, it is still strong enough to be useful in some important applications. By weakening the consistency condition, the algorithm can support multiple writers more efficiently than the known multi-writer algorithms for atomic consistency.

We propose a generic algorithmic model called STAMP (Synchronous, Transactional, and Asynchronous Multi- Processing) as a universal performance and power complexity model for multithreaded algorithms and systems. We provide examples to illustrate how to design and analyze algorithms using STAMP and how to apply the complexity estimates to better utilize CMP(Chip MultiProcessor)-based machines within given constraints such as power.

No abstract available.

We propose a generic algorithmic model called STAMP(synchronous, transactional, and asynchronous multi-processing) as a universal performance and power complexity model for multithreaded algorithms and systems. We provide examples to illustrate how to design and analyze algorithms using STAMP and how to apply the complexity estimates to better utilize CMP(chip multiprocessor)-based machines within given constraints such as power.

No abstract available.

An important property in a sensor network is the mon- itoring of temporal changes of hazardous situations such as forest fires. Rescue groups need to be aware of dy- namic changes that affect their rescue efforts. In this paper, we discuss a sensor network model that provides a good abstraction of geometric and topological fea- tures of a dynamically changing sensing environment. This model enables efficient path planning and naviga- tion using localized algorithms. We propose a dynamic medial axis model that represents shapes and changes of shapes in a geometric space. We develop distributed algorithms to capture the dynamic network topologies. Dynamic medial axis allows rescue teams to find a short path to safety in a changing environment. We show that our dynamic medial axis algorithms provide good ap- proximations to the true medial axis and our routing scheme generates short and safe routes. The simula- tion results show that the routes found by our scheme are near-optimal.

This paper proposes an energy efficient protocol for sensor data management. The protocol employs replicated data sinks to achieve (1) resiliency to data sink failure, and (2) efficiency in storing and retrieving sensor data. A simple address assignment scheme is introduced that partitions the sensor field into cells, where each cell contains one data sink and all sensors that are closest to this data sink. It is shown that this scheme is scalable and resilient against data sink and sensor node failures. Furthermore, the scheme has a reasonably low message complexity and a high energy efficiency

Presents a definition of a read-write register that sometimes returns out-of-date values, shows that the definition is implemented by the probabilistic quorum algorithm of D. Malkhi et al. (1997), and shows how to program with such registers using the framework of A. U/spl uml/resin and M. Dubois (1990). Consequently, existing iterative algorithms for an interesting class of problems (including finding shortest paths, constraint satisfaction and transitive closure) converge with high probability if executed in a system in which the shared data is implemented with registers satisfying the new definition. Furthermore, the algorithms in this framework inherit positive attributes concerning load and availability from the underlying register implementation. A monotone version of the new register definition is specified and implemented; it can provide improved expected convergence time and message complexity for iterative algorithms.

This paper presents a specification of a randomized shared queue that can lose some elements or return them out of order (not in FIFO), shows that the specification can be implemented over the probabilistic quorum algorithm of [4, 3], and analyzes the behavior of this implementation. Distributed algorithms that can tolerate some lost and out-of-order messages are candidates for replacing the message queues with random queues. The modified algorithms will inherit positive attributes concerning load and availability from the underlying queue implementation. The behavior of an application — a class of combinatorial optimization algorithms — when it is implemented using random queues is analyzed.

This paper presents a definition of a randomized regular register, shows that the definition is implemented by the probabilistic quorum algorithm of [3], and shows how to program with such registers using the framework of [4]. Consequently, existing iterative algorithms for a large class of problems (including solving systems of linear equations, finding shortest paths, etc.) will converge with high probability if executed in a system in which the shared data is implemented with registers satisfying the new condition. A modified definition is presented and its expected time for convergence is calculated and compared experimentally with that for the original definition.