A simple proof technique for priority-scheduled systems

A simple proof method is presented for proving invariance properties of concurrent programs in priority-scheduled systems. This method is illustrated by using it to establish the correctness of a simple wait-free consensus algorithm for priority-scheduled uniprocessor systems. This consensus algorithm is of interest in its own right because is shows that atomic read and write operations are universal in priority-scheduled uniprocessor systems, i.e., they can be used to implement any shared object in such a system in a wait-free manner. This stands in contrast to fully asynchronous systems, where strong synchronization primitives such as compare-and-swap are needed for universality.     

Anonymous and fault-tolerant shared-memory computing

The vast majority of papers on distributed computing assume that processes are assigned unique identifiers before computation begins. But is this assumption necessary? What if processes do not have unique identifiers or do not wish to divulge them for reasons of privacy? We consider asynchronous shared-memory systems that are anonymous. The shared memory contains only the most common type of shared objects, read/write registers. We investigate, for the first time, what can be implemented deterministically in this model when processes can fail. We give anonymous algorithms for some fundamental problems: time-stamping, snapshots and consensus. Our solutions to the first two are wait-free and the third is obstruction-free. We also show that a shared object has an obstruction-free implementation if and only if it satisfies a simple property called idempotence. To prove the sufficiency of this condition, we give a universal construction that implements any idempotent object.     

Sharing Memory between Byzantine Processes Using Policy-Enforced Tuple Spaces

Despite the large amount of Byzantine fault-tolerant algorithms for message-passing systems designed through the years, only recently algorithms for the coordination of processes subject to Byzantine failures using shared memory have appeared. This paper presents a new computing model in which shared memory objects are protected by fine-grained access policies, and a new shared memory object, the Policy-Enforced Augmented Tuple Space (PEATS). We show the benefits of this model by providing simple and efficient consensus algorithms. These algorithms are much simpler and requires less shared memory operations, using also less memory bits than previous algorithms based on ACLs and sticky bits. We also prove that PEATS objects are universal, i.e., that they can be used to implement any other shared memory object, and present lock-free and wait-free universal constructions.     

Randomized naming using wait-free shared variables

A naming protocol assigns unique names (keys) to every process out of a set of communicating processes. We construct a randomized wait-free naming protocol using wait-free atomic read/write registers (shared variables) as process intercommunication primitives. Each process has its own private register and can read all others. The addresses/names each one uses for the others are possibly different: Processes p and q address the register of process r in a way not known to each other. For processes and , the protocol uses a name space of size and running time (read/writes to shared bits) with probability at least , and overall expected running time. The protocol is based on the wait-free implementation of a novel -Test&SetOnce object that randomly and fast selects a winner from a set of q contenders with probability at least in the face of the strongest possible adaptive adversary. Received: September 1994 / Accepted: January 1998     

Universal constructions for large objects

We present lock-free and wait-free universal constructions for implementing large shared objects. Most previous universal constructions require processes to copy the entire object state, which is impractical for large objects. Previous attempts to address this problem require programmers to explicitly fragment large objects into smaller, more manageable pieces, paying particular attention to how such pieces are copied. In contrast, our constructions are designed to largely shield programmers from this fragmentation. Furthermore, for many objects, our constructions result in lower copying overhead than previous ones. Fragmentation is achieved in our constructions through the use of load-linked, store-conditional, and validate operations on a “large” multiword shared variable. Before presenting our constructions, we show how these operations can be efficiently implemented from similar one-word primitives     

On the inherent weakness of conditional primitives

Some well-known primitive operations, such as compare-and-swap, can be used, together with read and write, to implement any object in a wait-free manner. However, this paper shows that, for a large class of objects, including counters, queues, stacks, and single-writer snapshots, wait-free implementations using only these primitive operations and a large class of other primitive operations cannot be space efficient: the number of base objects required is at least linear in the number of processes that share the implemented object. The same lower bounds are obtained for implementations of starvation-free mutual exclusion using only primitive operations from this class. For wait-free implementations of a closely related class of one-time objects, lower bounds on the tradeoff between time and space are presented.     

