Computability Abstractions for Fault-tolerant Asynchronous Distributed Computing

Julien Stainer 1, 2
1 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
UR1 - Université de Rennes 1, Inria Saclay - Ile de France, INSA - Institut National des Sciences Appliquées, CNRS - Centre National de la Recherche Scientifique : UMR
2 DiverSe - Diversity-centric Software Engineering
Inria Rennes – Bretagne Atlantique , IRISA-D4 - LANGAGE ET GÉNIE LOGICIEL
Abstract : This thesis studies computability in systems composed of multiple computers exchanging messages or sharing memory. The considered models take into account the possible failure of some of these computers, as well as variations in time and heterogeneity of their execution speeds. The presented results essentially consider agreement problems, systems prone to partitioning and failure detectors. The document establishes relations between known iterated models and the concept of failure detector and presents a hierarchy of agreement problems spanning from k-set agreement to s-simultaneous consensus. It also introduces a new universal construction based on s-simultaneous consensus objects and a family of iterated models allowing several processes to run in isolation.
Complete list of metadatas

Cited literature [91 references]  Display  Hide  Download

https://hal.inria.fr/tel-01256926
Contributor : Abes Star <>
Submitted on : Monday, January 18, 2016 - 5:44:05 AM
Last modification on : Friday, January 11, 2019 - 1:53:35 PM
Long-term archiving on : Friday, November 11, 2016 - 9:16:07 AM

File

STAINER_Julien.pdf
Version validated by the jury (STAR)

Identifiers

  • HAL Id : tel-01256926, version 2

Citation

Julien Stainer. Computability Abstractions for Fault-tolerant Asynchronous Distributed Computing. Distributed, Parallel, and Cluster Computing [cs.DC]. Université Rennes 1, 2015. English. ⟨NNT : 2015REN1S054⟩. ⟨tel-01256926v2⟩

Share

Metrics

Record views

503

Files downloads

274