Passer à la navigation principale Passer à la recherche Passer au contenu principal

A generalized Asynchronous Computability Theorem

  • Computer Science Department, UCLA
  • University of California, Los Angeles

Résultats de recherche: Le chapitre dans un livre, un rapport, une anthologie ou une collection › Contribution à une conférence › Revue par des pairs

27 Citations (Scopus)

Résumé

We consider the models of distributed computation defined as subsets of the runs of the iterated immediate snapshot model. Given a task T and a model M, we provide topological conditions for T to be solvable in M. When applied to the wait-free model, our conditions result in the celebrated Asynchronous Computability Theorem (ACT) of Herlihy and Shavit. To demonstrate the utility of our characterization, we consider a task that has been shown earlier to admit only a very complex t-resilient solution. In contrast, our generalized computability theorem confirms its t-resilient solvability in a straightforward manner.

langue originaleAnglais
titrePODC 2014 - Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing
EditeurAssociation for Computing Machinery
Pages222-231
Nombre de pages10
ISBN (imprimé)9781450329446, 9781450329446
Les DOIs
étatPublié - 15 juil. 2014
Evénement2014 ACM Symposium on Principles of Distributed Computing, PODC 2014 - Paris, France
Durée: 15 juil. 2014 → 18 juil. 2014

Série de publications

NomProceedings of the Annual ACM Symposium on Principles of Distributed Computing

Une conférence

Une conférence2014 ACM Symposium on Principles of Distributed Computing, PODC 2014
Pays/TerritoireFrance
La villeParis
période15/07/14 → 18/07/14

Empreinte digitale

Examiner les sujets de recherche de « A generalized Asynchronous Computability Theorem ». Ensemble, ils forment une empreinte digitale unique.

Contient cette citation