Laziness pays! Using lazy synchronization mechanisms to improve non-blocking constructions

Summary. We present a simple and efficient wait-free implementation of Lazy Large Load-Linked/Store-Conditional (Lazy-LL/SC), which can be used to atomically modify a dynamically-determined set of shared variables in a lock-free manner. The semantics of Lazy-LL/SC is weaker than that of similar objects used by us previously to design lock-free and wait-free constructions, and as a result can be implemented more efficiently. However, we show that Lazy-LL/SC is strong enough to be used in existing non-blocking universal constructions and to build new ones. Received: December 2000 / Accepted: September 2001     

Common2 extended to stacks and unbounded concurrency

This paper extends Common2, the family of objects that implement and are wait-free implementable from 2 consensus objects, in two ways: First, the stack object is shown to be in the family, refuting a conjecture to the contrary [6]. Second, Common2 is investigated in the unbounded concurrency model, whereas until now it was considered only in an n-process model. We show that the fetch-and-add, test-and-set , and stack objects are in Common2 even with respect to this stronger notion of wait-free implementation. Our constructions rely on a wait-free implementation of immediate snapshots in the unbounded concurrency model, which was previously not known to be possible. The introduction of unbounded concurrency to the study of Common2 opens several directions of research: are there objects that have n-process implementations but are not unbounded concurrency implementable? We conjecture that swap is such an object. Additionally, the hope is that a queue impossibility proof, which eludes us in the n-process model, will be easier to establish in the unbounded concurrency model.     

Using local-spin k-exclusion algorithms to improve wait-free object implementations

Summary.  We present the first shared-memory algorithms for k-exclusion in which all process blocking is achieved through the use of “local-spin” busy waiting. Such algorithms are designed to reduce interconnect traffic, which is important for good performance. Our k-exclusion algorithms are starvation-free, and are designed to be fast in the absence of contention, and to exhibit scalable performance as contention rises. In contrast, all previous starvation-free k-exclusion algorithms require unrealistic operations or generate excessive interconnect traffic under contention. We also show that efficient, starvation-free k-exclusion algorithms can be used to reduce the time and space overhead associated with existing wait-free shared object implementations, while still providing some resilience to delays and failures. The resulting “hybrid” object implementations combine the advantages of local-spin spin locks, which perform well in the absence of process delays (caused, for example, by preemptions), and wait-free algorithms, which effectively tolerate such delays. We present performance results that confirm that this k-exclusion-based technique can improve the performance of existing wait-free shared object implementations. These results also show that lock-based implementations can be susceptible to severe performance degradation under multiprogramming, while our hybrid implementations are not. Received: December 1995 / Accepted: February 1997     

Multi-writer composite registers

Summary Acomposite register is an array-like shared data object that is partitioned into a number of components. An operation of such a register either writes a value to a single component, or reads the values of all components. A composite register reduces to an ordinary atomic register when there is only one component. In this paper, we show that a composite register with multiple writers per component can be implemented in a wait-free manner from a composite register with a single writer per component. It has been previously shown that registers of the latter kind can be implemented from atomic registers without waiting. Thus, our results establish that any composite register can be implemented in a wait-free manner from atomic registers. We show that our construction has comparable space compexity and better time complexity than other constructions that have been presented in the literature. James H. Anderson received the B.S. degree in Computer Science from Michigan State University in 1982, the M.S. degree in Computer Science from Purdue University in 1983, and the Ph.D. degree in Computer Sciences from the University of Texas at Austin in 1990. He recently joined the Computer Science Department at the University of North Carolina at Chapel Hill, where he is now an Assistant Professor. Prior to joining the University of North Carolina, he was an Assistant Professor of Computer Science for three years at the University of Maryland at College Park. Professor Anderson's main research interests are within the area of concurrent and distributed computing. His current interests primarily involve the implementation of resilient and scalable synchronization mechanisms.Preliminary version was presented at the Ninth Annual ACM Symposium on Principles of Distributed Computing [2]Much of the work described herein was completed while the author was with the University of Texas at Austin and the University of Maryland at College Park. This work was supported at the University of Texas by ONR Contract N00014-89-J-1913, and at the University of Maryland by NSF Contract CCR 9109497 and by an award from the University of Maryland General Research Board     

