Skip to Main content Skip to Navigation

Combinatorial characterization of asynchronous distributed computability

Abstract : Modern computing systems are distributed, ranging from single-chip multi-processors to large-scale internet systems. In this thesis, we study computability and complexity issues raising in asynchronous crash-prone shared memory systems.The major part of this thesis is devoted to characterizing the power of a shared memory model to solve distributed tasks. Our first contribution is a refined and extended agreement-based simulation technique that allows us to reason about the relative task computability of shared-memory models. Using this simulation technique, we show that the task computability of a shared-memory adversarial model is grasped by its ability to solve specific agreement tasks. We then use the language of combinatorial topology to characterize the task computability of shared-memory models via affine tasks: sub-complexes of a finite iteration of the standard chromatic subdivision. Our characterization applies to the wait-free model enhanced with k-test-and-set objects and a to large class of fair adversarial models. These results generalize and improve all previously derived topological characterizations of the task computability power of shared memory models.In the second part of the thesis, we focus on space complexity of implementing stable storage, i.e., ensuring that written values persists in memory, in the comparison-based model using multi-writer registers. Our results exhibit a non-trivial tradeoff between space complexity of stable-storage implementations and the progress guarantees they provide.
Complete list of metadata

Cited literature [102 references]  Display  Hide  Download
Contributor : ABES STAR :  Contact
Submitted on : Monday, September 14, 2020 - 4:39:17 PM
Last modification on : Wednesday, June 15, 2022 - 8:46:31 PM
Long-term archiving on: : Friday, December 4, 2020 - 8:53:53 PM


Version validated by the jury (STAR)


  • HAL Id : tel-02938080, version 1



Thibault Rieutord. Combinatorial characterization of asynchronous distributed computability. Distributed, Parallel, and Cluster Computing [cs.DC]. Université Paris Saclay (COmUE), 2018. English. ⟨NNT : 2018SACLT007⟩. ⟨tel-02938080⟩



Record views


Files downloads