---
_id: '767'
abstract:
- lang: eng
text: Synchronous distributed algorithms are easier to design and prove correct
than algorithms that tolerate asynchrony. Yet, in the real world, networks experience
asynchrony and other timing anomalies. In this paper, we address the question
of how to efficiently transform an algorithm that relies on synchronous timing
into an algorithm that tolerates asynchronous executions. We introduce a transformation
technique from synchronous algorithms to indulgent algorithms (Guerraoui, in PODC,
pp. 289-297, 2000), which induces only a constant overhead in terms of time complexity
in well-behaved executions. Our technique is based on a new abstraction we call
an asynchrony detector, which the participating processes implement collectively.
The resulting transformation works for the class of colorless distributed tasks,
including consensus and set agreement. Interestingly, we also show that our technique
is relevant for colored tasks, by applying it to the renaming problem, to obtain
the first indulgent renaming algorithm.
acknowledgement: "Dan Alistarh was supported by the NCCR MICS Project. Corentin Travers
had additional support from INRIA team REGAL and ANR project SPREADS.\r\nThe authors
would like to thank Hagit Attiya and Nikola Kneževi\r\n ́\r\nc for their feed-\r\nback
on previous drafts of this paper, and the anonymous reviewers for their useful comments."
article_processing_charge: No
author:
- first_name: Dan-Adrian
full_name: Alistarh, Dan-Adrian
id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
last_name: Alistarh
orcid: 0000-0003-3650-940X
- first_name: Seth
full_name: Gilbert, Seth
last_name: Gilbert
- first_name: Rachid
full_name: Guerraoui, Rachid
last_name: Guerraoui
- first_name: Corentin
full_name: Travers, Corentin
last_name: Travers
citation:
ama: Alistarh D-A, Gilbert S, Guerraoui R, Travers C. Generating Fast Indulgent
Algorithms. Theory of Computing Systems. 2012;51(4):404-424. doi:10.1007/s00224-012-9407-2
apa: Alistarh, D.-A., Gilbert, S., Guerraoui, R., & Travers, C. (2012). Generating
Fast Indulgent Algorithms. Theory of Computing Systems. Elsevier. https://doi.org/10.1007/s00224-012-9407-2
chicago: Alistarh, Dan-Adrian, Seth Gilbert, Rachid Guerraoui, and Corentin Travers.
“Generating Fast Indulgent Algorithms.” Theory of Computing Systems. Elsevier,
2012. https://doi.org/10.1007/s00224-012-9407-2.
ieee: D.-A. Alistarh, S. Gilbert, R. Guerraoui, and C. Travers, “Generating Fast
Indulgent Algorithms,” Theory of Computing Systems, vol. 51, no. 4. Elsevier,
pp. 404–424, 2012.
ista: Alistarh D-A, Gilbert S, Guerraoui R, Travers C. 2012. Generating Fast Indulgent
Algorithms. Theory of Computing Systems. 51(4), 404–424.
mla: Alistarh, Dan-Adrian, et al. “Generating Fast Indulgent Algorithms.” Theory
of Computing Systems, vol. 51, no. 4, Elsevier, 2012, pp. 404–24, doi:10.1007/s00224-012-9407-2.
short: D.-A. Alistarh, S. Gilbert, R. Guerraoui, C. Travers, Theory of Computing
Systems 51 (2012) 404–424.
date_created: 2018-12-11T11:48:23Z
date_published: 2012-01-01T00:00:00Z
date_updated: 2023-02-23T13:13:40Z
day: '01'
doi: 10.1007/s00224-012-9407-2
extern: '1'
intvolume: ' 51'
issue: '4'
language:
- iso: eng
month: '01'
oa_version: None
page: 404 - 424
publication: Theory of Computing Systems
publication_status: published
publisher: Elsevier
publist_id: '6891'
status: public
title: Generating Fast Indulgent Algorithms
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 51
year: '2012'
...