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 metadatas

Cited literature [31 references]  Display  Hide  Download

https://hal.inria.fr/hal-01955837
Contributor : Carole Delporte-Gallet <>
Submitted on : Friday, December 14, 2018 - 4:14:00 PM
Last modification on : Wednesday, October 2, 2019 - 4:31:06 PM
Long-term archiving on : Friday, March 15, 2019 - 5:18:37 PM

File

main.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

67

Files downloads

141