The Experts below are selected from a list of 12204 Experts worldwide ranked by ideXlab platform
Michel Raynal - One of the best experts on this subject based on the ideXlab platform.
-
time efficient read write register in crash prone Asynchronous Message passing systems
Computing, 2019Co-Authors: Achour Mostefaoui, Michel Raynal, Matthieu RoyAbstract:The atomic register is one of the most basic and useful object of computing science, and its simple read-write semantics is appealing when programming distributed systems. Hence, its implementation on top of crash-prone Asynchronous Message-passing systems has received a lot of attention. It was shown that having a strict minority of processes that may crash is a necessary and sufficient requirement to build an atomic register on top of a crash-prone Asynchronous Message-passing system. This paper visits the notion of a fast implementation of an atomic register, and presents a new time-efficient Asynchronous algorithm that reduces latency in many cases: a write operation always costs a round-trip delay, while a read operation costs a round-trip delay in favorable circumstances (intuitively, when it is not concurrent with a write). When designing this algorithm, the design spirit was to be as close as possible to the original algorithm proposed by Attiya, Bar-Noy, and Dolev.
-
Implementing Snapshot Objects on Top of Crash-Prone Asynchronous Message-Passing Systems
IEEE Transactions on Parallel and Distributed Systems, 2018Co-Authors: Carole Delporte-gallet, Sergio Rajsbaum, Hugues Fauconnier, Michel RaynalAbstract:In Asynchronous crash-prone read/write shared-memory systems there is the notion of a snapshot object, which simulates the behavior of an array of single-writer/multi-reader (SWMR) shared registers that can be read atomically. Processes in the system can access the object invoking (any number of times) two operations, denoted write() and snapshot(). A process invokes write() to update the value of its register in the array. When it invokes snapshot(), the process obtains the values of all registers, as if it read them simultaneously. It is known that a snapshot object can be implemented on top of SWMR registers, tolerating any number of process failures. Snapshot objects provide a level of abstraction higher than individual SWMR registers, and they simplify the design of applications. Building a snapshot object on an Asynchronous crash-prone Message-passing system has similar benefits. The object can be implemented by using the known simulations of a SWMR shared memory on top of an Asynchronous Message-passing system (if less than half the processes can crash), and then build a snapshot object on top of the simulated SWMR memory. This paper presents an algorithm that implements a snapshot object directly on top of the Message-passing system, without building an intermediate layer of a SWMR shared memory. To the authors knowledge, the proposed algorithm is the first providing such a direct construction. The algorithm is more efficient than the indirect solution, yet relatively simple.
-
implementable agreement abstractions despite asynchrony and a minority of process crashes
2018Co-Authors: Michel RaynalAbstract:This chapter addresses the implementation of agreement abstractions in Asynchronous systems where the processes communicate by reading and writing atomic registers. We have seen in Chap. 5 that atomic registers can be built in Asynchronous Message-passing systems only if t < n/2. Implementations of read/write registers in the system model CAMPn,t[t < n/2] have been presented in Chap. 6 and Chap. 8.
-
set constrained delivery broadcast definition abstraction power and computability limits
arXiv: Distributed Parallel and Cluster Computing, 2017Co-Authors: Damien Imbs, Achour Mostefaoui, Matthieu Perrin, Michel RaynalAbstract:This paper introduces a new communication abstraction, called Set-Constrained Delivery Broadcast (SCD-broadcast), whose aim is to provide its users with an appropriate abstraction level when they have to implement objects or distributed tasks in an Asynchronous Message-passing system prone to process crash failures. This abstraction allows each process to broadcast Messages and deliver a sequence of sets of Messages in such a way that, if a process delivers a set of Messages including a Message m and later delivers a set of Messages including a Message m ' , no process delivers first a set of Messages including m ' and later a set of Message including m. After having presented an algorithm implementing SCD-broadcast, the paper investigates its programming power and its computability limits. On the "power" side it presents SCD-broadcast-based algorithms, which are both simple and efficient, building objects (such as snapshot and conflict-free replicated data), and distributed tasks. On the "computability limits" side it shows that SCD-broadcast and read/write registers are computationally equivalent.
-
atomic read write memory in signature free byzantine Asynchronous Message passing systems
Parallel Computing Technologies, 2017Co-Authors: Achour Mostefaoui, Michel Raynal, Matoula Petrolia, Claude JardAbstract:This article presents a signature-free distributed algorithm which builds an atomic read/write shared memory on top of a fully connected peer-to-peer n-process Asynchronous Message-passing system in which up to t
Achour Mostefaoui - One of the best experts on this subject based on the ideXlab platform.
-
time efficient read write register in crash prone Asynchronous Message passing systems
Computing, 2019Co-Authors: Achour Mostefaoui, Michel Raynal, Matthieu RoyAbstract:The atomic register is one of the most basic and useful object of computing science, and its simple read-write semantics is appealing when programming distributed systems. Hence, its implementation on top of crash-prone Asynchronous Message-passing systems has received a lot of attention. It was shown that having a strict minority of processes that may crash is a necessary and sufficient requirement to build an atomic register on top of a crash-prone Asynchronous Message-passing system. This paper visits the notion of a fast implementation of an atomic register, and presents a new time-efficient Asynchronous algorithm that reduces latency in many cases: a write operation always costs a round-trip delay, while a read operation costs a round-trip delay in favorable circumstances (intuitively, when it is not concurrent with a write). When designing this algorithm, the design spirit was to be as close as possible to the original algorithm proposed by Attiya, Bar-Noy, and Dolev.
-
set constrained delivery broadcast definition abstraction power and computability limits
arXiv: Distributed Parallel and Cluster Computing, 2017Co-Authors: Damien Imbs, Achour Mostefaoui, Matthieu Perrin, Michel RaynalAbstract:This paper introduces a new communication abstraction, called Set-Constrained Delivery Broadcast (SCD-broadcast), whose aim is to provide its users with an appropriate abstraction level when they have to implement objects or distributed tasks in an Asynchronous Message-passing system prone to process crash failures. This abstraction allows each process to broadcast Messages and deliver a sequence of sets of Messages in such a way that, if a process delivers a set of Messages including a Message m and later delivers a set of Messages including a Message m ' , no process delivers first a set of Messages including m ' and later a set of Message including m. After having presented an algorithm implementing SCD-broadcast, the paper investigates its programming power and its computability limits. On the "power" side it presents SCD-broadcast-based algorithms, which are both simple and efficient, building objects (such as snapshot and conflict-free replicated data), and distributed tasks. On the "computability limits" side it shows that SCD-broadcast and read/write registers are computationally equivalent.
-
atomic read write memory in signature free byzantine Asynchronous Message passing systems
Parallel Computing Technologies, 2017Co-Authors: Achour Mostefaoui, Michel Raynal, Matoula Petrolia, Claude JardAbstract:This article presents a signature-free distributed algorithm which builds an atomic read/write shared memory on top of a fully connected peer-to-peer n-process Asynchronous Message-passing system in which up to t
-
another look at the implementation of read write registers in crash prone Asynchronous Message passing systems extended version
arXiv: Distributed Parallel and Cluster Computing, 2017Co-Authors: Damien Imbs, Achour Mostefaoui, Matthieu Perrin, Michel RaynalAbstract:" Yet another paper on " the implementation of read/write registers in crash-prone Asynchronous Message-passing systems! Yes..., but, differently from its predecessors, this paper looks for a communication abstraction which captures the essence of such an implementation in the same sense that total order broadcast can be associated with consensus, or Message causal delivery can be associated with causal read/write registers. To this end, the paper introduces a new communication abstraction, named SCD-broadcast (SCD standing for " Set Constrained Delivery "), which, instead of a single Message, delivers to processes sets of Messages (whose size can be arbitrary), such that the sequences of Message sets delivered to any two processes satisfies some constraints. The paper then shows that: (a) SCD-broadcast allows for a very simple implementation of a snapshot object (and consequently also of atomic read/write registers) in crash-prone Asynchronous Message-passing systems; (b) SCD-broadcast can be built from snapshot objects (hence SCD-broadcast and snapshot objects –or read/write registers– are " computationally equivalent "); (c) SCD-broadcast can be built in Message-passing systems where any minority of processes may crash (which is the weakest assumption on the number of possible process crashes needed to implement a read/write register).
-
on composition and implementation of sequential consistency
International Symposium on Distributed Computing, 2016Co-Authors: Matthieu Perrin, Achour Mostefaoui, Matoula Petrolia, Claude JardAbstract:It has been proved that to implement a linearizable shared memory in synchronous Message-passing systems it is necessary to wait for a time proportional to the uncertainty in the latency of the network for both read and write operations, while waiting during read or during write operations is sufficient for sequential consistency. This paper extends this result to crash-prone Asynchronous systems. We propose a distributed algorithm that builds a sequentially consistent shared memory abstraction with snapshot on top of an Asynchronous Message-passing system where less than half of the processes may crash. We prove that it is only necessary to wait when a read/snapshot is immediately preceded by a write on the same process. We also show that sequential consistency is composable in some cases commonly encountered: 1) objects that would be linearizable if they were implemented on top of a linearizable memory become sequentially consistent when implemented on top of a sequential memory while remaining composable and 2) in round-based algorithms, where each object is only accessed within one round.
Alexander A Shvartsman - One of the best experts on this subject based on the ideXlab platform.
-
emulating shared memory do all algorithms in Asynchronous Message passing systems
Journal of Parallel and Distributed Computing, 2010Co-Authors: Dariusz R Kowalski, M Momenzadeh, Alexander A ShvartsmanAbstract:A fundamental problem in distributed computing is performing a set of tasks despite failures and delays. Stated abstractly, the problem is to perform N tasks using P failure-prone processors. This paper studies the efficiency of emulating shared-memory task-performing algorithms on Asynchronous Message-passing processors with quantifiable Message latency. Efficiency is measured in terms of work and communication, and the challenge is to obtain subquadratic work and Message complexity. While prior solutions assumed synchrony and constant delays, the solutions given here yield subquadratic efficiency with Asynchronous processors when the delays and failures are suitably constrained. The solutions replicate shared objects using a quorum system, provided it is not disabled. One algorithm has subquadratic work and communication when the delays and the number of processors, K, owning object replicas, are O(P^0^.^4^1). It tolerates @[email protected]? crashes. It is also shown that there exists an algorithm that has subquadratic work and communication and that tolerates o(P) failures, provided Message delays are sublinear.
-
emulating shared memory do all algorithms in Asynchronous Message passing systems
International Conference on Principles of Distributed Systems, 2003Co-Authors: Dariusz R Kowalski, M Momenzadeh, Alexander A ShvartsmanAbstract:A fundamental problem in distributed computing is performing a set of tasks despite failures and delays. Stated abstractly, the problem is to perform N tasks using P failure-prone processors. This paper studies the efficiency of emulating shared-memory task-performing algorithms on Asynchronous Message-passing processors with quantifiable Message latency. Efficiency is measured in terms of work and communication, and the challenge is to obtain subquadratic work and Message complexity. While prior solutions assumed synchrony and constant delays, the solutions given here yields subquadratic efficiency with Asynchronous processors when the delays and failures is suitably constrained. The solutions replicate shared objects using a quorum system, provided it is not disabled. One algorithm has subquadratic work and communication when the delays and the number of processors, K, owning object replicas, are O(P 0.41). It tolerates \(\lceil \frac{K-1}{2}\rceil\) crashes. It is also shown that there exists an algorithm that has subquadratic work and communication and that tolerates o(P) failures, provided Message delays are sublinear.
Dariusz R Kowalski - One of the best experts on this subject based on the ideXlab platform.
-
emulating shared memory do all algorithms in Asynchronous Message passing systems
Journal of Parallel and Distributed Computing, 2010Co-Authors: Dariusz R Kowalski, M Momenzadeh, Alexander A ShvartsmanAbstract:A fundamental problem in distributed computing is performing a set of tasks despite failures and delays. Stated abstractly, the problem is to perform N tasks using P failure-prone processors. This paper studies the efficiency of emulating shared-memory task-performing algorithms on Asynchronous Message-passing processors with quantifiable Message latency. Efficiency is measured in terms of work and communication, and the challenge is to obtain subquadratic work and Message complexity. While prior solutions assumed synchrony and constant delays, the solutions given here yield subquadratic efficiency with Asynchronous processors when the delays and failures are suitably constrained. The solutions replicate shared objects using a quorum system, provided it is not disabled. One algorithm has subquadratic work and communication when the delays and the number of processors, K, owning object replicas, are O(P^0^.^4^1). It tolerates @[email protected]? crashes. It is also shown that there exists an algorithm that has subquadratic work and communication and that tolerates o(P) failures, provided Message delays are sublinear.
-
emulating shared memory do all algorithms in Asynchronous Message passing systems
International Conference on Principles of Distributed Systems, 2003Co-Authors: Dariusz R Kowalski, M Momenzadeh, Alexander A ShvartsmanAbstract:A fundamental problem in distributed computing is performing a set of tasks despite failures and delays. Stated abstractly, the problem is to perform N tasks using P failure-prone processors. This paper studies the efficiency of emulating shared-memory task-performing algorithms on Asynchronous Message-passing processors with quantifiable Message latency. Efficiency is measured in terms of work and communication, and the challenge is to obtain subquadratic work and Message complexity. While prior solutions assumed synchrony and constant delays, the solutions given here yields subquadratic efficiency with Asynchronous processors when the delays and failures is suitably constrained. The solutions replicate shared objects using a quorum system, provided it is not disabled. One algorithm has subquadratic work and communication when the delays and the number of processors, K, owning object replicas, are O(P 0.41). It tolerates \(\lceil \frac{K-1}{2}\rceil\) crashes. It is also shown that there exists an algorithm that has subquadratic work and communication and that tolerates o(P) failures, provided Message delays are sublinear.
Sergio Rajsbaum - One of the best experts on this subject based on the ideXlab platform.
-
Implementing Snapshot Objects on Top of Crash-Prone Asynchronous Message-Passing Systems
IEEE Transactions on Parallel and Distributed Systems, 2018Co-Authors: Carole Delporte-gallet, Sergio Rajsbaum, Hugues Fauconnier, Michel RaynalAbstract:In Asynchronous crash-prone read/write shared-memory systems there is the notion of a snapshot object, which simulates the behavior of an array of single-writer/multi-reader (SWMR) shared registers that can be read atomically. Processes in the system can access the object invoking (any number of times) two operations, denoted write() and snapshot(). A process invokes write() to update the value of its register in the array. When it invokes snapshot(), the process obtains the values of all registers, as if it read them simultaneously. It is known that a snapshot object can be implemented on top of SWMR registers, tolerating any number of process failures. Snapshot objects provide a level of abstraction higher than individual SWMR registers, and they simplify the design of applications. Building a snapshot object on an Asynchronous crash-prone Message-passing system has similar benefits. The object can be implemented by using the known simulations of a SWMR shared memory on top of an Asynchronous Message-passing system (if less than half the processes can crash), and then build a snapshot object on top of the simulated SWMR memory. This paper presents an algorithm that implements a snapshot object directly on top of the Message-passing system, without building an intermediate layer of a SWMR shared memory. To the authors knowledge, the proposed algorithm is the first providing such a direct construction. The algorithm is more efficient than the indirect solution, yet relatively simple.
-
implementing snapshot objects on top of crash prone Asynchronous Message passing systems
International Conference on Algorithms and Architectures for Parallel Processing, 2016Co-Authors: Carole Delportegallet, Hugues Fauconnier, Sergio Rajsbaum, Michel RaynalAbstract:Distributed snapshots, as introduced by Chandy and Lamport in the context of Asynchronous failure-free Message-passing distributed systems, are consistent global states in which the observed distributed application might have passed through. It appears that two such distributed snapshots cannot necessarily be compared (in the sense of determining which one of them is the “first”). Differently, snapshots introduced in Asynchronous crash-prone read/write distributed systems are totally ordered, which greatly simplify their use by upper layer applications.
-
read write shared memory abstraction on top of Asynchronous byzantine Message passing systems
Journal of Parallel and Distributed Computing, 2016Co-Authors: Damien Imbs, Michel Raynal, Sergio Rajsbaum, Julien StainerAbstract:Abstract This paper is on the construction and use of a shared memory abstraction on top of an Asynchronous Message-passing system in which up to t processes may commit Byzantine failures. This abstraction consists of arrays of n single-writer/multi-reader atomic registers, where n is the number of processes. These registers enable Byzantine tolerance by recording the whole history of values written to each one of them. A distributed algorithm building such a shared memory abstraction is first presented. This algorithm assumes t n / 3 , which is shown to be a necessary and sufficient condition for such a construction. Hence, the algorithm is resilient-optimal. Then the paper presents distributed objects built on top of this read/write shared memory abstraction, which cope with Byzantine processes. As illustrated by these objects, the proposed shared memory abstraction is motivated by the fact that, for a lot of problems, algorithms are simpler to design and prove correct in a shared memory system than in a Message-passing system.
-
reliable shared memory abstraction on top of Asynchronous byzantine Message passing systems
International Colloquium on Structural Information and Communication Complexity, 2014Co-Authors: Damien Imbs, Michel Raynal, Sergio Rajsbaum, Julien StainerAbstract:This paper is on the construction and the use of a shared memory abstraction on top of an Asynchronous Message-passing system in which up to t processes may commit Byzantine failures. This abstraction consists of arrays of n single-writer/multi-reader atomic registers, where n is the number of processes. Differently from usual atomic registers which record a single value, each of these atomic registers records the whole history of values written to it. A distributed algorithm building such a shared memory abstraction it first presented. This algorithm assumes t < n/3, which is shown to be a necessary and sufficient condition for such a construction. Hence, the algorithm is resilient-optimal. Then the paper presents distributed algorithms built on top of this shared memory abstraction, which cope with up to t Byzantine processes. The simplicity of these algorithms constitutes a strong motivation for such a shared memory abstraction in the presence of Byzantine processes.
-
Reliable Shared Memory Abstractions on Top of Asynchronous t-Resilient Byzantine Message-passing Systems
2014Co-Authors: Damien Imbs, Michel Raynal, Sergio Rajsbaum, Julien StainerAbstract:This paper is on the construction and the use of a shared memory abstraction on top of an Asynchronous Message-passing system in which up to t processes may commit Byzantine failures. This abstraction consists of arrays of n single-writer/multi-reader atomic registers, where n is the number of processes. A distributed algorithm building such a shared memory abstraction it first presented. This algorithm assumes t < n/3, which is shown to be a necessary and sufficient condition for such a construction. Hence, the algorithm is resilient-optimal. Then the paper presents distributed algorithms built on top of this shared memory abstraction, which cope with up to t Byzantine processes. The simplicity of these algorithms constitutes a strong motivation for such a shared memory abstraction in the presence of Byzantine processes. For a lot of problems, algorithms are more difficult to design and prove correct in a Message-passing system than in a shared memory system. Using a protocol stacking methodology, the aim of the proposed abstraction is to allow an easier design (and proof) of distributed algorithm, when one has the underlying system is an Asynchronous Message-passing system prone to Byzantine failures.
