Showing 1 to 61 of 61 matching Articles
Results per page:
Export (CSV)
By
Imbs, Damien; Rajsbaum, Sergio; Valle, Adrián
Post to Citeulike
The basic read/write shared memory model where asynchronous and crash prone processes communicate to solve a task is difficult to analyze. A more structured model is the iterated immediate snapshot model (IIS), where processes execute communication closed rounds. In each round, they communicate using read/write registers that cannot be reused in later rounds. It is known that a task is solvable in the IIS model if and only if it is solvable in the basic read/write model. Both models are also equivalent when, in addition to read/write registers, processes also have access to stronger communication objects called 01tasks.
This paper extends further the task computability equivalence presenting a simulation that includes xconsensus objects, which solve consensus among up to x processes. The simulation implies that an iterated model where processes communicate through a sequence consisting only of xconsensus objects is equivalent to the basic shared memory model augmented with xconsensus objects.
more …
By
Castañeda, Armando; Imbs, Damien; Rajsbaum, Sergio; Raynal, Michel
Show all (4)
Post to Citeulike
1 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
Post to Citeulike
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
Post to Citeulike
3 Citations
In roundbyround models of distributed computing processes run in a sequence of (synchronous or asynchronous) rounds. The advantage of the roundbyround approach is that invariants established in the first round are preserved in later rounds. An elegant asynchronous roundbyround shared memory model, is the iterated snapshots model (IS). Instead of the snapshots model where processes share an array m[·] that can be accessed any number of times, indexed by process ID, where P_{i} writes to m[i] and can take a snapshot of the entire array, we have processes share a twodimensional array m[·,·], indexed by iteration number and by process ID, where P_{i} in iteration r writes once to m[r, i] and takes one snapshot of row r, m[r,·]. The IS model lends itself more easily to combinatorial analysis. However, to show that whenever a task is impossible in the IS model the task is impossible in the snapshots model, a simulation is needed. Such a simulation was presented by Borowsky and Gafni in PODC97; namely, it was shown how to take a waitfree protocol for the snapshots model, and transform it into a protocol for the IS model, solving the same task.
In this paper we present a new simulation from the snapshots model to the IS model, and show that it can be extended to work with models stronger that waitfree. The main contribution is to show that the simulation can work with models that have access to certain communication objects, called 01tasks. This extends the result of Gafni, Rajsbaum and Herlihy in DISC’2006 stating that renaming is strictly weaker than set agreement from the IS model to the usual noniterated waitfree read/write shared memory model.
We also show that our simulation works with tresilient models and the more general dependent process failure model of Junqueira and Marzullo. This version of the simulation extends previous results by Herlihy and Rajsbaum in PODC’2010 and DISC’2010 about the topological connectivity of a protocol complex in an iterated dependent process failure model, to the corresponding noniterated model.
more …
By
Conde, Rodolfo; Rajsbaum, Sergio
Post to Citeulike
1 Citations
In the consensus task each process proposes a value, and all correct processes have to decide the same value. In addition, validity requires that the decided value is a proposed value. Afek, Gafni and Lieber (DISC’09) introduced the safeconsensus task, by weakening the validity requirement: if the first process to invoke the task returns before any other process invokes it, then it outputs its input; otherwise, when there is concurrency, the consensus output can be arbitrary, not even the input of any process. Surprisingly, they showed that safeconsensus is equivalent to consensus, in a system where any number of processes can crash (e.g., waitfree).
We show that safeconsensus is nevertheless a much weaker communication primitive, in the sense that any waitfree implementation of consensus requires
$\binom{n}{2}$
safeconsensus blackboxes, and this bound is tight. The lower bound proof uses connectivity arguments based on subgraphs of Johnson graphs. For the upper bound protocol that we present, we introduce the g2coalitionsconsensus task, which may be of independent interest. We work in an iterated model of computation, where the processes repeatedly: write their information to a (fresh) shared array, invoke safeconsensus boxes and snapshot the contents of the shared array.
more …
By
Fraigniaud, Pierre; Ilcinkas, David; Rajsbaum, Sergio; Tixeuil, Sébastien
Show all (4)
Post to Citeulike
3 Citations
We consider the task of exploring graphs with anonymous nodes by a team of noncooperative robots, modeled as finite automata. For exploration to be completed, each edge of the graph has to be traversed by at least one robot. In this paper, the robots have no a priori knowledge of the topology of the graph, nor of its size, and we are interested in the amount of memory the robots need to accomplish exploration, We introduce the socalled reduced automata technique, and we show how to use this technique for deriving several space lower bounds for exploration. Informally speaking, the reduced automata technique consists in reducing a robot to a simpler form that preserves its “core” behavior on some graphs. Using this technique, we first show that any set of q≥ 1 noncooperative robots, requires
$\Omega(\log(\frac{n}{q}))$
memory bits to explore all nnode graphs. The proof implies that, for any set of qKstate robots, there exists a graph of size O(qK) that no robot of this set can explore, which improves the O(K^{O(q)}) bound by Rollik (1980). Our main result is an application of this latter result, concerning terminating graph exploration with one robot, i.e., in which the robot is requested to stop after completing exploration. For this task, the robot is provided with a pebble, that it can use to mark nodes (without such a marker, even terminating exploration of cycles cannot be achieved). We prove that terminating exploration requires Ω(log n) bits of memory for a robot achieving this task in all nnode graphs.
more …
By
Gafni, Eli; Rajsbaum, Sergio; Raynal, Michel; Travers, Corentin
Show all (4)
Post to Citeulike
3 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
Post to Citeulike
5 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
Post to Citeulike
5 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)
Post to Citeulike
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)
Post to Citeulike
3 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
Fraigniaud, Pierre; Rajsbaum, Sergio; Travers, Corentin
Post to Citeulike
1 Citations
The notion of deciding a distributed language
$$\mathcal {L} $$
is of growing interest in various distributed computing settings. Each process
$$p_i$$
is given an input value
$$x_i$$
, and the processes should collectively decide whether their set of input values
$$x=(x_i)_i$$
is a valid state of the system w.r.t. to some specification, i.e., if
$$x\in \mathcal {L} $$
. In nondeterministic distributed decision each process
$$p_i$$
gets a local certificate
$$c_i$$
in addition to its input
$$x_i$$
. If the input
$$x\in \mathcal {L} $$
then there exists a certificate
$$c=(c_i)_i$$
such that the processes collectively accept x, and if
$$x\not \in \mathcal {L} $$
, then for every c, the processes should collectively reject x. The collective decision is expressed by the set of opinions emitted by the processes.
In this paper we study nondeterministic distributed decision in systems where asynchronous processes may crash. It is known that the number of opinions needed to deterministically decide a language can grow with n, the number of processes in the system. We prove that every distributed language
$$\mathcal {L} $$
can be nondeterministically decided using only three opinions, with certificates of size
$$\lceil \log \alpha (n)\rceil +1$$
bits, where
$$\alpha $$
grows at least as slowly as the inverse of the Ackerman function. The result is optimal, as we show that there are distributed languages that cannot be decided using just two opinions, even with arbitrarily large certificates.
To prove our upper bound, we introduce the notion of distributed encoding of the integers, that provides an explicit construction of a long bad sequence in the wellquasiordering
$$(\{0,1\}^*,\le _*)$$
controlled by the successor function. Thus, we provide a new class of applications for wellquasiorderings that lies outside logic and complexity theory. For the lower bound we use combinatorial topology techniques.
more …
By
DelporteGallet, Carole; Fauconnier, Hugues; Rajsbaum, Sergio; Yanagisawa, Nayuta
Show all (4)
Post to Citeulike
One of the central questions in distributed computability is characterizing the tasks that are solvable in a given system model. In the anonymous case, where processes have no identifiers and communicate through multiwriter/multireader registers, there is a recent topological characterization (Yanagisawa 2017) of the colorless tasks that are solvable when any number of asynchronous processes may crash. In this paper, we consider the case where at most t asynchronous processes may crash, where
$$1\le t<n$$
. We prove that a colorless task is tresilient solvable anonymously if and only if it is tresilient solvable nonanonymously. We obtain our results through various reductions and simulations that explore how to extend techniques for nonanonymous computation to anonymous one.
more …
By
Gafni, Eli; Rajsbaum, Sergio
Post to Citeulike
3 Citations
We propose the musical benches problem to model a waitfree coordination difficulty that is orthogonal to previously studied ones such as agreement or symmetry breaking (leader election or renaming). A bench is the usual binary consensus problem for 2 processes. Assume n+1 processes want to sit in n benches as follows. Each one starts with a preference, consisting of a bench and one place (left or right) in the bench where it wants to sit. Each process should produce as output the place of the bench where it decides to sit. It is required that no two processes sit in different places of the same bench. Upon the observance of a conflict in one of the benches an undecided process can “abandon” its initial bench and place and try to sit in another bench at another place.
The musical benches problem is so called because processes jump from bench to bench trying to find one in which they may be alone or not in conflict with one another. If at most one process starts in each bench, the problem is trivially solvable– each process stays in its place. We show that if there is just one bench where two processes rather than one, start, the problem is waitfree unsolvable in read/write shared memory. This impossibility establishes a new connection between distributed computing and topology, via the BorsukUlam theorem.
The musical benches problem seems like just a collection of consensus problems, where by the pigeon hole principle at least one of them will have to be solved by two processes. Consequently, one is tempted to try to find a bivalency impossibility proof of the FLP style. Our second result shows that there is no such proof: We present an algorithm to solve the musical benches problem using set agreement, a primitive stronger than read/write registers, but weaker than consensus. Thus, an FLPstyle impossibility for musical benches will imply an FLPstyle impossibility of setconsensus.
The musical benches problem can be generalized by considering benches other than consensus, such as set agreement or renaming, leading to a very interesting class of new problems.
more …
By
DelporteGallet, Carole; Fauconnier, Hugues; Rajsbaum, Sergio; Yanagisawa, Nayuta
Show all (4)
Post to Citeulike
We consider a system of n anonymous processes communicating through multiwriter/multireader (MWMR) registers. A weakset object is a particularly interesting communication abstraction for anonymous processes; it may be seen as the equivalent of an atomic snapshot object in an anonymous system. It can be accessed through two operations:
$$\textsc {add}()$$
and
$$\textsc {get}()$$
. Intuitively, an
$$\textsc {add}(v)$$
operation puts value v in the set represented by the object, while a
$$\textsc {get}()$$
operation returns the contents of the set. The paper describes a waitfree atomic implementation of a weakset object shared by n anonymous processes using 3n MWMR registers. The description of the algorithm is incremental. The paper first presents an implementation that is waitfree only for the
$$\textsc {Get}()$$
operations, using 2n MWMR registers. Then it describes an implementation that is waitfree for the
$$\textsc {Get}()$$
and the
$$\textsc {Add}()$$
operations, using
$$3n+1$$
MWMR registers, and finally it is improved to an implementation using 3n MWMR registers. In addition, a lowerbound of n registers for the implementation of a waitfree atomic weakset is proved.
more …
By
Rajsbaum, Sergio
Post to Citeulike
3 Citations
In centralized computing we can compute a function composing a sequence of elementary functions, where the output of the ith function in the sequence is the input to the i + 1st function in the sequence. This computation is done without persistent registers that could store information of the outcomes of these function invocations. In distributed computing, a task is the analogue of a function. An iterated model is defined by some base set of tasks. Processes invoke a sequence of tasks from this set. Each process invokes the i + 1st task with its output from the ith task. Processes access the sequence of tasks, onebyone, in the same order, and asynchronously. Any number of processes can crash. In the most basic iterated model the base tasks are read/write registers. Previous papers have studied this and other iterated models with more powerful base tasks or enriched with failure detectors, which have been useful to prove impossibility results and to design algorithms, due to the elegant recursive structure of the runs. This talk surveys results in this area, contributed mainly by Borowsky, Gafni, Herlihy, Raynal, Travers and the author.
more …
By
Gafni, Eli; Rajsbaum, Sergio
Post to Citeulike
13 Citations
The benefits of developing algorithms via recursion are well known. However, little use of recursion has been done in distributed algorithms, in spite of the fact that recursive structuring principles for distributed systems have been advocated since the beginning of the field. We present several distributed algorithms in a recursive form, which makes them easier to understand and analyze. Also, we expose several interesting issues arising in recursive distributed algorithms. Our goal is to promote the use and study of recursion in distributed algorithms.
more …
By
Friedman, Roy; Mostéfaoui, Achour; Rajsbaum, Sergio; Raynal, Michel
Show all (4)
Post to Citeulike
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
Fraigniaud, Pierre; Gafni, Eli; Rajsbaum, Sergio; Roy, Matthieu
Show all (4)
Post to Citeulike
2 Citations
The state machine approach is a wellknown technique for building distributed services requiring high performance and high availability, by replicating servers, and by coordinating client interactions with server replicas using consensus. Indulgent consensus algorithms exist for realistic eventually partially synchronous models, that never violate safety and guarantee liveness once the system becomes synchronous. Unavoidably, these algorithms may never terminate, even when no processor crashes, if the system never becomes synchronous.
This paper proposes a mechanism similar to state machine replication, called RCsimulation, that can always make progress, even if the system is never synchronous. Using RCsimulation, the quality of the service will adjust to the current level of asynchrony of the network — degrading when the system is very asynchronous, and improving when the system becomes more synchronous. RCsimulation generalizes the state machine approach in the following sense: when the system is asynchronous, the system behaves as if k + 1 threads were running concurrently, where k is a function of the asynchrony.
In order to illustrate how the RCsimulation can be used, we describe a longlived renaming implementation. By reducing the concurrency down to the asynchrony of the system, RCsimulation enables to obtain renaming quality that adapts linearly to the asynchrony.
more …
By
Fraigniaud, Pierre; Rajsbaum, Sergio; Roy, Matthieu; Travers, Corentin
Show all (4)
Post to Citeulike
1 Citations
This paper carries on the effort to bridging runtime verification with distributed computability, studying necessary conditions for monitoring failure prone asynchronous distributed systems. It has been recently proved that there are correctness properties that require a large number of opinions to be monitored, an opinion being of the form true, false, perhaps, probably true, probably no, etc. The main outcome of this paper is to show that this large number of opinions is not an artifact induced by the existence of artificial constructions. Instead, monitoring an important class of properties, requiring processes to produce at most k different values does require such a large number of opinions. Specifically, our main result is a proof that it is impossible to monitor ksetagreement in an nprocess system with fewer than min {2k,n} + 1 opinions. We also provide an algorithm to monitor ksetagreement with min {2k,n} + 1 opinions, showing that the lower bound is tight.
more …
By
Fraigniaud, Pierre; Rajsbaum, Sergio; Travers, Corentin
Post to Citeulike
10 Citations
Decentralized runtime monitoring involves a set of monitors observing the behavior of system executions with respect to some correctness property. It is generally assumed that, as soon as a violation of the property is revealed by any of the monitors at runtime, some recovery code can be executed for bringing the system back to a legal state. This implicitly assumes that each monitor produces a binary opinion, true or false, and that the recovery code is launched as soon as one of these opinions is equal to false. In this paper, we formally prove that, in a failureprone asynchronous computing model, there are correctness properties for which there is no such decentralized monitoring. We show that there exist some properties which, in order to be monitored in a waitfree decentralized manner, inherently require that the monitors produce a number of opinions larger than two. More specifically, our main result is that, for every k, 1 ≤ k ≤ n, there exists a property that requires at least k opinions to be monitored by n monitors. We also present a corresponding distributed monitor using at most k + 1 opinions, showing that our lower bound is nearly tight.
more …
By
Herlihy, Maurice; Rajsbaum, Sergio
Post to Citeulike
3 Citations
Roughly speaking, a simplicial complex is shellable if it can be constructed by gluing a sequence of nsimplexes to one another along (n − 1)faces only. Shellable complexes have been studied in the combinatorial topology literature because they have many nice properties.
It turns out that many standard models of concurrent computation can be captured either as shellable complexes, or as the simple union of shellable complexes. We consider general adversaries in the synchronous, asynchronous, and semisynchronous messagepassing models, as well as asynchronous shared memory augmented by consensus and set agreement objects.
We show how to exploit their common shellability structure to derive new and remarkably succinct tight (or nearly so) lower bounds on connectivity of protocol complexes and hence on solutions to the kset agreement task in these models.
more …
By
Castañeda, Armando; Herlihy, Maurice; Rajsbaum, Sergio
Post to Citeulike
3 Citations
In the renaming problem, each process in a distributed system is issued a unique name from a large name space, and the processes must coordinate with one another to choose unique names from a much smaller name space.
We show that lower bounds on the solvability of renaming in an asynchronous distributed system can be formulated as a purely topological question about the existence of an equivariant chain map from a “topological disk” to a “topological annulus”. Proving the nonexistence of such a map implies the nonexistence of a distributed renaming algorithm in several related models of computation.
more …
By
Fraigniaud, Pierre; Ilcinkas, David; Rajsbaum, Sergio; Tixeuil, Sébastien
Show all (4)
Post to Citeulike
1 Citations
We consider the task of exploring graphs with anonymous nodes by a team of noncooperative robots modeled as finite automata. These robots have no a priori knowledge of the topology of the graph, or of its size. Each edge has to be traversed by at least one robot. We first show that, for any set of q noncooperative Kstate robots, there exists a graph of size O(qK) that no robot of this set can explore. This improves the O(K^{O(q)}) bound by Rollik (1980). Our main result is an application of this improvement. It concerns exploration with stop, in which one robot has to explore and stop after completing exploration. For this task, the robot is provided with a pebble, that it can use to mark nodes. We prove that exploration with stop requires Ω(log n) bits for the family of graphs with at most n nodes. On the other hand, we prove that there exists an exploration with stop algorithm using a robot with O(D log Δ) bits of memory to explore all graphs of diameter at most D and degree at most Δ.
more …
By
Afek, Yehuda; Gafni, Eli; Rajsbaum, Sergio; Raynal, Michel; Travers, Corentin
Show all (5)
Post to Citeulike
4 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
Bonakdarpour, Borzoo; Fraigniaud, Pierre; Rajsbaum, Sergio; Travers, Corentin
Show all (4)
Post to Citeulike
2 Citations
Runtime Verification is a lightweight method for monitoring the formal specification of a system (usually in some form of temporal logics) at execution time. In a setting, where a set of distributed monitors have only a partial view of a large system and may be subject to different types of faults, the literature of runtime verification falls short in answering many fundamental questions. Examples include techniques to reason about the soundness and consistency of the collective set of verdicts computed by the set of distributed monitors. In this paper, we discuss open research problems on faulttolerant distributed monitoring that stem from different design choices and implementation platforms.
more …
By
Gafni, Eli; Rajsbaum, Sergio; Herlihy, Maurice
Post to Citeulike
12 Citations
We consider the the relative power of two important synchronization problems: set agreement and renaming. We show that renaming is strictly weaker than set agreement, in a roundbyround model of computation. We introduce new techniques, including previously unknown connections between properties of manifolds and computation, as well as novel “symmetrybreaking” constructions.
more …
By
Mostefaoui, Achour; Rajsbaum, Sergio; Raynal, Michel
Post to Citeulike
2 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
Post to Citeulike
8 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
Castañeda, Armando; Fraigniaud, Pierre; Gafni, Eli; Rajsbaum, Sergio; Roy, Matthieu
Show all (5)
Post to Citeulike
1 Citations
Adaptive renaming can be viewed as a coordination task involving a set of asynchronous agents, each aiming at grabbing a single resource out of a set of resources Similarly, musical chairs is also defined as a coordination task involving a set of asynchronous agents, each aiming at picking one of a set of available resources, where every agent comes with an a priori preference for some resource. We foresee instances in which some combinations of resources are allowed, while others are disallowed.
We model these constraints as an undirected graph whose nodes represent the resources, and an edge between two resources indicates that these two resources cannot be used simultaneously. In other words, the sets of resources that are allowed are those which form independent sets.
We assume that each agent comes with an a priori preference for some resource. If an agent’s preference is not in conflict with the preferences of the other agents, then this preference can be grabbed by the agent. Otherwise, the agents must coordinate to resolve their conflicts, and potentially choose non preferred resources. We investigate the following problem: given a graph, what is the maximum number of agents that can be accommodated subject to nonaltruistic behaviors of early arriving agents?
Just for cyclic constraints, the problem is surprisingly difficult. Indeed, we show that, intriguingly, the natural algorithm inspired from optimal solutions to adaptive renaming or musical chairs is suboptimal for cycles, but proven to be at most 1 to the optimal. The main message of this paper is that finding optimal solutions to the coordination with constraints and preferences task requires to design “dynamic” algorithms, that is, algorithms of a completely different nature than the “static” algorithms used for, e.g., renaming.
more …
By
Attiya, Hagit; Rajsbaum, Sergio
Post to Citeulike
This paper presents a selfcontained study of waitfree solvable tasks. A new necessary and sufficient condition for waitfree solvability is proved, providing a characterization of the waitfree solvable tasks. The necessary condition is used to prove tight bounds on renaming and kset consensus. The framework is based on topology, but uses only elementary combinatorics, and does not rely on algebraic or geometric arguments.
more …
By
DelporteGallet, Carole; Fauconnier, Hugues; Gafni, Eli; Rajsbaum, Sergio
Show all (4)
Post to Citeulike
We consider a system of n processes with ids not a priori known, that are drawn from a large space, potentially unbounded. How can these n processes communicate to solve a task? We show that n a priori allocated MultiWriter MultiReader (MWMR) registers are both needed and sufficient to solve any readwrite wait free solvable task. This contrasts with the existing possible solution borrowed from adaptive algorithms that require Θ(n^{2}) MWMR registers.
To obtain these results, the paper shows how the processes can non blocking emulate a system of n SingleWriter MultiReader (SWMR) registers on top of n MWMR registers. It is impossible to do such an emulation with n − 1 MWMR registers.
Furthermore, we want to solve a sequence of tasks (potentially infinite) that are sequentially dependent (processes need the previous task’s outputs in order to proceed to the next task). A non blocking emulation might starve a process forever. By doubling the space complexity, using 2n − 1 rather than just n registers, the computation is wait free rather than non blocking.
more …
By
Mostefaoui, Achour; Rajsbaum, Sergio; Raynal, Michel
Post to Citeulike
11 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
Fraigniaud, Pierre; Rajsbaum, Sergio; Travers, Corentin
Post to Citeulike
1 Citations
This paper studies notions of locality that are inherent to the specification of a distributed task and independent of the computing environment, in a shared memory waitfree system.
A locality property called projectionclosed is identified, that completely characterizes tasks that are waitfree checkable. A task
$T =(\ensuremath{\mathcal{I}} ,\ensuremath{\mathcal{O}} ,\Delta)$
is checkable if there exists a waitfree distributed algorithm that, given
$s\in\ensuremath{\mathcal{I}} $
and
$t\in\ensuremath{\mathcal{O}} $
, determines whether t ∈ Δ(s), i.e., if t is a valid output for s according to the specification of T. Moreover, determining whether a projectionclosed task is waitfree solvable remains undecidable, and hence this is a rich class of tasks.
A stronger notion of locality considers tasks where the outputs look identically to the inputs at every vertex (input value of a process). A task
$T= (\ensuremath{\mathcal{I}} ,\ensuremath{\mathcal{O}} ,\Delta)$
is said to be localitypreserving if
$\ensuremath{\mathcal{O}} $
is a covering complex of
$\ensuremath{\mathcal{I}} $
. This topological property yields obstacles for waitfree solvability different in nature from the classical agreement impossibility results. On the other hand, localitypreserving tasks are projectionclosed and therefore always waitfree checkable. A classification of localitypreserving tasks in term of their relative computational power is provided. A correspondence between localitypreserving tasks and subgroups of the edgepath group of an input complex shows the existence of hierarchies of localitypreserving tasks, each one containing at the top the universal task (induced by the universal covering complex), and at the bottom the trivial identity task.
more …
By
Du, Jingzhe; Kranakis, Evangelos; Ponce, Oscar Morales; Rajsbaum, Sergio
Show all (4)
Post to Citeulike
4 Citations
Consider a network of n directional antennae in the plane. We consider the problem of efficient neighbor discovery in a (synchronous) network of sensors employing directional antennae. In this setting sensors send messages and listen for messages by directing their antennae towards a specific direction (which is not necessarily known in advance). In our model the directional antennae can be rotated by the sensors as required so as to discover all neighbors in their vicinity. In this paper we will limit ourselves to the (D,D) communication model whereby sensors employ directional antennae with identical transmission/reception beam widths. Our methodology is based on techniques for symmetry breaking so as to enable sender/receiver communication. We provide 1) deterministic algorithms that introduce delay in the rotation of the antennae and exploit knowledge of the existence of a vertex coloring of the network, and 2) randomized algorithms that require knowledge only of an upper bound on the size of the network so as to accomplish neighbor discovery. In both instances we study tradeoffs on the efficiency of the algorithms proposed.
more …
By
Fraigniaud, Pierre; Rajsbaum, Sergio; Travers, Corentin
Post to Citeulike
13 Citations
This paper studies notions of locality that are inherent to the specification of distributed tasks by identifying fundamental relationships between the various scales of computation, from the individual process to the whole system. A locality property called projectionclosed is identified. This property completely characterizes tasks that are waitfree checkable, where a task
$$T =(\mathcal{I },\mathcal{O },\varDelta )$$
is said to be checkable if there exists a distributed algorithm that, given
$$s\in \mathcal{I }$$
and
$$t\in \mathcal{O }$$
, determines whether
$$t\in \varDelta {(s)}$$
, i.e., whether
$$t$$
is a valid output for
$$s$$
according to the specification of
$$T$$
. Projectionclosed tasks are proved to form a rich class of tasks. In particular, determining whether a projectionclosed task is waitfree solvable is shown to be undecidable. A stronger notion of locality is identified by considering tasks whose outputs “look identical” to the inputs at every process: a task
$$T= (\mathcal{I },\mathcal{O },\varDelta )$$
is said to be localitypreserving if
$$\mathcal{O }$$
is a covering complex of
$$\mathcal{I }$$
. We show that this topological property yields obstacles for waitfree solvability different in nature from the classical impossibility results. On the other hand, localitypreserving tasks are projectionclosed, and thus they are waitfree checkable. A classification of localitypreserving tasks in term of their relative computational power is provided. This is achieved by defining a correspondence between subgroups of the edgepath group of an input complex and localitypreserving tasks. This correspondence enables to demonstrate the existence of hierarchies of localitypreserving tasks, each one containing, at the top, the universal task (induced by the universal covering complex), and, at the bottom, the trivial identity task.
more …
By
Fraigniaud, Pierre; Rajsbaum, Sergio; Travers, Corentin; Kuznetsov, Petr; Rieutord, Thibault
Show all (5)
Post to Citeulike
A failure detector is a distributed oracle that provides each process with a module that continuously outputs an estimate of which processes in the system have failed. The perfect failure detector provides accurate and eventually complete information about process failures. We show that, in asynchronous failureprone messagepassing systems, perfect failure detection can be achieved by an oracle that outputs at most
$$\lceil \log \alpha (n)\rceil +1$$
bits per process in nprocess systems, where
$$\alpha $$
denotes the inverseAckermann function. This result is essentially optimal, as we also show that, in the same environment, no failure detector outputting a constant number of bits per process can achieve perfect failure detection.
more …
By
Benavides, Fernando; Rajsbaum, Sergio
Post to Citeulike
2 Citations
The celebrated asynchronous computability theorem provides a characterization of the class of decision tasks that can be solved in a waitfree manner by asynchronous processes that communicate by writing and taking atomic snapshots of a shared memory. Several variations of the model have been proposed (immediate snapshots and iterated immediate snapshots), all equivalent for waitfree solution of decision tasks, in spite of the fact that the protocol complexes that arise from the different models are structurally distinct. The topological and combinatorial properties of these snapshot protocol complexes have been studied in detail, providing explanations for why the asynchronous computability theorem holds in all the models.
In reality concurrent systems do not provide processes with snapshot operations. Instead, snapshots are implemented (by a waitfree protocol) using operations that write and read individual shared memory locations. Thus, read/write protocols are also computationally equivalent to snapshot protocols. However, the structure of the read/write protocol complex has not been studied. In this paper we show that the read/write iterated protocol complex is collapsible (and hence contractible). Furthermore, we show that a distributed protocol that waitfree implements atomic snapshots in effect is performing the collapses.
more …
By
Keidar, Idit; Rajsbaum, Sergio
Post to Citeulike
1 Citations
We consider the consensus problem in a messagepassing system where processes can crash: Each process has an input, and each correct process must decide on an output, such that all correct processes decide on the same output, and this output is the input of one of the processes. Consensus is an important building block for faulttolerant systems. It is wellknown that consensus is not solvable in an asynchronous model even if only one process can crash [7.13]. However, real systems are not completely asynchronous. Some partially synchronous models [7.12], [7.10] where consensus is solvable better approximate real systems.We consider a partial synchronymodel defined as follows [7.12]^{1}: (1) processes have bounded drift clocks; (2) there are known bounds on processing times and message delays; and (3) less than half of the processes can crash. In addition, this model allows the system to be unstable, where the bounds in (2) do not hold for an unbounded but finite period, but it must eventually enter a stableperiod where the bounds do hold.A consensus algorithm for the partial synchrony model never violates safety, and guarantees liveness once the system becomes stable. Algorithms for this model are called indulgent in [7.16]. What can we say about the running time of consensus algorithms in a partial synchrony model? Unfortunately, even in the absence of failures, any consensus algorithm in this model is bound to have unbounded running times, by [7.13].
more …
By
Even, Shimon; Itkis, Gene; Rajsbaum, Sergio
Post to Citeulike
2 Citations
Vertex and edge connectivity are special cases of mixed connectivity, in which all edges and a specified set of vertices play a similar role. Certificates of kconnectivity for a graph are obtained by removing a subset of its edges, while preserving its connectivity up to k.
We unify the previous work on connectivity certificates and extend it to handle mixed connectivity and multigraphs. Our treatment contributes a new insight of the pertinent structures, yielding more general results and simpler proofs. Also, we present a communicationoptimal distributed algorithm for finding mixed connectivity certificates.
more …
By
DelporteGallet, Carole; Fauconnier, Hugues; Gafni, Eli; Rajsbaum, Sergio
Show all (4)
Post to Citeulike
3 Citations
When n processes communicate by writing to and reading from k < n MWMR registers the “communication bandwidth” precludes emulation of SWMR system, even nonblocking.
Nevertheless, recently a positive result was shown that such a system either waitfree or obstructionfree can solve an interesting oneshot task. This paper demonstrates another such result. It shows that (n − 1)set agreement can be solved obstructionfree with merely 2 MWMR registers. Achieving kset agreement with n − k + 1 registers is a challenge. We make the first step toward it by showing kset agreement with 2(n − k) registers.
more …
By
Imbs, Damien; Rajsbaum, Sergio; Raynal, Michel; Stainer, Julien
Show all (4)
Post to Citeulike
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
Post to Citeulike
2 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
Post to Citeulike
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
Post to Citeulike
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
Herlihy, Maurice; Rajsbaum, Sergio
Post to Citeulike
3 Citations
Roughly speaking, a simplicial complex is shellable if it can be constructed by gluing a sequence of nsimplexes to one another along
$$(n1)$$
faces only. Shellable complexes have been widely studied because they have nice combinatorial properties. It turns out that several standard models of concurrent computation can be constructed from shellable complexes. We consider adversarial schedulers in the synchronous, asynchronous, and semisynchronous messagepassing models, as well as asynchronous shared memory. We show how to exploit their common shellability structure to derive new and remarkably succinct tight (or nearly so) lower bounds on connectivity of protocol complexes and hence on solutions to the
$$k$$
set agreement task in these models. Earlier versions of material in this article appeared in the 2010 ACM Symposium on Principles of Distributed Computing (Herlihy and Rajsbaum 2010), and the International Conference on Distributed Computing (Herlihy and Rajsbaum 2010, doi:
10.1145/1835698.1835724
).
more …
By
DelporteGallet, Carole; Fauconnier, Hugues; Rajsbaum, Sergio; Raynal, Michel
Show all (4)
Post to Citeulike
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
Herlihy, Maurice; Rajsbaum, Sergio
Post to Citeulike
1 Citations
Loop agreement is a family of waitfree tasks that includes set agreement and approximate agreement tasks. This paper presents a complete classification of loop agreement tasks. Each loop agreement task can be assigned an algebraic signature consisting of a finitelypresented group G and a distinguished element g in G. This signature completely characterizes the task's computational power. If G and H are loop agreement tasks with respective signatures 〈G, g〉 and 〈H, h〉, then G implements H if and only if there exists a group homomorphism Φ: G → H carrying g to h.
more …
By
Alcántara, Manuel; Castañeda, Armando; FloresPeñaloza, David; Rajsbaum, Sergio
Show all (4)
Post to Citeulike
LookComputeMove models for a set of autonomous robots have been thoroughly studied for over two decades. We consider the standard Asynchronous Luminous Robots (ALR) model, where robots are located in a graph G. Each robot, repeatedly Looks at its surroundings and obtains a snapshot containing the vertices of G, where all robots are located; based on this snapshot, each robot Computes a vertex (adjacent to its current position), and then Moves to it. Robots have visible lights, allowing them to communicate more information than only its actual position, and they move asynchronously, meaning that each one runs at its own arbitrary speed. We are also interested in a case which has been barely explored: the robots need not all be present initially, they might appear asynchronously. We call this the Extended Asynchronous Appearing Luminous Robots (EALR) model. A central problem in the mobile robots area is bringing the robots to the same vertex. We study several versions of this problem, where the robots move towards the same (or close to each other) vertices. And we concentrate on the requirement that each robot executes a finite number of LookComputeMove cycles, independently of the interleaving of other robot’s cycles, and then stops. Our main result is direct connections between the (ALR and) EALR model and the asynchronous waitfree multiprocess read/write shared memory (WFSM) model. General robot tasks in a graph are also provided, which include several version of gathering. Finally, using the connection between the EALR model and the WFSM model, a combinatorial topology characterization for the solvable robot tasks is presented.
more …
By
Castañeda, Armando; Delporte, Carole; Fauconnier, Hugues; Rajsbaum, Sergio; Raynal, Michel
Show all (5)
Post to Citeulike
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)
Post to Citeulike
12 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)
Post to Citeulike
9 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
MarcelínJiménez, Ricardo; Rajsbaum, Sergio
Post to Citeulike
2 Citations
Given a set V of active components in charge of a distributed execution, a storage scheme is a sequence of subsets, B_{1},B_{2},...,B_{b}, of V where, succesive global states are recorded. The subsets, called blocks, have the same size and are scheduled according to some fixed and cyclic calendar of b steps. During ith step, block B_{i} is selected. Next, a global snapshot is taken and each component sends its corresponding local state to one of the appointed places in B_{i}, in a way that each component stores (approx.) the same number of local states. Afterwards, if a component of B_{i} crashes, all of the data stored in the block is useless, because the global state can not be reconstructed. In this case, the information recorded in an earlier block can be used to recover a global state, provided there is at least one such block where no component has crashed. The goal is to design storage schema that tolerate as many crashes as possible, while trying to have each component participating in as few blocks as possible and, at the same time, working with large blocks (so that a component in a block stores a small number of local states). In this paper several such schema are described and compared in terms of these measures.
more …
By
Castañeda, Armando; Rajsbaum, Sergio
Post to Citeulike
15 Citations
In the renaming task n + 1 processes start with unique input names taken from a large space and must choose unique output names taken from a smaller name space, 0, 1, . . . , K. To rule out trivial solutions, a protocol must be anonymous: the value chosen by a process can depend on its input name and on the execution, but not on the specific process id. Attiya et al. showed in 1990 that renaming has a waitfree solution when K ≥ 2n. Several proofs of a lower bound stating that no such protocol exists when K < 2n have been published. We presented in the ACM PODC 2008 conference the following two results. First, we presented the first completely combinatorial lower bound proof stating that no such a protocol exists when K < 2n. This bound holds for infinitely many values of n. Second, for the other values of n, we proved that the lower bound for K < 2n is incorrect, exhibiting a waitfree renaming protocol for K = 2n−1. More precisely, we presented a theorem stating that there exists a waitfree renaming protocol for K < 2n if and only if the set of integers
$${\{ {n+1 \choose i+1}  0 \leq i \leq \lfloor \frac{n1}{2} \rfloor \}}$$
are relatively prime. This paper is the first part of the full version of the results presented in the ACM PODC 2008 conference. It includes only the lower bound. Namely, we show here that no protocol for renaming exists when K < 2n, if n is such that
$${\{ {n+1 \choose i+1}  0 \leq i \leq \lfloor \frac{n1}{2}\rfloor \}}$$
are not relatively prime. We prove this result using the known equivalence of Krenaming for K = 2n−1 and the weak symmetry breaking task. In this task processes have no input values and the output values are 0 or 1, and it is required that in every execution in which all processes participate, at least one process decides 0 and at least one process decides 1. The full version of the upper bound appears in a companion paper [10].
more …
By
Castañeda, Armando; Herlihy, Maurice; Rajsbaum, Sergio
Post to Citeulike
1 Citations
In the renaming problem, each process in a distributed system is issued a unique name from a large namespace, and the processes must coordinate with one another to choose unique names from a much smaller name space.
We show that lower bounds on the solvability of renaming can be formulated as a purely topological question about the existence of an equivariant chain map from a “topological disk” to a “topological annulus”. Proving the nonexistence of such a map implies the nonexistence of a distributed renaming algorithm in several related models of computation.
more …
By
Castañeda, Armando; Rajsbaum, Sergio; Roy, Matthieu
Post to Citeulike
The class of robot convergence tasks has been shown to capture fundamental aspects of faulttolerant computability. A set of asynchronous robots that may fail by crashing, start from unknown places in some given space, and have to move towards positions close to each other. In this article, we study the case where the space is unidimensional, modeled as a graph G. In graph convergence, robots have to end up on one or two vertices of the same edge. We consider also a variant of robot convergence on graphs, edge covering, where additionally, it is required that not all robots end up on the same vertex. Remarkably, these two similar problems have very different computability properties, related to orthogonal fundamental issues of distributed computations: agreement and symmetry breaking. We characterize the graphs on which each of these problems is solvable, and give optimal time algorithms for the solvable cases. Although the results can be derived from known general topology theorems, the presentation serves as a selfcontained introduction to the algebraic topology approach to distributed computing, and yields concrete algorithms and impossibility results.
more …
By
Castañeda, Armando; DelporteGallet, Carole; Fauconnier, Hugues; Rajsbaum, Sergio; Raynal, Michel
Show all (5)
Post to Citeulike
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 …
