Skip to Main content Skip to Navigation
Conference papers

A Characterization of t-Resilient Colorless Task Anonymous Solvability

Abstract : One of the central questions in distributed computability is characterizing the tasks that are solvable in a given system model. In the anonymous case, where processes have no identifiers and communicate through multi-writer/multi-reader registers, there is a recent topologi-cal characterization (Yanagisawa 2017) of the colorless tasks that are solvable when any number of asynchronous processes may crash. In this paper, we consider the case where at most t asynchronous processes may crash, where 1 ≤ t < n. We prove that a colorless task is t-resilient solvable anonymously if and only if it is t-resilient solvable non-anonymously. We obtain our results through various reductions and simulations that explore how to extend techniques for non-anonymous computation to anonymous one.
Document type :
Conference papers
Complete list of metadata

Cited literature [31 references]  Display  Hide  Download
Contributor : Carole Delporte-Gallet Connect in order to contact the contributor
Submitted on : Friday, December 14, 2018 - 4:14:00 PM
Last modification on : Friday, January 21, 2022 - 3:19:55 AM
Long-term archiving on: : Friday, March 15, 2019 - 5:18:37 PM


Files produced by the author(s)



Carole Delporte-Gallet, Hugues Fauconnier, Sergio Rajsbaum, Nayuta Yanagisawa. A Characterization of t-Resilient Colorless Task Anonymous Solvability. SIROCCO 2018 - 25th International Colloquium Structural Information and Communication Complexity, Jun 2018, Ma'ale HaHamisha, Israel. ⟨10.1007/978-3-030-01325-7_18⟩. ⟨hal-01955837⟩



Les métriques sont temporairement indisponibles