<div class="csl-bib-body">
<div class="csl-entry">Galeana, H. R., Rajsbaum, S., & Schmid, U. (2022). Continuous Tasks and the Asynchronous Computability Theorem. In M. Braverman (Ed.), <i>13th Innovations in Theoretical Computer Science Conference (ITCS’22)</i> (pp. 73:1-73:27). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ITCS.2022.73</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/139841
-
dc.description.abstract
The celebrated 1999 Asynchronous Computability Theorem (ACT) of Herlihy and Shavit characterized distributed tasks that are wait-free solvable and uncovered deep connections with combinatorial topology. We provide an alternative characterization of those tasks by means of the novel concept of continuous tasks, which have an input/output specification that is a continuous function between the geometric realizations of the input and output complex: We state and prove a precise characterization theorem (CACT) for wait-free solvable tasks in terms of continuous tasks. Its proof utilizes a novel chromatic version of a foundational result in algebraic topology, the simplicial approximation theorem, which is also proved in this paper. Apart from the alternative proof of the ACT implied by our CACT, we also demonstrate that continuous tasks have an expressive power that goes beyond classic task specifications, and hence open up a promising venue for future research: For the well-known approximate agreement task, we show that one can easily encode the desired proportion of the occurrence of specific outputs, namely, exact agreement, in the continuous task specification.
en
dc.description.sponsorship
Fonds zur Förderung der wissenschaftlichen Forschung (FWF)
-
dc.language.iso
en
-
dc.relation.ispartofseries
Leibniz International Proceedings in Informatics (LIPIcs)
-
dc.subject
Decision tasks
en
dc.subject
Distributed computing
en
dc.subject
Shared memory
en
dc.subject
Topology
en
dc.subject
Wait-free computability
en
dc.title
Continuous Tasks and the Asynchronous Computability Theorem
en
dc.type
Inproceedings
en
dc.type
Konferenzbeitrag
de
dc.contributor.affiliation
Universidad Nacional Autónoma de México
-
dc.contributor.editoraffiliation
Princeton University, USA
-
dc.relation.isbn
9783959772174
-
dc.description.startpage
73:1
-
dc.description.endpage
73:27
-
dc.relation.grantno
P 33600-N
-
dcterms.dateSubmitted
2022-01
-
dc.type.category
Full-Paper Contribution
-
dc.relation.eissn
1868-8969
-
tuw.booktitle
13th Innovations in Theoretical Computer Science Conference (ITCS'22)
-
tuw.container.volume
215
-
tuw.peerreviewed
true
-
tuw.relation.publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
-
tuw.project.title
Reasoning about Knowledge in Byzantine Distributed Systems
-
tuw.researchTopic.id
I2
-
tuw.researchTopic.name
Computer Engineering and Software-Intensive Systems
-
tuw.researchTopic.value
100
-
tuw.publication.orgunit
E191-02 - Forschungsbereich Embedded Computing Systems
-
tuw.publisher.doi
10.4230/LIPIcs.ITCS.2022.73
-
dc.description.numberOfPages
27
-
tuw.author.orcid
0000-0002-8152-1275
-
tuw.author.orcid
0000-0001-9831-8583
-
tuw.editor.orcid
0000-0002-6964-5291
-
tuw.event.name
13th Innovations in Theoretical Computer Science Conference (ITCS'22)
en
dc.description.sponsorshipexternal
UNAM
-
dc.relation.grantnoexternal
UNAM-PAPIIT IN106520.
-
tuw.event.startdate
31-01-2022
-
tuw.event.enddate
03-02-2022
-
tuw.event.online
Online
-
tuw.event.type
Event for scientific audience
-
tuw.event.place
Berkeley
-
tuw.event.country
US
-
tuw.event.institution
Simons Institute Berkeley
-
tuw.event.presenter
Galeana, Hugo Rincon
-
tuw.presentation.online
Online
-
tuw.event.track
Single Track
-
wb.sciencebranch
Informatik
-
wb.sciencebranch
Mathematik
-
wb.sciencebranch.oefos
1020
-
wb.sciencebranch.oefos
1010
-
wb.sciencebranch.value
50
-
wb.sciencebranch.value
50
-
item.openairetype
conference paper
-
item.openairecristype
http://purl.org/coar/resource_type/c_5794
-
item.languageiso639-1
en
-
item.fulltext
no Fulltext
-
item.cerifentitytype
Publications
-
item.grantfulltext
none
-
crisitem.project.funder
FWF - Österr. Wissenschaftsfonds
-
crisitem.project.grantno
P 33600-N
-
crisitem.author.dept
E191-02 - Forschungsbereich Embedded Computing Systems
-
crisitem.author.dept
Universidad Nacional Autónoma de México
-
crisitem.author.dept
E191-02 - Forschungsbereich Embedded Computing Systems