An adaptive collect algorithm with applications

Summary. In a shared-memory distributed system, n independent asynchronous processes communicate by reading and writing to shared variables. An algorithm is adaptive (to total contention) if its step complexity depends only on the actual number, k, of active processes in the execution; this number is unknown in advance and may change in different executions of the algorithm. Adaptive algorithms are inherently wait-free, providing fault-tolerance in the presence of an arbitrary number of crash failures and different processes' speed. A wait-free adaptive collect algorithm with O(k) step complexity is presented, together with its applications in wait-free adaptive alg orithms for atomic snapshots, immediate snapshots and renaming. Received: August 1999 / Accepted: August 2001     

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     

On the weakest failure detector ever

Many problems in distributed computing are impossible to solve when no information about process failures is available. It is common to ask what information about failures is necessary and sufficient to circumvent some specific impossibility, e.g., consensus, atomic commit, mutual exclusion, etc. This paper asks what information about failures is necessary to circumvent any impossibility and sufficient to circumvent some impossibility. In other words, what is the minimal yet non-trivial failure information. We present an abstraction, denoted U{\Upsilon} , that provides very little information about failures. In every run of the distributed system, U{\Upsilon} eventually informs the processes that some set of processes in the system cannot be the set of correct processes in that run. Although seemingly weak, for it might provide random information for an arbitrarily long period of time, and it eventually excludes only one set of processes (among many) that is not the set of correct processes in the current run, U{\Upsilon} still captures non-trivial failure information. We show that U{\Upsilon} is sufficient to circumvent the fundamental wait-free set-agreement impossibility. While doing so, (a) we disprove previous conjectures about the weakest failure detector to solve set-agreement and (b) we prove that solving set-agreement with registers is strictly weaker than solving n + 1-process consensus using n-process consensus. We show that U{\Upsilon} is the weakest stable non-trivial failure detector: any stable failure detector that circumvents some wait-free impossibility provides at least as much information about failures as U{\Upsilon} does. Our results are generalized, from the wait-free to the f-resilient case, through an abstraction U^f{\Upsilon^f} that we introduce and prove minimal to solve any problem that cannot be solved in an f-resilient manner, and yet sufficient to solve f-resilient f-set-agreement.     

Wait-free concurrent memory management by Create and Read until Deletion (CaRuD)

Summary. The acronym CaRuD represents an interface specification and an algorithm for the management of memory shared by concurrent processes. The memory cells form a directed acyclic graph. This graph is only modified by adding a new node with a list of reachable children, and by removing unreachable nodes. If memory is not full, the algorithm ensures wait-free redistribution of free nodes. It uses atomic counters for reference counting and consensus variables to ensure exclusive access. Performance is enhanced by using nondeterminacy guided by insecure knowledge. Experiments indicate that the algorithm is very suitable for multiprocessing. Received: July 1998 / Accepted: July 2000     

The congenial talking philosophers problem in computer networks

Summary. Group mutual exclusion occurs naturally in situations where a resource can be shared by processes of the same group, but not by processes of different groups. For example, suppose data is stored in a CD-jukebox. Then when a disc is loaded for access, users that need data on the disc can concurrently access the disc, while users that need data on a different disc have to wait until the current disc is unloaded. The design issues for group mutual exclusion have been modeled as the Congenial Talking Philosophers problem, and solutions for shared-memory models have been proposed [12,14]. As in ordinary mutual exclusion and many other problems in distributed systems, however, techniques developed for shared memory do not necessary apply to message passing (and vice versa). So in this paper we investigate solutions for Congenial Talking Philosophers in computer networks where processes communicate by asynchronous message passing. We first present a solution that is a straightforward adaptation from Ricart and Agrawala's algorithm for ordinary mutual exclusion. Then we show that the simple modification suffers a severe performance degradation that could cause the system to behave as though only one process of a group can be in the critical section at a time. We then present a more efficient and highly concurrent distributed algorithm for the problem, the first such solution in computer networks. Received: August 2000 / Accepted: November 2001     

