Showing 1 to 22 of 22 matching Articles
Results per page:
Export (CSV)
By
Castañeda, Armando; Imbs, Damien; Rajsbaum, Sergio; Raynal, Michel
Show all (4)
2 Citations
In the waitfree shared memory model substantial attention has been devoted to understanding the relative power of subconsensus tasks. Two important subconsensus families of tasks have been identified: kset agreement and Mrenaming. When 2 ≤ k ≤ n − 1 and n ≤ M ≤ 2n − 2, these tasks are more powerful than read/write registers, but not strong enough to solve consensus for two processes.
This paper studies the power of renaming with respect to set agreement. It shows that, in a system of n processes, nrenaming is strictly stronger than (n − 1)set agreement, but not stronger than (n − 2)set agreement. Furthermore, (n + 1)renaming cannot solve even (n − 1)set agreement. As a consequence, there are cases where set agreement and renaming are incomparable when looking at their power to implement each other.
more …
By
Rajsbaum, Sergio; Raynal, Michel
Due to the advent of multicore machines, shared memory distributed computing models taking into account asynchrony and process crashes are becoming more and more important. This paper visits models for these systems and analyses their properties from a computability point of view. Among them, the base snapshot model and the iterated model are particularly investigated. The paper visits also several approaches that have been proposed to model failures (mainly the waitfree model and the adversary model) and gives also a look at the BG simulation. The aim of this survey is to help the reader to better understand the power and limits of distributed computing shared memory models.
more …
By
Gafni, Eli; Rajsbaum, Sergio; Raynal, Michel; Travers, Corentin
Show all (4)
8 Citations
We introduce the (b,n)Committee Decision Problem (CD) – a generalization of the consensus problem. While set agreement generalizes consensus in terms of the number of decisions allowed, the CD problem generalizes consensus in the sense of considering many instances of consensus and requiring a processor to decide in at least one instance. In more detail, in the CD problem each one of a set of n processes has a (possibly distinct) value to propose to each one of a set of b consensus problems, which we call committees. Yet a process has to decide a value for at least one of these committees, such that all processes deciding for the same committee decide the same value. We study the CD problem in the context of a waitfree distributed system and analyze it using a combination of distributed algorithmic and topological techniques, introducing a novel reduction technique.
We use the reduction technique to obtain the following results. We show that the (2,3)CD problem is equivalent to the musical benches problem introduced by Gafni and Rajsbaum in [10], and both are equivalent to (2,3)set agreement, closing an open question left there. Thus, all three problems are waitfree unsolvable in a read/write shared memory system, and they are all solvable if the system is enriched with objects capable of solving (2,3)set agreement. While the previous proof of the impossibility of musical benches was based on the BorsukUlam (BU) Theorem, it now relies on Sperner’s Lemma, opening intriguing questions about the relation between BU and distributed computing tasks.
more …
By
Castañeda, Armando; Rajsbaum, Sergio; Raynal, Michel
7 Citations
Tasks and objects are two predominant ways of specifying distributed problems. A task specifies for each set of processes (which may run concurrently) the valid outputs of the processes. An object specifies the outputs the object may produce when it is accessed sequentially. Each one requires its own implementation notion, to tell when an execution satisfies the specification. For objects linearizability is commonly used, while for tasks implementation notions are less explored.
Sequential specifications are very convenient, especially important is the locality property of linearizability, which states that linearizable objects compose for free into a linearizable object. However, most wellknown tasks have no sequential specification. Also, tasks have no clear locality property.
The paper introduces the notion of intervalsequential object. The corresponding implementation notion of intervallinearizability generalizes linearizability. Intervallinearizability allows to specify any task. However, there are sequential oneshot objects that cannot be expressed as tasks, under the simplest interpretation of a task. The paper also shows that a natural extension of the notion of a task is expressive enough to specify any intervalsequential object.
more …
By
Imbs, Damien; Rajsbaum, Sergio; Raynal, Michel
7 Citations
Processes in a concurrent system need to coordinate using a shared memory or a messagepassing subsystem in order to solve agreement tasks such as, for example, consensus or set agreement. However, coordination is often needed to “break the symmetry” of processes that are initially in the same state, for example, to get exclusive access to a shared resource, to get distinct names or to elect a leader.
This paper introduces and studies the family of generalized symmetry breaking (GSB) tasks, that includes election, renaming and many other symmetry breaking tasks. Differently from agreement tasks, a GSB task is “inputless”, in the sense that processes do not propose values; the task only specifies the symmetry breaking requirement, independently of the system’s initial state (where processes differ only on their identifiers). Among various results characterizing the family of GSB tasks, it is shown that (non adaptive) perfect renaming is universal for all GSB tasks.
more …
By
Delporte, Carole; Fauconnier, Hugues; Rajsbaum, Sergio; Raynal, Michel
Show all (4)
An immediate snapshot object is a high level communication object, built on top of a read/write distributed system in which all except one processes may crash. It allows each process to write a value and obtains a set of pairs (process id, value) such that, despite process crashes and asynchrony, the sets obtained by the processes satisfy noteworthy inclusion properties.
Considering an nprocess model in which up to t processes are allowed to crash (tcrash system model), this paper is on the construction of tresilient immediate snapshot objects. In the tcrash system model, a process can obtain values from at least
$$(nt)$$
processes, and, consequently, timmediate snapshot is assumed to have the properties of the basic
$$(n1)$$
resilient immediate snapshot plus the additional property stating that each process obtains values from at least
$$(nt)$$
processes. The main result of the paper is the following. While there is a (deterministic)
$$(n1)$$
resilient algorithm implementing the basic
$$(n1)$$
immediate snapshot in an
$$(n1)$$
crash read/write system, there is no tresilient algorithm in a tcrash read/write model when
$$t\in [1\ldots (n2)]$$
. This means that, when
$$t<n1$$
, the notion of tresilience is inoperative when one has to implement timmediate snapshot for these values of t: the model assumption “at most
$$t<n1$$
processes may crash” does not provide us with additional computational power allowing for the design of a genuine tresilient algorithm (genuine meaning that such an algorithm would work in the tcrash model, but not in the
$$(t+1)$$
crash model). To show these results, the paper relies on wellknown distributed computing agreement problems such as consensus and kset agreement.
more …
By
Herlihy, Maurice; Rajsbaum, Sergio; Raynal, Michel; Stainer, Julien
Show all (4)
4 Citations
In a waitfree model any number of processes may crash. A process runs solo when it computes its local output without receiving any information from other processes, either because they crashed or they are too slow. While in waitfree sharedmemory models at most one process may run solo in an execution, any number of processes may have to run solo in an asynchronous waitfree messagepassing model.
This paper is on the computability power of models in which several processes may concurrently run solo. It first introduces a family of roundbased waitfree models, called the dsolo models, 1 ≤ d ≤ n, where up to d processes may run solo. The paper gives then a characterization of the colorless tasks that can be solved in each dsolo model. It also introduces the (d,ε)solo approximate agreement task, which generalizes εapproximate agreement, and proves that (d,ε)solo approximate agreement can be solved in the dsolo model, but cannot be solved in the (d + 1)solo model. The paper studies also the relation linking dset agreement and (d,ε)solo approximate agreement in asynchronous waitfree messagepassing systems.
These results establish for the first time a hierarchy of waitfree models that, while weaker than the basic read/write model, are nevertheless strong enough to solve nontrivial tasks.
more …
By
Friedman, Roy; Mostéfaoui, Achour; Rajsbaum, Sergio; Raynal, Michel
Show all (4)
1 Citations
The Consensus problem lies at the heart of many distributed computing problems one has to solve when designing reliable applications on top of unreliable distributed asynchronous systems. There is a large literature where theoretical and practical aspects of this problem are studied1, that can be informally stated in terms of three requirements. Each process proposes a value, and has to decide on a value (termination) such that there is a single decided value (agreement), and the decided value is a proposed value (validity). One of the most fundamental impossibility results in distributed computing says that this apparently simple problem has no deterministic solution in an asynchronous system even if only one process may crash [3.9].To circumvent this impossibility, known as FLP, two main approaches have been investigated. One of them consists of relaxing the requirements of the problem, by either allowing for probabilistic solutions (e.g., [3.4]), or for approximate solutions (εagreement [3.8], or kset agreement [3.6]). Another approach consists of enriching the system with synchrony assumptions until they allow the problem to be solved [3.7]. This approach has been abstracted in the notion of unreliable failure detectors [3.5]. There have also been studies of hybrid approaches, like combining failure detection with randomization [3.2], 3.21].
more …
By
Afek, Yehuda; Gafni, Eli; Rajsbaum, Sergio; Raynal, Michel; Travers, Corentin
Show all (5)
8 Citations
We address the problem of solving a task T=(T_{1},...T_{m}) (called (m,1)BG), in which a processor returns in an arbitrary one of m simultaneous consensus subtasks T_{1},...T_{m}. Processor p_{i} submits to T an input vector of proposals (prop_{i,1},...,prop_{i,m}), one entry per subtask, and outputs, from just one subtask ℓ, a pair (ℓ, prop_{j,l}) for some j. All processors that output at ℓ output the same proposal.
Let d be a bound on the number of distinct input vectors that may be submitted to T. For example, d=3 if Democrats always vote Democrats across the board, and similarly for Republicans and Libertarians. A waitfree algorithm that immaterial of the number of processors solves T provided m ≥d is presented. In addition, if in each T_{j} we allow kset consensus rather than consensus, i.e., for each ℓ, the outputs satisfy {j  prop_{j , ℓ}} ≤k, then the same algorithm solves T if m ≥⌈d/k ⌉.
What is the power of T=(T_{1},...,T_{m}) when given as a subroutine, to be used by any number of processors with any number of input vectors? Obviously, T solves mset consensus since each processor p_{i} can submit the vector (id_{i},id_{i},...id_{i}), but can mset consensus solve T? We show it does, and thus simultaneous consensus is a new characterization of setconsensus.
Finally, what if each T_{j} is just a binaryconsensus rather than consensus? Then we get the novel problem that was recently introduced of the CommitteeDecision. It was shown that for 3 processors and m=2, the simultaneous binaryconsensus is equivalent to (3,2)set consensus. Here, using a variation of our waitfree algorithms mentioned above, we show that a task, in which a processor is required to return in one of m simultaneous binaryconsensus subtasks, when used by n processors, is equivalent to (n,m)set consensus. Thus, while setconsensus unlike consensus, has no binary version, now that we characterize mset consensus through simultaneous consensus, the notion of binarysetconsensus is well defined. We have then showed that binarysetconsensus is equivalent to set consensus as it was with consensus.
more …
By
Mostefaoui, Achour; Rajsbaum, Sergio; Raynal, Michel
6 Citations
In the context of a system made up of n processes where at most t can crash, the conditionbased approach studies restrictions on the inputs of a distributed problem, called conditions, that make it solvable, or easier to solve (in case it is solvable without restricting its inputs). Previous work studied conditions for consensus and other agreement problems, mostly for asynchronous systems. This paper considers the conditionbased approach for consensus in synchronous systems, and establishes a bridge between the asynchronous and synchronous models, with a hierarchy
$ {\cal S}_t^{[t]}\subset\cdots\subset {\cal S}_t^{[0]}\subset\cdots\subset {\cal S}_t^{[t]} $
where
${\cal S}_t^{[t]}$
includes all conditions (and in particular the trivial one made up of all possible input vectors). For a condition
$C \in{\cal S}_t^{[d]}$
, –t ≤ d ≤ t, we have:
For values of d ≤ 0 we have the hierarchy of conditions (we introduced in PODC’01) where consensus is solvable by more and more efficient protocols in an asynchronous system with t failures, as we go from d=0 to d=–t.
For values of d>0 consensus is not solvable in an asynchronous system with t failures, but it is solvable in a synchronous system with more and more rounds, as we go from d=1 (two rounds) to d=t (t+1 rounds).
d=0 is the borderline case where consensus is solvable in an asynchronous system with t failures, and optimally in a synchronous system (we proved this in DISC’03).
The two main results of this paper are proving the second item above. For the upper bound, the paper presents a generic synchronous earlydeciding uniform consensus protocol. When instantiated with a condition
$C \in {\cal S}_t^{[d]}$
, 1≤
d ≤
t<
n, the processes decide in at most min (
α + 1,
f + 2,
t + 1) rounds, where
f is the number of actual crashes, and
α=
d if the input vector belongs to
C, or
α=+∞ otherwise. The paper establishes a corresponding lower bound stating that
d+1 rounds are necessary to get a decision when the input vector belong to
C.
more …
By
Rajsbaum, Sergio; Raynal, Michel; Travers, Corentin
13 Citations
In the Iterated Immediate Snapshot model (
${\mathit{IIS}}$
) the memory consists of a sequence of oneshot Immediate Snapshot (
$\mathit{IS}$
) objects. Processes access the sequence of
$\mathit{IS}$
objects, onebyone, asynchronously, in a waitfree manner; any number of processes can crash. Its interest lies in the elegant recursive structure of its runs, hence of the ease to analyze it round by round. In a very interesting way, Borowsky and Gafni have shown that the
${\mathit{IIS}}$
model and the read/write model are equivalent for the waitfree solvability of decision tasks.
This paper extends the benefits of the
$\mathit{IIS}$
model to partially synchronous systems. Given a shared memory model enriched with a failure detector, what is an equivalent
$\mathit{IIS}$
model? The paper shows that an elegant way of capturing the power of a failure detector and other partially synchronous systems in the
${\mathit{IIS}}$
model is by restricting appropriately its set of runs, giving rise to the Iterated Restricted Immediate Snapshot model (
$\mathit{IRIS}$
).
more …
By
Mostefaoui, Achour; Rajsbaum, Sergio; Raynal, Michel
14 Citations
The conditionbased approach studies restrictions on the inputs to a distributed problem, called conditions, that facilitate its solution. Previous work considered mostly the asynchronous model of computation. This paper studies conditions for consensus in a synchronous system where processes can fail by crashing. It describes a full classification of conditions for consensus, establishing a continuum between the asynchronous and synchronous models, with the following hierarchy
$${\cal S}_t^{[t]}\subset\cdots\subset {\cal S}_t^{[0]}\subset\cdots\subset {\cal S}_t^{[t]}$$
where
$${\cal S}_t^{[t]}$$
includes all conditions (and in particular the trivial one made up of all possible input vectors). For a condition
$$C \in{\cal S}_t^{[d]}$, $t \leq d \leq t$$
, we have:
For values of
$$d \leq 0$$
consensus is solvable in an asynchronous system with t failures, and we obtain the known hierarchy of conditions that allows solving asynchronous consensus with more and more efficient protocols as we go from d = 0 to d = −t.
For values of
$$d \leq 0$$
consensus is solvable in an asynchronous system with t failures, and we obtain the known hierarchy of conditions that allows solving asynchronous consensus with more and more efficient protocols as we go from d = 0 to d = −t.
For values of d<0 consensus is known not solvable in an asynchronous system with t failures, but we obtain a hierarchy of conditions that allows solving synchronous consensus with protocols that can take more and more rounds, as we go from d = 0 to d = t.
d = 0 is the borderline case where consensus can be solved in an asynchronous system with t failures, and can be solved optimally in a synchronous system.
After having established the complete hierarchy, the paper concentrates on the two last items:
$$0\leq d\leq t$$
. The main result is that the necessary and sufficient number of rounds needed to solve uniform consensus for a condition
$$C \in {\cal S}_t^{[d]}$$
(such that
$$C\notin {\cal S}_t^{[d1]}$$
) is d +1.
In more detail, the paper presents a generic synchronous earlydeciding uniform consensus protocol that enjoys the following properties. Let f be the number of actual crashes, I the input vector and
$$C \in {\cal S}_t^{[d]}$$
the condition the protocol is instantiated with. The protocol terminates in two rounds when
$$I\in C$$
and
$$f\leq td$$
, and in at most d +1 rounds when
$$I\in C$$
and
$$f>td$$
. (It also terminates in one round when
$$I\in C$$
and
$$d=f=0$$
.) Moreover, whether I belongs or not to C, no process requires more than min
$$(t+1,f+2)$$
rounds to decide. The paper then proves a corresponding lower bound stating that at least d +1 rounds are necessary to get a decision in the worst case when
$$I\in C$$
(for
$$C \in {\cal S}_t^{[d]}$$
and
$$C \notin {\cal S}_t^{[d1]}$$
).
more …
By
Imbs, Damien; Rajsbaum, Sergio; Raynal, Michel; Stainer, Julien
Show all (4)
1 Citations
This paper is on the construction and the use of a shared memory abstraction on top of an asynchronous messagepassing system in which up to t processes may commit Byzantine failures. This abstraction consists of arrays of n singlewriter/multireader 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 resilientoptimal. 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 messagepassing 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 algorithms, when the underlying system is an asynchronous messagepassing system prone to Byzantine failures.
more …
By
Mostefaoui, Achour; Rajsbaum, Sergio; Raynal, Michel
8 Citations
The conditionbased approach to solve consensus has initially been developed in the context of asynchronous systems. It identifies a class of acceptable conditions on the set of input vectors that, when satisfied by the actual input vector, are exactly the conditions that allow to solve consensus despite up to t faulty processes. This paper investigates the use of conditions to solve consensus in synchronous systems prone to process crash failures. It first shows that for any acceptable condition there is a conditionbased protocol solving uniform consensus that enjoys the following property: when the input vector belongs to the condition, it terminates in a single round if no process crashes, and in two rounds otherwise. When the input vector does not belong to the condition, the actual number of rounds is upper bounded by t+1 (it actually depends on both the crash pattern and the input vector). The paper then extends the previous protocol to combine early decision with the conditionbased approach. It presents a general protocol that enjoys the previous properties (decision in one or two rounds) when the input vector belongs to the condition and terminates in at most (t + 1, f + 2) rounds when the input vector does not belong to the condition (where f is the actual number of faulty processes). Finally, the paper presents corresponding matching lower bounds. It shows that acceptable conditions are the only ones for which a consensus protocol can enjoy the previous properties.
more …
By
Mostefaoui, Achour; Rajsbaum, Sergio; Raynal, Michel
Abstract
In the context of a system made up of n processes where at most t can crash, the conditionbased approach studies restrictions on the inputs of a distributed problem, called conditions, that make it solvable, or easier to solve (in case it is solvable without restricting its inputs). Previous work studied conditions for consensus and other agreement problems, mostly for asynchronous systems. This paper considers the conditionbased approach for consensus in synchronous systems, and establishes a bridge between the asynchronous and synchronous models, with a hierarchy $ {\cal S}_t^{[t]}\subset\cdots\subset {\cal S}_t^{[0]}\subset\cdots\subset {\cal S}_t^{[t]} $ where ${\cal S}_t^{[t]}$ includes all conditions (and in particular the trivial one made up of all possible input vectors). For a condition $C \in{\cal S}_t^{[d]}$, –t ≤ d ≤ t, we have:
For values of d ≤ 0 we have the hierarchy of conditions (we introduced in PODC’01) where consensus is solvable by more and more efficient protocols in an asynchronous system with t failures, as we go from d=0 to d=–t.
For values of d>0 consensus is not solvable in an asynchronous system with t failures, but it is solvable in a synchronous system with more and more rounds, as we go from d=1 (two rounds) to d=t (t+1 rounds).
d=0 is the borderline case where consensus is solvable in an asynchronous system with t failures, and optimally in a synchronous system (we proved this in DISC’03).
The two main results of this paper are proving the second item above. For the upper bound, the paper presents a generic synchronous earlydeciding uniform consensus protocol. When instantiated with a condition $C \in {\cal S}_t^{[d]}$, 1≤
d ≤
t<
n, the processes decide in at most $\min(\alpha+1,f+2,t+1)$ rounds, where
f is the number of actual crashes, and
α=
d if the input vector belongs to
C, or
α=+∞ otherwise. The paper establishes a corresponding lower bound stating that
d+1 rounds are necessary to get a decision when the input vector belong to
C.
Keywords: Condition, Consensus, Early deciding, Input Vector, Message passing, Process crash failure, Synchronous distributed system.
more …
By
Castañeda, Armando; Rajsbaum, Sergio; Raynal, Michel
1 Citations
The predominant notion for specifying problems to study distributed computability are tasks. Notable examples of tasks are consensus, set agreement, renaming and commitadopt. The theory of task solvability is welldeveloped using topology techniques and distributed simulations. However, concurrent computing problems are usually specified by objects. Tasks and objects differ in at least two ways. While a task is a oneshot problem, an object, such as a queue or a stack, typically can be invoked multiple times by each process. Also, a task, defined in terms of sets, specifies its responses when invoked by each set of processes concurrently, while an object, defined in terms of sequences, specifies the outputs the object may produce when it is accessed sequentially.
In a previous paper we showed how tasks can be used to specify oneshot objects (where each process can invoke only one operation, only once). In this paper we show how the notion of tasks can be extended to model any object. A potential benefit of this result is the use of topology, and other distributed computability techniques to study longlived objects.
more …
By
DelporteGallet, Carole; Fauconnier, Hugues; Rajsbaum, Sergio; Raynal, Michel
Show all (4)
1 Citations
Distributed snapshots, as introduced by Chandy and Lamport in the context of asynchronous failurefree messagepassing 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 crashprone read/write distributed systems are totally ordered, which greatly simplify their use by upper layer applications.
In order to benefit from shared memory snapshot objects, it is possible to simulate a read/write shared memory on top of an asynchronous crashprone messagepassing system, and build then snapshot objects on top of it. This algorithm stacking is costly in both time and messages. To circumvent this drawback, this paper presents algorithms building snapshot objects directly on top of asynchronous crashprone messagepassing system. “Directly” means here “without building an intermediate layer such as a read/write shared memory”. To the authors knowledge, the proposed algorithms are the first providing such constructions. Interestingly enough, these algorithms are efficient and relatively simple.
more …
By
Castañeda, Armando; Delporte, Carole; Fauconnier, Hugues; Rajsbaum, Sergio; Raynal, Michel
Show all (5)
When considering distributed computing, reliable messagepassing synchronous systems on the one side, and asynchronous failureprone sharedmemory systems on tyhe other side, remain two quite independently studied ends of the reliability/asynchrony spectrum. The concept of locality of a computation is central to the first one, while the concept of waitfreedom is central to the second one. The paper proposes a new
$$\mathcal{DECOUPLED}$$
model in an attempt to reconcile these two worlds. It consists of a synchronous and reliable communication graph of nnodes, and on top a set of asynchronous crashprone processes, each attached to a communication node.
To illustrate the
$$\mathcal{DECOUPLED}$$
model, the paper presents an asynchronous 3coloring algorithm for the processes of a ring. From the processes point of view, the algorithm is waitfree. From a locality point of view, each process uses information only from processes at distance
$$O(\log ^* n)$$
from it. This local waitfree algorithm is based on an extension of the classical Cole and Vishkin vertex coloring algorithm in which the processes are not required to start simultaneously.
more …
By
Afek, Yehuda; Gafni, Eli; Rajsbaum, Sergio; Raynal, Michel; Travers, Corentin
Show all (5)
15 Citations
This paper introduces and investigates the ksimultaneous consensus task: each process participates at the same time in k independent consensus instances until it decides in any one of them. It is shown that the ksimultaneous consensus task is equivalent to the kset agreement task in the waitfree read/write shared memory model, and furthermore ksimultaneous consensus possesses properties that kset does not. In particular we show that the multivalued version and the binary version of the ksimultaneous consensus task are waitfree equivalent. These equivalences are independent of the number of processes. Interestingly, this provides us with a new characterization of the kset agreement task that is based on the fundamental binary consensus problem.
more …
By
Mostefaoui, Achour; Rajsbaum, Sergio; Raynal, Michel; Travers, Corentin
Show all (4)
12 Citations
Solving agreement problems deterministically, such as consensus and kset agreement, in asynchronous distributed systems prone to an unbounded number of process failures has been shown to be impossible. To circumvent this impossibility, unreliable failure detectors for the crash failure model have been widely studied. These are oracles that provide information on failures. The exact nature of such information is defined by a set of abstract properties that a particular class of failure detectors satisfy. The weakest class of such failure detectors that allow to solve consensus is Ω. This paper considers failure detector classes from the literature that solve kset agreement in the crash failure model, and studies their relative power. It shows that the family of failure detector classes
$${\diamond\mathcal{S}_x}$$
(1 ≤ x ≤ n), and
$${\diamond \psi^y}$$
(0 ≤ y ≤ n), can be “added” to provide a failure detector of the class Ω^{z} (1 ≤ z ≤ n, a generalization of Ω). It also characterizes the power of such an “addition”, namely,
$${\diamond {\mathcal S}_x +\diamond \psi^y\rightsquigarrow\Omega^z \Leftrightarrow x+y+z > t+1}$$
,
$${\diamond \psi^y}$$
can construct Ω^{z} iff y + z > t, and
$${\diamond {\mathcal S}_x}$$
can construct Ω^{z} iff x + z > t + 1, where t is the maximum number of processes that can crash in a run. As an example, the paper shows that, while
$${\diamond {\mathcal S}_{t}}$$
allows solving 2set agreement (but not consensus) and
$${\diamond \psi^{1}}$$
allows solving tset agreement (but not (t − 1)set agreement), a system with failure detectors of both classes can solve consensus for any value of t. More generally, the paper studies the failure detector classes
$${\diamond {\mathcal S}_x}$$
,
$${\diamond \psi^y}$$
and Ω^{z}, and shows which reductions among these classes are possible and which are not. The paper also presents a messagepassing Ω^{k}based kset agreement protocol and shows that Ω^{k} is not enough to solve (k − 1)set agreement. In that sense, it can be seen as a step toward the characterization of the weakest failure detector class that allows solving the kset agreement problem.
more …
By
Castañeda, Armando; Moses, Yoram; Raynal, Michel; Roy, Matthieu
Show all (4)
1 Citations
Consensus is the most basic agreement problem encountered in faulttolerant distributed computing: each process proposes a value and nonfaulty processes must agree on the same value, which has to be one of the proposed values. While this problem is impossible to solve in asynchronous systems prone to process crash failures, it can be solved in synchronous (roundbased) systems where all but one process might crash in any execution. It is wellknown that
$$(t+1)$$
rounds are necessary and sufficient in the worst case execution scenario for the processes to decide and stop executing, where
$$t < n$$
is a system parameter denoting the maximum number of allowed process crashes and n denotes the number of processes in the system.
Early decision and stopping considers the case where
$$f<t$$
processes actually crash, f not being known by processes. It has been shown that the number of rounds that have to be executed in the worst case is then
$$\mathsf{min}(f+2,t+1)$$
. Following Castañeda, Gonczarowski and Moses (DISC 2014), the paper shows that this value is an upper bound attained only in worst execution scenarios. To this end, it investigates a sequence of three early deciding/stopping predicates
$$P_1=P_\mathsf{count}$$
,
$$P_2=P_\mathsf{dif}$$
and
$$P_3=P_\mathsf{pref0}$$
, of increasing power, which differ in the information obtained by the processes from the actual failure, communication and data pattern. It is shown that each predicate
$$P_i$$
is better than the previous one
$$P_{i1}$$
,
$$i\in \{2,3\}$$
, in the sense that there are executions where
$$P_i$$
allows processes to reach a decision earlier than
$$P_{i1}$$
, while
$$P_{i1}$$
never allows a process to decide earlier than
$$P_i$$
. Moreover,
$$P_3=P_\mathsf{pref0}$$
is an unbeatable predicate in the sense that it cannot be strictly improved: if there is an early deciding/stopping predicate
$$P'$$
that improves the decision time of a process with respect to
$$P_\mathsf{pref0}$$
in a given execution, then there is at least one execution in which a process decides with
$$P'$$
strictly later than with
$$P_\mathsf{pref0}$$
.
more …
By
Castañeda, Armando; DelporteGallet, Carole; Fauconnier, Hugues; Rajsbaum, Sergio; Raynal, Michel
Show all (5)
When considering distributed computing, reliable messagepassing synchronous systems on the one side, and asynchronous failureprone sharedmemory systems on the other side, remain two quite independently studied ends of the reliability/asynchrony spectrum. The concept of locality of a computation is central to the first one, while the concept of waitfreedom is central to the second one. The paper proposes a new DECOUPLED model in an attempt to reconcile these two worlds. It consists of a synchronous and reliable communication graph of nnodes, and on top a set of asynchronous crashprone processes, each attached to a communication node. To illustrate the DECOUPLED model, the paper presents an asynchronous 3coloring algorithm for the processes of a ring. From the processes point of view, the algorithm is waitfree. From a locality point of view, each process uses information only from processes at distance
$O(\log ^{*} n)$
from it. This local waitfree algorithm is based on an extension of the classical Cole and Vishkin’s vertex coloring algorithm in which the processes are not required to start simultaneously.
more …