Byzantine disk paxos: optimal resilience with byzantine shared memory

We present Byzantine Disk Paxos, an asynchronous shared-memory consensus algorithm that uses a collection of n < 3t disks, t of which may fail by becoming non-responsive or arbitrarily corrupted. We give two constructions of this algorithm; that is, we construct two different t-tolerant (i.e., tolerating up to t disk failures) building blocks, each of which can be used, along with a leader oracle, to solve consensus. One building block is a t-tolerant wait-free shared safe register. The second building block is a t-tolerant regular register that satisfies a weaker termination (liveness) condition than wait freedom: its write operations are wait-free, whereas its read operations are guaranteed to return only in executions with a finite number of writes. We call this termination condition finite writes (FW), and show that wait-free consensus is solvable with FW-terminating registers and a leader oracle. We construct each of these t-tolerant registers from n < 3t base registers, t of which can be non-responsive or Byzantine. All the previous t-tolerant wait-free constructions in this model used at least 4t + 1 fault-prone registers, and we are not familiar with any prior FW-terminating constructions in this model. We further show tight lower bounds on the number of invocation rounds required for optimal resilience reliable register constructions, or more generally, constructions that use less than 4t + 1 fault-prone registers. Our lower bounds show that such constructions are inherently more costly than constructions that use 4t + 1 registers, and that our constructions have optimal round complexity. Furthermore, our wait-free construction is early-stopping, and it achieves the optimal round complexity with any number of actual failures. A preliminary version of this paper, by the same authors and with the same title, appears in Proceedings of the 23rd ACM Symposium on Principles of Distributed Computing (PODC ’04), July 2004, pages 226–235.     

Continuous k-Means Monitoring over Moving Objects

Given a dataset P, a k-means query returns k points in space (called centers), such that the average squared distance between each point in P and its nearest center is minimized. Since this problem is NP-hard, several approximate algorithms have been proposed and used in practice. In this paper, we study continuous k-means computation at a server that monitors a set of moving objects. Re-evaluating k-means every time there is an object update imposes a heavy burden on the server (for computing the centers from scratch) and the clients (for continuously sending location updates). We overcome these problems with a novel approach that significantly reduces the computation and communication costs, while guaranteeing that the quality of the solution, with respect to the re-evaluation approach, is bounded by a user-defined tolerance. The proposed method assigns each moving object a threshold (i.e., range) such that the object sends a location update only when it crosses the range boundary. First, we develop an efficient technique for maintaining the k-means. Then, we present mathematical formulae and algorithms for deriving the individual thresholds. Finally, we justify our performance claims with extensive experiments.     

Optimizing the topological and combinatorial complexity of isosurfaces

Since the publication of the original Marching Cubes algorithm, numerous variations have been proposed for guaranteeing water-tight constructions of triangulated approximations of isosurfaces. Most approaches divide the 3D space into cubes that each occupy the space between eight neighboring samples of a regular lattice. The portion of the isosurface inside a cube may be computed independently of what happens in the other cubes, provided that the constructions for each pair of neighboring cubes agree along their common face. The portion of the isosurface associated with a cube may consist of one or more connected components, which we call sheets. The topology and combinatorial complexity of the isosurface is influenced by three types of decisions made during its construction: (1) how to connect the four intersection points on each ambiguous face, (2) how to form interpolating sheets for cubes with more than one loop, and (3) how to triangulate each sheet. To determine topological properties, it is only relevant whether the samples are inside or outside the object, and not their precise value, if there is one. Previously reported techniques make these decisions based on local—per cube—criteria, often using precomputed look-up tables or simple construction rules. Instead, we propose global strategies for optimizing several topological and combinatorial measures of the isosurfaces: triangle count, genus, and number of shells. We describe efficient implementations of these optimizations and the auxiliary data structures developed to support them.     