Long lived adaptive splitter and applications

Summary. Long-lived and adaptive implementations of mutual exclusion and renaming in the read/write shared memory model are presented. An implementation of a task is adaptive if the step complexity of any operation in the implementation is a function of the number of processes that take steps concurrently with the operation. The renaming algorithm assigns a new unique id in the range to any process whose initial unique name is taken from a set of size N, for an arbitrary N and where k is the number of processes that actually take steps or hold a name while the new name is being acquired. The step complexity of acquiring a new name is , while the step complexity of releasing a name is 1. The space complexity of the algorithm is where n is an upper bound on the number of processes that may be active at the same time (acquiring or holding new names), which could be N in the worst case. Both the system response time and the worst case number of operations per process in the presented mutual-exclusion algorithm are adaptive. Both algorithms rely on the basic building block of a long-lived and adaptive splitter. While the adaptive-splitter satisfies a slightly different set of properties than the Moir-Anderson splitter [MA95], it is adaptive and long-lived. In addition, the new splitter properties enable the construction of a non-blocking long-lived (2k-1)-renaming algorithm (which is optimal in the size of the new name space). We believe that the mechanisms introduced in our splitter implementation are interesting on their own, and might be used in other adaptive and long-lived constructions. Received: March 2000 / Accepted July 2001     

Implementing sequentially consistent programs on processor consistent platforms

Designers of distributed algorithms typically assume strong memory consistency guarantees, but system implementations provide weaker guarantees for better performance and scalability. This motivates the study of how to implement programs designed for sequential consistency on platforms with weaker consistency models. Typically, such implementations are impossible using only read and write operations to shared variables. One variant of processor consistency originally proposed by Goodman and called here PC-G is an exception because it provides just enough consistency to implement mutual exclusion using only reads and writes. This paper investigates the existence of compilers to convert arbitrary programs that use shared read/write variables with sequentially consistent memory semantics, to programs that use read/write variables with PC-G consistency semantics. We first provide a simple program transformation, and prove that it correctly compiles any 2-process program to a PC-G memory system, while preserving wait-freedom. We next prove that even a substantial generalization of this transformation cannot be a compiler for even a very restricted class of 3-process programs. Even though our program transformation is not a general compiler for three or more processes, it does correctly transform some specific n-process programs. In particular, for the special case of the (necessarily randomized) Test&Set algorithm of Tromp and Vitanyi, our transformation extends to any number of processes, thus providing the first algorithm for expected wait-free Test&Set on any weak memory system, using only read/write variables.     

Dynamic vp-tree indexing for n-nearest neighbor search given pair-wise distances

Abstract. For some multimedia applications, it has been found that domain objects cannot be represented as feature vectors in a multidimensional space. Instead, pair-wise distances between data objects are the only input. To support content-based retrieval, one approach maps each object to a k-dimensional (k-d) point and tries to preserve the distances among the points. Then, existing spatial access index methods such as the R-trees and KD-trees can support fast searching on the resulting k-d points. However, information loss is inevitable with such an approach since the distances between data objects can only be preserved to a certain extent. Here we investigate the use of a distance-based indexing method. In particular, we apply the vantage point tree (vp-tree) method. There are two important problems for the vp-tree method that warrant further investigation, the n-nearest neighbors search and the updating mechanisms. We study an n-nearest neighbors search algorithm for the vp-tree, which is shown by experiments to scale up well with the size of the dataset and the desired number of nearest neighbors, n. Experiments also show that the searching in the vp-tree is more efficient than that for the -tree and the M-tree. Next, we propose solutions for the update problem for the vp-tree, and show by experiments that the algorithms are efficient and effective. Finally, we investigate the problem of selecting vantage-point, propose a few alternative methods, and study their impact on the number of distance computation. Received June 9, 1998 / Accepted January 31, 2000     

Minimized embedding of arbitrary hamiltonian graphs in fault-tolerant graph and reconfiguration at faults. II. Grids and <Emphasis Type="Italic">k</Emphasis>-fault-tolerance

