Search

The advent of multicore architectures is a good incentive to better understand base synchronization mechanisms. This paper, which can be considered as a simple introduction to the topic, presents (with a pedagogical flavor) the concept of rendezvous (also called interaction, synchronous communication, or logically instantaneous communication) and several implementations of it. This abstraction adds synchronization to communication, namely, it requires that, for a message to be sent by a process, the receiver has to be ready to receive it. From an external observer point view, the message transmission looks like instantaneous: the sending and the reception of a message appear as being a single event (and the sense of the communication could have been in the other direction). From an operational point of view, we have the following: for each pair of processes, the first process that wants to communicate - be it the sender or the receiver - has to. wait until the other process is ready to communicate.

3D Virtual Environments, used to visualize complex data, are emerging in different domains. Among interaction tasks that have been defined for this kind of applications, the evaluation of an elementary task like the pointing task can simplify the determination of an appropriate technique used to perform the task in this environment. We detail and discuss results of a user experimentation conducted according to a composite approach, which aims at assessing performance, comfort of techniques and satisfaction of users for a 3D pointing task.

This invited talk surveys notions related to synchronization in presence of asynchrony and failures. To the author knowledge, there is currently no textbook in which these notions are pieced together, unified, and presented in a homogeneous way. This talk (that pretends to be neither exhaustive, nor objective) is only a first endeavor in that direction. The notions that are presented and discussed are listed in the keyword list.

An important issue in fault-tolerant asynchronous computing is the respective power of an object type with respect to another object type. This question has received a lot of attention, mainly in the context of the consensus problem where a major advance has been the introduction of the consensus number notion that allows ranking the synchronization power of base object types (atomic registers, queues, test&set objects, compare&swap objects, etc.) with respect to the consensus problem. This has given rise to the well-known Herlihy's hierarchy. Due to its very definition, the consensus number notion is irrelevant for studying the respective power of object types that are too weak to solve consensus for an arbitrary number of processes (these objects are usually called subconsensus objects). Considering an asynchonous system made up of n processes prone to crash, this paper addresses the power of such object types, namely, the k-test&set object type, the k-set agreement object type, and the adaptive M-renaming object type for M = 2p - [P/N] and M = min(2p - 1,p + k - 1), where p < n is the number of processes that want to acquire a new name. It investigates their respective power stating the necessary and sufficient conditions to build objects of any of these types from objects of any of the other types. More precisely, the paper shows that (1) these object types define a strict hierarchy when k ne1,n - 1, (2) they all are equivalent when k = n - 1, and (3) they all are equivalent except k-set agreement that is stronger when k = 1 ne n - 1 (a side effect of these results is that that the consensus number of the renaming problem is 2.)

A concurrent object is an object that can be concurrently accessed by several processes. A wait-free implementation of an object is such that any operation issued by a non-faulty process terminates in a finite number of its own steps, whatever the behavior of the other processes (that can be very slow or even have crashed). An object type is universal if objects of that type, together with atomic registers, allows implementing any concurrent object defined by a sequential specification. A universal construction is a wait-free algorithm, based only on atomic registers and universal objects, that, given any sequential object type T, provides the processes with a wait-free concurrent object of the type T. In a famous paper (titled "Wait-free synchronization") Herlihy has shown that consensus objects are universal, and has presented a consensus-based universal construction. We present here a new universal construction. That construction, that is built incrementally, is particularly simple. While, in addition to consensus objects, Herlihy's universal construction uses low-level objects such as pointers, the design of the construction presented here is based on the simple and well-known state machine replication paradigm. Its proof is also simple and consequently allows to better understand not only the power of consensus objects but also the subtleties of wait-free computations and the way the consensus objects allow coping with both process failures and non-determinism. In that sense, this paper has a pedagogical flavor.

A noteworthy advance in distributed computing is due to the recent development of peer-to-peer systems. These systems are essentially dynamic in the sense that no process can get a global knowledge on the system structure. They mainly allow processes to look up for data that can be dynamically added/suppressed in a permanently evolving set of nodes. Although protocols have been developed for such dynamic systems, to our knowledge, up to date no computation model for dynamic systems has been proposed. Nevertheless, there is a strong demand for the definition of such models as soon as one wants to develop provably correct protocols suited to dynamic systems. The talk will present an approach aiming at defining an appropriate model for (a class of) dynamic systems. That dynamic model is defined by (1) a parameter (an integer denoted alpah) and (2) two basic communication abstractions (query-response and persistent reliable broadcast). The parameter alpha is a threshold value introduced to capture the liveness part of the system (it is the counterpart of the minimal number of processes that do not crash in a static system). To show the relevance of the model, the paper discusses several distributed computing issues in the context of dynamic systems, such as atomicity, quorums, and leader election.

A concurrent object is an object that can be concurrently accessed by several processes. Two well-known consistency criteria for such objects are atomic consistency (also called linearizability) and sequential consistency. Both criteria require that all the operations on the concurrent objects can be totally ordered in such a way that each read operation obtains the last value written into the corresponding object. They differ in the meaning of the word "last" that refers to physical time for atomic consistency, and to logical time for sequential consistency. This paper investigates the merging of these consistency criteria in a multiprocess program. The proposed combination offers two read operations to the processes, namely, an atomic read operation and a sequentially consistent read operation. While the first provides a process with the last "physical" value of an object, the second provides it with a value that is approximate with respect to real-time but whose semantics is perfectly well defined. A protocol that implements the combination on top of an asynchronous distributed system is described. The protocol provides a better understanding of the similarities and differences between these consistency criteria. Moreover, the protocol is generic in the sense that it can be tailored to provide only one of these consistency criteria.

