In a seminal paper, Chandra and Toueg showed how unreliable failure detectors could allows processors to achieve consensus in asynchronous message passing systems. Since then, other researchers have developed consensu...
详细信息
ISBN:
(纸本)9780897919777
In a seminal paper, Chandra and Toueg showed how unreliable failure detectors could allows processors to achieve consensus in asynchronous message passing systems. Since then, other researchers have developed consensus algorithms for other systems or based on different failure detectors. Each algorithm was developed and proven independently. This paper shows how a consensus algorithm for any of the standard models can be automatically converted to run in any other. These results show more clearly how the different system models and failure detectors can be related. In addition, they may permit the development of new results for new models also through transformations.
We take a significant step toward unifying the synchronous, semi-synchronous, and asynchronous message-passing models of distributed computation. The key idea is the concept of a pseudosphere, a new combinatorial stru...
详细信息
We take a significant step toward unifying the synchronous, semi-synchronous, and asynchronous message-passing models of distributed computation. The key idea is the concept of a pseudosphere, a new combinatorial structure in which each process from a set of processes is independently assigned a value from a set of values. Pseudospheres have a number of nice combinatorial properties, but their principal interest lies in the observation that the behavior of protocols in the three models can be characterized as simple unions of pseudospheres, where the exact structure of these unions is determined by the timing properties of the model. We use this pseudosphere construction to derive new and remarkably succinct proofs of bounds on consensus and k-set agreement in the asynchronous and synchronous models, as well as the first lower bound on wait-free k-set agreement in the semi-synchronous model.
Mutual exclusion and concurrency are two fundamental and essentially opposite features in distributed systems. However, in some applications such as computer supported cooperative works (CSCW) we have found it necessa...
详细信息
Mutual exclusion and concurrency are two fundamental and essentially opposite features in distributed systems. However, in some applications such as computer supported cooperative works (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 raised in the literature. Our contributions of the paper are to present a new problem, which we refer to as the Congenial Talking Philosophers, to model the design issue for concurrency while 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 a similar performance as some naive but centralized solutions to the problem.
This paper studies the ability of shared memory distributed systems to solve the wait-free consensus problem if processes are permitted to access more than one shared data object in a single atomic action. Suppose T i...
详细信息
ISBN:
(纸本)9780897919777
This paper studies the ability of shared memory distributed systems to solve the wait-free consensus problem if processes are permitted to access more than one shared data object in a single atomic action. Suppose T is any deterministic object type that can be used, with read/write registers, to solve consensus among n processes, with n>2. A multi-object of type Tm consists of a collection of objects of type T, any m of which can be accessed in a single atomic action. It will be shown that a multi-object of type Tm can be used, with registers, to solve consensus among Ω(n√m) processes. Furthermore, if the type T is equipped with operations that allow processes to read its state without altering the state, then the multi-object can be used with registers to solve consensus among Ω(nm) processes. Neither of these lower bounds can be improved.
In this paper we present a novel algorithm that implements a totally ordered multicast primitive for a Totally Ordered Group Communication Service (TO-GCS). TO-GCS is a powerful infrastructure for building distributed...
详细信息
In this paper we present a novel algorithm that implements a totally ordered multicast primitive for a Totally Ordered Group Communication Service (TO-GCS). TO-GCS is a powerful infrastructure for building distributed fault-tolerant applications, such as totally ordered broadcast, consistent object replication, distributed shared memory, Computer Supported Cooperative Work (CSCW) applications and distributed monitoring and display applications. Our algorithm is adaptive, i.e., it is able to dynamically alter the message delivery order in response to changes in the transmission rates of the participating processes. This compensates for differences among participant transmission rates and therefore minimizes fluctuations in message delivery latency. Our algorithm is thus useful for soft real-time environments where sharp fluctuations in message delivery latency are not acceptable. Our solution provides well-defined message ordering semantics. These semantics are preserved even in the face of site and communication link failures.
We present a new model for handling messages and state in a distributed application that we call Messages in Local Transactions (MLT). Under this model, messages and data are not lost after crashes, and all sends and ...
详细信息
ISBN:
(纸本)9780897919777
We present a new model for handling messages and state in a distributed application that we call Messages in Local Transactions (MLT). Under this model, messages and data are not lost after crashes, and all sends and receives are performed in local transactions. The model is unique in that it guarantees consistent recovery without the complexity or overhead of other recovery techniques. Applications using MLT do not need to coordinate checkpoints, track causal dependencies, or perform distributed commits. We show that MLT can be implemented using any reliable protocol. Finally, we describe our implementation of Vista-grams, a system based on the MLT model. We show that Vistagrams are just as fast as traditional messages, despite the recoverability they offer. The efficiency of our model and our Vistagrams implementation is enabled by the availability of fast stable storage, such as the reliable memory provided by the Rio file cache.
This paper presents a new family of models of distributed-computation which combines features from synchronous, asynchronous, and failure-detector-augmented systems. Like synchronous systems, computation in this famil...
详细信息
This paper presents a new family of models of distributed-computation which combines features from synchronous, asynchronous, and failure-detector-augmented systems. Like synchronous systems, computation in this family of models evolves in rounds, and communication missed at a round is lost. Unlike synchronous systems, information that is missed at a round does not necessarily imply a real process failure. The features of a specific model is captured in an abstract module called the round-by-round fault detector. The abstraction of system features into such a module facilitates the comparison of different systems, by contrasting their associated fault detectors. We show that this family of models unifies the study of synchrony, asynchrony, message-passing and shared memory. We further show that this approach leads to the development of shorter and simpler proofs of important results such as a lower bound on the number of rounds to achieve k-set agreement in a synchronous system. We believe that studying distributed systems through the proposed unifying framework will lead to new results and insights.
We introduce simple notion of layering that provides a tool for defining submodels of a given model of distributed computation. We describe two layerings, the synchronic and the permutation layering, and show that the...
详细信息
We introduce simple notion of layering that provides a tool for defining submodels of a given model of distributed computation. We describe two layerings, the synchronic and the permutation layering, and show that they induce appropriate submodels of several asynchronous models of computation. The synchronic layering applies to the synchronous model too. We perform a model-independent analysis of the consensus problem in terms of abstract connectivity properties of layering functions. By defining particular layerings in specific models, we derive several popular (and some new) lower bounds and impossibility results for consensus in various classical models. These results are often stronger in the sense that they apply to the submodel induced by the layering. The proofs obtained in this way are also simpler and more direct than existing ones. Moreover, the analysis is done in a uniform fashion and demonstrates the fundamental common structure of the consensus problem in the presence of failures. The analysis is then extended to general decision problems (1-resilient in the asynchronous models, t-rounds in the t-resilient synchronous model), providing a characterization of solvability of decision problems in the style of [8] which, for some of the models, is given for the first time.
View-oriented group communication services are widely used for fault-tolerant distributedcomputing. For applications involving coherent data, it is important to know when a process has a primary view of the current g...
详细信息
View-oriented group communication services are widely used for fault-tolerant distributedcomputing. For applications involving coherent data, it is important to know when a process has a primary view of the current group membership, usually defined as a view containing a majority out of a static universe of processes. For high availability in a system where processes can join and leave routinely, some researchers have suggested defining primary views dynamically, depending on having enough members in common with recent views. We present a new formal automaton specification, DVS, for the safety guarantees made by a practical group communication service providing a dynamic notion of primary view. We demonstrate the value of DVS by showing both how it can be implemented and how it can be used in an application. First, we present a distributed algorithm based on a group membership algorithm of Lotem, Keidar and Dolev;our version integrates communication with the membership service, uses information from the application processes saying when a view has been prepared for computation by the application, and uses a static view-oriented service internally. We prove that this algorithm implements DVS. Second, we present an application algorithm that is a variant of an algorithm of Amir, Dolev, Keidar, Melliar-Smith and Moser, modified to use DVS instead of a static service. We prove that it implements a (non-group-oriented) totally-ordered-broadcast service.
暂无评论