Optimal algorithms to construct 1-fault-tolerant structures were presented with examples of simple and diagonal grids and torus based on algorithm A2 discussed in the first part of the paper. The general procedure of constructing the k-fault-tolerant structures was presented first for a simple cycle and then for more involved grid graphs. Algorithms for reconfiguration after failure were described. For the 1-fault-tolerant structures, these algorithms are realized as a simple table of automorphisms of the fault-tolerant graph. For the case of k-fault-tolerance, correct reconfiguration requires symmetrization of the reduced graph after the ith failure by elimination of the redundant connections introduced to improve fault-tolerance from i - 1 to i when constructin the k-fault-tolerant system graph.Translated from Avtomatika i Telemekhanika, No. 2, 2005, pp. 175–189.Original Russian Text Copyright © 2005 by Karavai.     

Progress under bounded fairness

Summary. Progress is investigated for a shared-memory distributed system with a weak form of fault tolerance that allows processes to stop and restart functioning without notification. The concept of bounded fairness is introduced to formalize bounded delay under the assumption that each family of related processes continuously contains at least one active member. This is a generalization of wait-freedom, and also of a finitary form of weak fairness. Several useful proof rules are stated and proved. In a system with bounded fairness, a wait-free process can be constructed by forming a new process in which processes from the various families are scheduled in a round robin way. The theory is applied to prove progress within bounded delay for a linearizing concurrent data-object in shared memory. The safety properties of this algorithm have been treated elsewhere. Received: April 1998 / Accepted: March 1999     

Adaptive and efficient mutual exclusion

Summary. This paper presents adaptive algorithms for mutual exclusion using only read and write operations; the performance of the algorithms depends only on the point contention, i.e., the number of processes that are concurrently active during the algorithm execution (and not on n, the total number of processes). Our algorithm has O(k) remote step complexity and O(logk) system response time, wherek is the point contention. The remote step complexity is the maximal number of steps performed by a process where a wait is counted as one step. The system response time is the time interval between subsequent entries to the critical section, where one time unit is the minimal interval in which every active process performs at least one step. The space complexity of this algorithm is O(N logn), where N is the range of processes' names. We show how to make the space complexity of our algorithm depend solely on n, while preserving the other performance measures of the algorithm. Received: March 2001 / Accepted: November 2001     

Asynchronous group mutual exclusion

Abstract. Mutual exclusion and concurrency are two fundamental and essentially opposite features in distributed systems. However, in some applications such as Computer Supported Cooperative Work (CSCW) we have found it necessary to impose mutual exclusion on different groups of processes in accessing a resource, while allowing processes of the same group to share the resource. To our knowledge, no such design issue has been previously raised in the literature. In this paper we address this issue by presenting a new problem, called Congenial Talking Philosophers, to model group mutual exclusion. We also propose several criteria to evaluate solutions of the problem and to measure their performance. Finally, we provide an efficient and highly concurrent distributed algorithm for the problem in a shared-memory model where processes communicate by reading from and writing to shared variables. The distributed algorithm meets the proposed criteria, and has performance similar to some naive but centralized solutions to the problem. Received: November 1998 / Accepted: April 2000     

Performing tasks on synchronous restartable message-passing processors

Summary. This work considers the problem of performing t tasks in a distributed system of p fault-prone processors. This problem, called do-all herein, was introduced by Dwork, Halpern and Waarts. The solutions presented here are for the model of computation that abstracts a synchronous message-passing distributed system with processor stop-failures and restarts. We present two new algorithms based on a new aggressive coordination paradigm by which multiple coordinators may be active as the result of failures. The first algorithm is tolerant of stop-failures and does not allow restarts. Its available processor steps (work) complexity is and its message complexity is . Unlike prior solutions, our algorithm uses redundant broadcasts when encountering failures and, for p =t and largef, it achieves better work complexity. This algorithm is used as the basis for another algorithm that tolerates stop-failures and restarts. This new algorithm is the first solution for the do-all problem that efficiently deals with processor restarts. Its available processor steps is , and its message complexity is , wheref is the total number of failures. Received: October 1998 / Accepted: September 2000     

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     

