The Iterated Restricted Immediate Snapshot Model

Corentin Travers (1) , Sergio Rajsbaum (2) , Michel Raynal (3)

1 LaBRI - Laboratoire Bordelais de Recherche en Informatique
2 Instituto de Matematicas [México]
3 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems

In the Iterated Immediate Snapshot model (IIS ) the memory consists of a sequence of one-shot Immediate Snapshot (IS ) objects. Processes access the sequence of IS objects, one-by-one, asynchronously, in a wait-free manner; any number of processes can crash. Although more restricted (each IS object can be accessed only once), the IIS model is equivalent to the read/write model for wait-free solvability of decision tasks. Its interest lies in the elegant recursive structure of its runs, which facilitates its analysis, round by round. Although there are by now quite a few papers that use the IIS model or its variants, the approach has not yet been used to study failure detectors. The paper shows that an elegant way of capturing the power of a failure detector and other partially synchronous systems is by considering appropriate subsets of runs of the IIS model, giving rise to the Iterated Restricted Immediate Snapshot model (IRIS ). The proposed approach has several benefits. First it provides us with new simulations in presence of asynchrony and failures. Then, it gives new insights on the very nature of failure detectors, and on how to represent them in an iterated model. Finally, it allows designing simpler proofs of existing results. As a study case, the paper considers a system enriched with a limited-scope accuracy failure detector, where there is a cluster of processes such that some correct process is eventually never suspected by any process in that cluster. A new proof of the k-set agreement Herlihy and Penso's lower bound for shared memory system augmented with a limited-scope accuracy failure detector is provided. The proof is based on an extension of the Borowsky-Gafni IIS simulation to encompass failure detectors, followed by a very simple topological argumentation. The paper describes similar applications for other failure detectors including the classes Ωz and ✸ψ y .

Ce rapport présente un modèle de calcul réparti itéré généralisé.

Domaines: Calcul parallèle, distribué et partagé [cs.DC]

Corentin Travers, Sergio Rajsbaum, Michel Raynal. The Iterated Restricted Immediate Snapshot Model. [Research Report] PI-2005, 2013. ⟨hal-00829436v2⟩