We consider the models of distributed computation defined as subsets of the runs of the iterated immediate snapshot model. Given a task @math and a model @math , we provide topological conditions for @math to be solvable in @math . When applied to the wait-free model, our conditions result in the celebrated Asynchronous Computability Theorem (ACT) of Herlihy and Shavit. To demonstrate the utility of our characterization, we consider a task that has been shown earlier to admit only a very complex @math -resilient solution. In contrast, our generalized computability theorem confirms its @math -resilient solvability in a straightforward manner.
We give necessary and sufficient combinatorial conditions characterizing the computational tasks that can be solved by N asynchronous processes, up to t of which can fail by halting. The range of possible input and output values for an asynchronous task can be associated with a high-dimensional geometric structure called a simplicial complex. Our main theorem characterizes computability y in terms of the topological properties of this complex. Most notably, a given task is computable only if it can be associated with a complex that is simply connected with trivial homology groups. In other words, the complex has “no holes!” Applications of this characterization include the first impossibility results for several long-standing open problems in distributed computing, such as the “renaming” problem of Attiya et. al., the “k-set agreement” problem of Chaudhuri, and a generalization of the approximate agreement problem. The invention relates to a fluid supply system and seeks to provide a simpler, safer but reliable system than at present known. The fluid supply system comprises a multi-charge solid propellant gas generator and a fluid expulsion unit integrated into a single unit, the gas generator being provided in a cap (8) for a chamber (1) having a gas portion (3) and a fluid portion (2) and a movable partition (4) between these two portions operable to expel fluid from the chamber when the gas generator is rendered operative. The system also comprises ignition control means (22) operable to control the ignition of the solid propellant charges (13) when required to give a fully controllable system output. The system can be designed for supplying under pressure fluids such as hydraulic oil, fuels, oxidants and water and is particularly useful in aerospace applications.   In the Iterated Immediate Snapshotmodel ( @math ) the memory consists of a sequence of one-shot Immediate Snapshot( @math ) objects. Processes access the sequence of @math objects, one-by-one, asynchronously, in a wait-freemanner; 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 @math model and the read write model are equivalent for the wait-free solvability of decision tasks. This paper extends the benefits of the @math model to partially synchronous systems. Given a shared memory model enriched with a failure detector, what is an equivalent @math model? The paper shows that an elegant way of capturing the power of a failure detector and other partially synchronous systems in the @math model is by restricting appropriately its set of runs, giving rise to the Iterated Restricted Immediate Snapshotmodel ( @math ). In round-by-round models of distributed computing processes run in a sequence of (synchronous or asynchronous) rounds. The advantage of the round-by-round approach is that invariants established in the first round are preserved in later rounds. An elegant asynchronous round-by-round 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 Pi writes to m[i] and can take a snapshot of the entire array, we have processes share a two-dimensional array m[ċ, ċ], indexed by iteration number and by process ID, where Pi 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 wait-free 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 wait-free. The main contribution is to show that the simulation can work with models that have access to certain communication objects, called 01-tasks. 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 non-iterated wait-free read write shared memory model. We also show that our simulation works with t-resilient 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 non-iterated model. Distributed Computing Through Combinatorial Topology describes techniques for analyzing distributed algorithms based on award winning combinatorial topology research. The authors present a solid theoretical foundation relevant to many real systems reliant on parallelism with unpredictable delays, such as multicore microprocessors, wireless networks, distributed systems, and Internet protocols. Today, a new student or researcher must assemble a collection of scattered conference publications, which are typically terse and commonly use different notations and terminologies. This book provides a self-contained explanation of the mathematics to readers with computer science backgrounds, as well as explaining computer science concepts to readers with backgrounds in applied mathematics. The first section presents mathematical notions and models, including message passing and shared-memory systems, failures, and timing models. The next section presents core concepts in two chapters each: first, proving a simple result that lends itself to examples and pictures that will build up readers' intuition; then generalizing the concept to prove a more sophisticated result. The overall result weaves together and develops the basic concepts of the field, presenting them in a gradual and intuitively appealing way. The book's final section discusses advanced topics typically found in a graduate-level course for those who wish to explore further. Gathers knowledge otherwise spread across research and conference papers using consistent notations and a standard approach to facilitate understandingPresents unique insights applicable to multiple computing fields, including multicore microprocessors, wireless networks, distributed systems, and Internet protocols Synthesizes and distills material into a simple, unified presentation with examples, illustrations, and exercises  We give necessary and sufficient combinatorial conditions characterizing the tasks that can be solved by asynchronous processes, of which all but one can fail, that communicate by reading and writing a shared memory. We introduce a new formalism for tasks, based on notions from classical algebraic and combinatorial topology, in which a task''s possible input and output values are each associated with high-dimensional geometric structures called simplicial complexes. We characterize computability in terms of the topological properties of these complexes. This characterization has a surprising geometric interpretation: a task is solvable if and only if the complex representing the task''s allowable inputs can be mapped to the complex representing the task''s allowable outputs by a function satisfying certain simple regularity properties. Our formalism thus replaces the operational'''' notion of a wait-free decision task, expressed in terms of interleaved computations unfolding in time, by a static combinatorial'''' description expressed in terms of relations among topological spaces, allowing us to exploit powerful theorems from the classic literature on algebraic and combinatorial topology. This approach yields the first impossibility results for several long-standing open problems in distributed computing, such as the renaming'''' problem of , and the @math -set agreement'''' problem of Chaudhuri. The Iterated Immediate Snapshot model (IIS), due to its elegant topological representation, has become standard for applying topological reasoning to distributed computing. In this paper, we focus on relations between IIS and the more realistic (non-iterated) read-write Atomic- Snapshot memory model (AS). We grasp equivalences between subsets of runs of AS and IIS (we call them sub-IIS and sub-AS models). To establish an equivalence between a sub-AS model M and a sub-IIS model M', we need two algorithms, a forward simulation F : AS -> IIS and a backward simulation B: IIS -> AS, such that B(F(M)) is a subset of M and F(B(M')) is a subset of M'. AS and IIS are provided with such simulations and, thus, they have the same task computability power. However, the relations between proper sub-AS and sub-IIS models remained unclear until now. In this paper, we present a two-way simulation protocol that provides an equivalent sub-IIS model for any adversarial sub-AS model, i.e., for any sub-AS model specified by the sets of live processes. We achieve the result by ensuring that, under the two-way simulation, the set of live processes in an AS run coincides with the set of fast processes in the simulated IIS run, and vice versa. The base distributed asynchronous read write computation model is made up of n asynchronous processes which communicate by reading and writing atomic registers only. The distributed asynchronous iterated model is a more constrained model in which the processes execute an infinite number of rounds and communicate at each round with a new object called immediate snapshot object. Moreover, in both models up to n−1 processes may crash in an unexpected way. When considering computability issues, two main results are associated with the previous models. The first states that they are computationally equivalent for decision tasks. The second states that they are no longer equivalent when both are enriched with the same failure detector. This paper shows how to capture failure detectors in each model so that both models become computationally equivalent. To that end it introduces the notion of a "strongly correct" process which appears particularly well-suited to the iterated model, and presents simulations that prove the computational equivalence when both models are enriched with the same failure detector. The paper extends also these simulations to the case where the wait-freedom requirement is replaced by the notion of t-resilience.