On space-optimality of buffer-based conflict-free constructions of 1-writer 1-reader multivalued atomic variables from safe bits

A shared variable construction is called buffer-based if the values of the variable are stored in buffers that are different from control storage. Each buffer stores only a single value from the domain of the variable. A buffer-based construction is conflict-free if, in each execution of the shared variable, no reading of any buffer overlaps with any writing of that buffer. This paper studies shared space requirements for wait-free, conflict-free, deterministic constructions of 1-writer 1-reader multivalued atomic variables from safe variables. That four buffers are necessary and sufficient for such constructions has been established in the literature. This paper establishes the requirement for control storage. The least shared space for such a construction in the literature is (four safe buffers and) four safe control bits. We show that four safe control bits are necessary for such constructions when the reader is restricted to read at most one buffer in each read operation.     

An impossibility about failure detectors in the iterated immediate snapshot model

The Iterated Immediate Snapshot model (IIS) is an asynchronous computation model where processes communicate through a sequence of one-shot Immediate Snapshot (IS) objects. It is known that this model is equivalent to the usual asynchronous read/write shared memory model, for wait-free task solvability. Its interest lies in the fact that its runs are more structured and easier to analyze than the runs in the shared memory model. As the IIS model and the shared memory model are equivalent for wait-free task solvability, a natural question is the following: Are they still equivalent for wait-free task solvability, when they are enriched with the same failure detector? The paper shows that the answer to this question is “no”.     

Using wait-free synchronization in the design of distributed applications

Wait-free synchronization has been recognized in the literature as an effective concurrent programming technique. The concurrent programming community, however, has been slow to adopt this technique. This paper addresses the practical application of wait-free synchronization in the design of distributed applications. In this paper, we present an implementation of a server that uses wait-free synchronization. The resulting code is more easily seen to be fault tolerant. The performance analysis of the wait-free synchronization server outperformed a server that uses traditional locking techniques. This practical demonstration of the benefits of wait-free synchronization should help foster its adoption in the development of distributed applications.     

The complexity of updating snapshot objects

This paper proves Ω(m) lower bounds on the step complexity of UPDATE operations for space-optimal wait-free implementations of an m-component snapshot object from historyless objects. These lower bounds follow from lower bounds for a new, more general class of implementations from base objects of any type. This work extends a similar lower bound by Israeli and Shirazi for implementations of m-component single-writer snapshot objects from single-writer registers.     

Simple extensions of 1-writer atomic variable constructions to multiwriter ones

We present several simple wait-free constructions of multiwriter multireader multivalued atomic shared variables. These are extensions of two 1-writer constructions in the literature and use a multiwriter multireader fixed-valued atomic variable. All the constructions are intuitive, and their correctness proofs are short and easy to follow. Some constructions are conflictfree, that is, in each execution, no reading of a buffer overlaps with any writing of that buffer. All the conflict-free constructions have the property that there is only one reading of a buffer in a read execution. Some of them have the additional property that there is only one writing of a 1-reader buffer, for each reader, in a write execution.     

Gröbner fan and universal characteristic sets of prime differential ideals

The concepts of Gröbner cone, Gröbner fan, and universal Gröbner basis are generalized to the case of characteristic sets of prime differential ideals. It is shown that for each cone there exists a set of polynomials which is characteristic for every ranking from this cone; this set is called a strong characteristic set, and an algorithm for its construction is given. Next, it is shown that the set of all differential Gröbner cones is finite for any differential ideal. A subset of the ideal is called its universal characteristic set, if it contains a characteristic set of the ideal w.r.t. any ranking. It is shown that every prime differential ideal has a finite universal characteristic set, and an algorithm for its construction is given. The question of minimality of this set is addressed in an example. The example also suggests that construction of a universal characteristic set can help in solving a system of nonlinear PDE’s, as well as maybe providing a means for more efficient parallel computation of characteristic sets.