An algorithm for the asynchronous Write-All problem based on process collision

Summary. The problem of using P processes to write a given value to all positions of a shared array of size N is called the Write-All problem. We present and analyze an asynchronous algorithm with work complexity , where (assuming and ). Our algorithm is a generalization of the naive two-processor algorithm where the two processes each start at one side of the array and walk towards each other until they collide. Received: October 1999 / Accepted: September 2000     

Functional-join processing

Inter-object references are one of the key concepts of object-relational and object-oriented database systems. In this work, we investigate alternative techniques to implement inter-object references and make the best use of them in query processing, i.e., in evaluating functional joins. We will give a comprehensive overview and performance evaluation of all known techniques for simple (single-valued) as well as multi-valued functional joins. Furthermore, we will describe special order-preserving\/ functional-join techniques that are particularly attractive for decision support queries that require ordered results. While most of the presentation of this paper is focused on object-relational and object-oriented database systems, some of the results can also be applied to plain relational databases because index nested-loop joins\/ along key/foreign-key relationships, as they are frequently found in relational databases, are just one particular way to execute a functional join. Received February 28, 1999 / Accepted September 27, 1999     

An efficient animation of wrinkled cloth with approximate implicit integration

This paper presents an efficient method for creating the animation of flexible objects. The mass-spring model was used to represent flexible objects. The easiest approach to creating animation with the mass-spring model is the explicit Euler method, but the method has a serious weakness in that it suffers from an instability problem. The implicit integration method is a possible solution, but a critical flaw of the implicit method is that it involves a large linear system. This paper presents an approximate implicit method for the mass-spring model. The proposed technique updates with stability the state of n mass points in O(n) time when the number of total springs is O(n). In order to increase the efficiency of simulation or reduce the numerical errors of the proposed approximate implicit method, the number of mass points must be as small as possible. However, coarse discretization with a small number of mass points generates an unrealistic appearance for a cloth model. By introducing a wrinkled cubic spline curve, we propose a new technique that generates realistic details of the cloth model, even though a small number of mass points are used for simulation.     

Formal Analysis of Memory Requirements

Shared memory provides a convenient programming model for parallel applications. However, such a model is provided on physically distributed memory systems at the expense of efficiency of execution of the applications. For this reason, applications can give minimum consistency requirements on the memory system, thus allowing alternatives to the shared memory model to be used which exploit the underlying machine more efficiently. To be effective, these requirements need to be specified in a precise way and to be amenable to formal analysis. Most approaches to formally specifying consistency conditions on memory systems have been from the viewpoint of the machine rather than from the application domain.  In this paper we show how requirements on memory systems can be given from the viewpoint of the application domain formally in a first-order theory MemReq, to improve the requirements engineering process for such systems. We show the general use of MemReq in expressing major classes of requirements for memory systems and conduct a case study of the use of MemReq in a real-life parallel system out of which the formalism arose.     

Universal dynamic synchronous self–stabilization

Summary. We prove the existence of a “universal” synchronous self-stabilizing protocol, that is, a protocol that allows a distributed system to stabilize to a desired nonreactive behaviour (as long as a protocol stabilizing to that behaviour exists). Previous proposals required drastic increases in asymmetry and knowledge to work, whereas our protocol does not use any additional knowledge, and does not require more symmetry-breaking conditions than available; thus, it is also stabilizing with respect to dynamic changes in the topology. We prove an optimal quiescence time n+D for a synchronous network of n processors and diameter D; the protocol can be made finite state with a negligible loss in quiescence time. Moreover, an optimal D+1 protocol is given for the case of unique identifiers. As a consequence, we provide an effective proof technique that allows to show whether self-stabilization to a certain behaviour is possible under a wide range of models. Received: January 1999 / Accepted: July 2001