Increasing the Power of the Iterated Immediate Snapshot Model with Failure Detectors
International audience 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 infin...
Main Authors: | , |
---|---|
Other Authors: | , , , , , , , |
Format: | Conference Object |
Language: | English |
Published: |
HAL CCSD
2012
|
Subjects: | |
Online Access: | https://hal.inria.fr/hal-00733077 |
id |
ftunivrennes1hal:oai:HAL:hal-00733077v1 |
---|---|
record_format |
openpolar |
spelling |
ftunivrennes1hal:oai:HAL:hal-00733077v1 2023-05-15T16:50:38+02:00 Increasing the Power of the Iterated Immediate Snapshot Model with Failure Detectors Raynal, Michel Stainer, Julien As Scalable As Possible: foundations of large scale dynamic distributed systems (ASAP) Inria Rennes – Bretagne Atlantique Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-SYSTÈMES LARGE ÉCHELLE (IRISA-D1) Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA) Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes) Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes) Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA) Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS) Reykjavik, Iceland 2012 https://hal.inria.fr/hal-00733077 en eng HAL CCSD hal-00733077 https://hal.inria.fr/hal-00733077 SIROCCO - Structural Information and Communication Complexity - 19th International Colloquium - 2012 https://hal.inria.fr/hal-00733077 SIROCCO - Structural Information and Communication Complexity - 19th International Colloquium - 2012, 2012, Reykjavik, Iceland. pp.231-242 [INFO.INFO-DC]Computer Science [cs]/Distributed Parallel and Cluster Computing [cs.DC] info:eu-repo/semantics/conferenceObject Conference papers 2012 ftunivrennes1hal 2023-03-21T23:50:24Z International audience 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. Conference Object Iceland Université de Rennes 1: Publications scientifiques (HAL) |
institution |
Open Polar |
collection |
Université de Rennes 1: Publications scientifiques (HAL) |
op_collection_id |
ftunivrennes1hal |
language |
English |
topic |
[INFO.INFO-DC]Computer Science [cs]/Distributed Parallel and Cluster Computing [cs.DC] |
spellingShingle |
[INFO.INFO-DC]Computer Science [cs]/Distributed Parallel and Cluster Computing [cs.DC] Raynal, Michel Stainer, Julien Increasing the Power of the Iterated Immediate Snapshot Model with Failure Detectors |
topic_facet |
[INFO.INFO-DC]Computer Science [cs]/Distributed Parallel and Cluster Computing [cs.DC] |
description |
International audience 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. |
author2 |
As Scalable As Possible: foundations of large scale dynamic distributed systems (ASAP) Inria Rennes – Bretagne Atlantique Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-SYSTÈMES LARGE ÉCHELLE (IRISA-D1) Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA) Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes) Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes) Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA) Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS) |
format |
Conference Object |
author |
Raynal, Michel Stainer, Julien |
author_facet |
Raynal, Michel Stainer, Julien |
author_sort |
Raynal, Michel |
title |
Increasing the Power of the Iterated Immediate Snapshot Model with Failure Detectors |
title_short |
Increasing the Power of the Iterated Immediate Snapshot Model with Failure Detectors |
title_full |
Increasing the Power of the Iterated Immediate Snapshot Model with Failure Detectors |
title_fullStr |
Increasing the Power of the Iterated Immediate Snapshot Model with Failure Detectors |
title_full_unstemmed |
Increasing the Power of the Iterated Immediate Snapshot Model with Failure Detectors |
title_sort |
increasing the power of the iterated immediate snapshot model with failure detectors |
publisher |
HAL CCSD |
publishDate |
2012 |
url |
https://hal.inria.fr/hal-00733077 |
op_coverage |
Reykjavik, Iceland |
genre |
Iceland |
genre_facet |
Iceland |
op_source |
SIROCCO - Structural Information and Communication Complexity - 19th International Colloquium - 2012 https://hal.inria.fr/hal-00733077 SIROCCO - Structural Information and Communication Complexity - 19th International Colloquium - 2012, 2012, Reykjavik, Iceland. pp.231-242 |
op_relation |
hal-00733077 https://hal.inria.fr/hal-00733077 |
_version_ |
1766040763108425728 |