Consensus is a fundamental distributed agreement problem that has to be solved when one has to design or implement reliable applications. As consensus cannot be solved in pure asynchronous distributed systems, those systems have to be equipped with appropriate oracles to circumvent the impossibility. Several oracles (unreliable failure detector leader capability, random number generator) have been proposed, and consensus protocols based on such ad hoc oracles have been designed This paper presents a generic consensus framework that can be instantiated with any oracle, or combination of oracles, that satisfies a set of properties. This generic framework provides indulgent consensus protocols that are particularly simple and efficient both in well-behaved runs (i.e., when there are no failures), and in stable runs (i.e., when there is no failure during the execution although some processes can be initially crashed). In those runs, the protocols terminate in two communication steps (which is optimal). Indulgence means that the resulting protocol never violates its safety property even when the underlying oracle behaves arbitrarily. Interestingly, the protocol can also allow processes to decide in one communication step in some specific configurations.

This paper considers central issues of distributed computing in a mobile environment. Its aim is to light on the first brick of a common view for mobile systems. We pool together mobile systems and analyze them from different angles including architecture and computability aspects. We show that mobile systems (i.e., cellular systems, ad hoc networks, peer-to-peer systems, virtual reality systems or cooperative robotics) are basically confronted with the same problems, hence it is useless to maintain the actual "misleading" barriers. Due to important similarities between the different mobile systems we claim that the next logical step in building a common view is to design a model which conceptually should unify them by providing an abstract description of the parameters which distinguish these systems from classic distributed systems. Moreover, in the new model, the fundamental problems of distributed computing (i.e., (k-)mutual exclusion, leader election or group communication) should find appropriate specifications.

Sequential consistency is a consistency criterion for concurrent objects stating that the execution of a multiprocess program is correct if it could have been produced by executing the program on a mono-processor system, preserving the order of the operations of each individual process. Several protocols implementing sequential consistency on top of asynchronous distributed systems have been proposed. They assume that the processes access the shared objects through basic read and write operations. We consider the case where the processes can invoke multiobject operations which can read or write several objects in a single operation atomically. It proposes a particularly simple protocol that guarantees sequentially consistent executions in such a context. The previous sequential consistency protocols, in addition to considering only unary operations, assume either full replication or a central manager storing copies of all the objects. In contrast, the proposed protocol has the noteworthy feature that each object has a separate manager. Interestingly, this provides the protocol with a versatility dimension that allows deriving simple protocols providing sequential consistency or atomic consistency when each operation is on a single object.

This paper presents two Compare&Swap protocols that, with respect to omission failures, are (1) fault-tolerant and (2) gracefully degrading, respectively. It shows that fault-tolerance and graceful degradation are close but distinct concepts, and that graceful degradation is inherently more costly than fault-tolerance. These Compare&Swap protocols are derived from consensus protocols proposed by Jayanti et al. (1999).

Multicast communications are of primary importance for multimedia real-time applications where participants are required to exchange real-time audio and video information over a communication network. This flow of information must preserve the causal dependency even though part of the information can be lost or discarded if it violates the timing constraints imposed by a real-time interaction. As it is, a causal order communication mode concerns distributed systems without real-time delivery constraints and assumes unpredictable but finite messages transmission delays and, hence, protocols implementing this communication mode do not cope with real-time issues. We first propose a communication abstraction to cope with unreliable communication networks with real-time delivery constraints: messages have a lifetime, /spl Delta/, after which their contents can no longer be used, moreover some of them can be lost. Secondly, we propose a protocol imposing /spl Delta/-causal order in the case of one-to-one and one-to-many (multicast) communications.

Describes a shore based monitoring system used in Mediterranean Sea within the framework of a European Acoustic Tomographic program. The main features of the listening station are: self governing, continuous real time processing to verify the working conditions of acoustic sources, and data storage at a very good accuracy. Moreover, the monitoring station is operated by remote control via a telephonic modem. >

Providing processes with the same view of a global state or allowing them to take consistent decisions, despite asynchrony and failure occurrences, are fundamental problems encountered in distributed systems. These problems are called agreement problems. Non blocking atomic commitment and definition of a single delivery order for broadcast messages are examples of such problems. We define a paradigm (called Single Global View) that encompasses various practical agreement problems. The interest of this paradigm lies in its practicability: each process starts with an initial value, and all these values are pieced together in such a way that, despite process crashes and asynchrony, all correct processes are delivered the same set of values (namely, the Single Global View). The power of this paradigm is the same as that of the consensus problem defined by theoreticians. Instantiations of the paradigm, which solve practical agreement problems, are given. A protocol implementing the paradigm is also presented.

This paper studies properties of messages communication modes in distributed systems. It establishes a simple, hierarchical and homogeneous characterization of logically instantaneous, causally ordered and first-in-first-out communications. It is shown that a distributed computation obeys one of the previous communication modes iff a communication graph of messages does not include a cycle. This characterization plays a key role when one is interested in designing, analyzing, testing or debugging asynchronous distributed computations. This graph-based approach shows there is some unity in the characterization of deadlock, concurrency control, memory consistency and communication modes. >

The focus of this work is on a particular class of unstable global states: the states with no in-transit message. A characterization of these states and their interest are given, along with the principles of their detection. As detecting these states requires a network traversal, choosing a particular implementation of this traversal gives one instance from a family of algorithms. The algorithm based on a virtual Hamiltonian cycle (a ring traversal) is presented and proved to be correct. The exposition of the principles and of the ring algorithm is done in an analytic way: algorithmic techniques are given separately (markers, message counting, network traversal) to lay down the snapshot definition properties. >