---
_id: '764'
abstract:
- lang: eng
text: Set agreement is a fundamental problem in distributed computing in which processes
collectively choose a small subset of values from a larger set of proposals. The
impossibility of fault-tolerant set agreement in asynchronous networks is one
of the seminal results in distributed computing. In synchronous networks, too,
the complexity of set agreement has been a significant research challenge that
has now been resolved. Real systems, however, are neither purely synchronous nor
purely asynchronous. Rather, they tend to alternate between periods of synchrony
and periods of asynchrony. Nothing specific is known about the complexity of set
agreement in such a "partially synchronous" setting. In this paper,
we address this challenge, presenting the first (asymptotically) tight bound on
the complexity of set agreement in such systems. We introduce a novel technique
for simulating, in a fault-prone asynchronous shared memory, executions of an
asynchronous and failure-prone message-passing system in which some fragments
appear synchronous to some processes. We use this simulation technique to derive
a lower bound on the round complexity of set agreement in a partially synchronous
system by a reduction from asynchronous wait-free set agreement. Specifically,
we show that every set agreement protocol requires at least $\lfloor\frac t k
\rfloor + 2$ synchronous rounds to decide. We present an (asymptotically) matching
algorithm that relies on a distributed asynchrony detection mechanism to decide
as soon as possible during periods of synchrony. From these two results, we derive
the size of the minimal window of synchrony needed to solve set agreement. By
relating synchronous, asynchronous and partially synchronous environments, our
simulation technique is of independent interest. In particular, it allows us to
obtain a new lower bound on the complexity of early deciding k-set agreement complementary
to that of Gafni et al. (in SIAM J. Comput. 40(1):63-78, 2011), and to re-derive
the combinatorial topology lower bound of Guerraoui et al. (in Theor. Comput.
Sci. 410(6-7):570-580, 2009) in an algorithmic way.
acknowledgement: "We would like to thank Hagit Attiya, Keren Censor-Hillel, and
the anonymous\r\nreviewers for their feedback on drafts of this paper.\r\nPart
of the work was performed as C. Travers was a Post-Doctoral Fellow at the Technion,
Haifa,\r\nsupported by the “Sam & Cecilia Neaman” Fellowship. Part of the work was
performed as S. Gilbert was\r\na Post-Doctoral Fellow at the Swiss Federal Institute
of Technology, Lausanne, Switzerland."
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. Of choices, failures and
asynchrony: the many faces of set agreement. Algorithmica (New York). 2012;62(1-2):595-629.
doi:10.1007/s00453-011-9581-7'
apa: 'Alistarh, D.-A., Gilbert, S., Guerraoui, R., & Travers, C. (2012). Of
choices, failures and asynchrony: the many faces of set agreement. Algorithmica
(New York). Springer. https://doi.org/10.1007/s00453-011-9581-7'
chicago: 'Alistarh, Dan-Adrian, Seth Gilbert, Rachid Guerraoui, and Corentin Travers.
“Of Choices, Failures and Asynchrony: The Many Faces of Set Agreement.” Algorithmica
(New York). Springer, 2012. https://doi.org/10.1007/s00453-011-9581-7.'
ieee: 'D.-A. Alistarh, S. Gilbert, R. Guerraoui, and C. Travers, “Of choices, failures
and asynchrony: the many faces of set agreement,” Algorithmica (New York),
vol. 62, no. 1–2. Springer, pp. 595–629, 2012.'
ista: 'Alistarh D-A, Gilbert S, Guerraoui R, Travers C. 2012. Of choices, failures
and asynchrony: the many faces of set agreement. Algorithmica (New York). 62(1–2),
595–629.'
mla: 'Alistarh, Dan-Adrian, et al. “Of Choices, Failures and Asynchrony: The Many
Faces of Set Agreement.” Algorithmica (New York), vol. 62, no. 1–2, Springer,
2012, pp. 595–629, doi:10.1007/s00453-011-9581-7.'
short: D.-A. Alistarh, S. Gilbert, R. Guerraoui, C. Travers, Algorithmica (New York)
62 (2012) 595–629.
date_created: 2018-12-11T11:48:23Z
date_published: 2012-02-01T00:00:00Z
date_updated: 2023-02-23T13:13:02Z
day: '01'
doi: 10.1007/s00453-011-9581-7
extern: '1'
intvolume: ' 62'
issue: 1-2
language:
- iso: eng
month: '02'
oa_version: None
page: 595 - 629
publication: Algorithmica (New York)
publication_status: published
publisher: Springer
publist_id: '6894'
status: public
title: 'Of choices, failures and asynchrony: the many faces of set agreement'
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 62
year: '2012'
...
---
_id: '766'
abstract:
- lang: eng
text: 'Asynchronous task allocation is a fundamental problem in distributed computing
in which p asynchronous processes must execute a set of m tasks. Also known as
write-all or do-all, this problem been studied extensively, both independently
and as a key building block for various distributed algorithms. In this paper,
we break new ground on this classic problem: we introduce the To-Do Tree concurrent
data structure, which improves on the best known randomized and deterministic
upper bounds. In the presence of an adaptive adversary, the randomized To-Do Tree
algorithm has O(m + p log p log2 m) work complexity. We then show that there exists
a deterministic variant of the To-Do Tree algorithm with work complexity O(m +
p log5 m log2 max(m, p)). For all values of m and p, our algorithms are within
log factors of the Ω(m + p log p) lower bound for this problem. The key technical
ingredient in our results is a new approach for analyzing concurrent executions
against a strong adaptive scheduler. This technique allows us to handle the complex
dependencies between the processes'' coin flips and their scheduling, and to tightly
bound the work needed to perform subsets of the tasks.'
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: Michael
full_name: Bender, Michael
last_name: Bender
- first_name: Seth
full_name: Gilbert, Seth
last_name: Gilbert
- first_name: Rachid
full_name: Guerraoui, Rachid
last_name: Guerraoui
citation:
ama: 'Alistarh D-A, Bender M, Gilbert S, Guerraoui R. How to allocate tasks asynchronously.
In: IEEE; 2012:331-340. doi:10.1109/FOCS.2012.41'
apa: 'Alistarh, D.-A., Bender, M., Gilbert, S., & Guerraoui, R. (2012). How
to allocate tasks asynchronously (pp. 331–340). Presented at the FOCS: Foundations
of Computer Science, IEEE. https://doi.org/10.1109/FOCS.2012.41'
chicago: Alistarh, Dan-Adrian, Michael Bender, Seth Gilbert, and Rachid Guerraoui.
“How to Allocate Tasks Asynchronously,” 331–40. IEEE, 2012. https://doi.org/10.1109/FOCS.2012.41.
ieee: 'D.-A. Alistarh, M. Bender, S. Gilbert, and R. Guerraoui, “How to allocate
tasks asynchronously,” presented at the FOCS: Foundations of Computer Science,
2012, pp. 331–340.'
ista: 'Alistarh D-A, Bender M, Gilbert S, Guerraoui R. 2012. How to allocate tasks
asynchronously. FOCS: Foundations of Computer Science, 331–340.'
mla: Alistarh, Dan-Adrian, et al. How to Allocate Tasks Asynchronously. IEEE,
2012, pp. 331–40, doi:10.1109/FOCS.2012.41.
short: D.-A. Alistarh, M. Bender, S. Gilbert, R. Guerraoui, in:, IEEE, 2012, pp.
331–340.
conference:
name: 'FOCS: Foundations of Computer Science'
date_created: 2018-12-11T11:48:23Z
date_published: 2012-01-01T00:00:00Z
date_updated: 2023-02-23T13:13:27Z
day: '01'
doi: 10.1109/FOCS.2012.41
extern: '1'
language:
- iso: eng
month: '01'
oa_version: None
page: 331 - 340
publication_status: published
publisher: IEEE
publist_id: '6890'
status: public
title: How to allocate tasks asynchronously
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2012'
...
---
_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'
...
---
_id: '7749'
abstract:
- lang: eng
text: Although studies on laboratory species and natural populations of vertebrates
have shown reproduction to impair later performance, little is known of the age‐specific
associations between reproduction and survival, and how such findings apply to
the ageing of large, long‐lived species. Herein we develop a framework to examine
population‐level patterns of reproduction and survival across lifespan in long‐lived
organisms, and decompose those changes into individual‐level effects, and the
effects of age‐specific trade‐offs between fitness components. We apply this to
an extensive longitudinal dataset on female semi‐captive Asian timber elephants
(Elephas maximus) and report the first evidence of age‐specific fitness declines
that are driven by age‐specific associations between fitness components in a long‐lived
mammal. Associations between reproduction and survival are positive in early life,
but negative in later life with up to 71% of later‐life survival declines associated
with investing in the production of offspring within this population of this critically
endangered species.
article_processing_charge: No
article_type: original
author:
- first_name: Matthew Richard
full_name: Robinson, Matthew Richard
id: E5D42276-F5DA-11E9-8E24-6303E6697425
last_name: Robinson
orcid: 0000-0001-8982-8813
- first_name: Khyne U
full_name: Mar, Khyne U
last_name: Mar
- first_name: Virpi
full_name: Lummaa, Virpi
last_name: Lummaa
citation:
ama: Robinson MR, Mar KU, Lummaa V. Senescence and age-specific trade-offs between
reproduction and survival in female Asian elephants. Ecology Letters. 2012;15(3):260-266.
doi:10.1111/j.1461-0248.2011.01735.x
apa: Robinson, M. R., Mar, K. U., & Lummaa, V. (2012). Senescence and age-specific
trade-offs between reproduction and survival in female Asian elephants. Ecology
Letters. Wiley. https://doi.org/10.1111/j.1461-0248.2011.01735.x
chicago: Robinson, Matthew Richard, Khyne U Mar, and Virpi Lummaa. “Senescence and
Age-Specific Trade-Offs between Reproduction and Survival in Female Asian Elephants.”
Ecology Letters. Wiley, 2012. https://doi.org/10.1111/j.1461-0248.2011.01735.x.
ieee: M. R. Robinson, K. U. Mar, and V. Lummaa, “Senescence and age-specific trade-offs
between reproduction and survival in female Asian elephants,” Ecology Letters,
vol. 15, no. 3. Wiley, pp. 260–266, 2012.
ista: Robinson MR, Mar KU, Lummaa V. 2012. Senescence and age-specific trade-offs
between reproduction and survival in female Asian elephants. Ecology Letters.
15(3), 260–266.
mla: Robinson, Matthew Richard, et al. “Senescence and Age-Specific Trade-Offs between
Reproduction and Survival in Female Asian Elephants.” Ecology Letters,
vol. 15, no. 3, Wiley, 2012, pp. 260–66, doi:10.1111/j.1461-0248.2011.01735.x.
short: M.R. Robinson, K.U. Mar, V. Lummaa, Ecology Letters 15 (2012) 260–266.
date_created: 2020-04-30T11:01:26Z
date_published: 2012-03-01T00:00:00Z
date_updated: 2021-01-12T08:15:16Z
day: '01'
doi: 10.1111/j.1461-0248.2011.01735.x
extern: '1'
intvolume: ' 15'
issue: '3'
language:
- iso: eng
month: '03'
oa_version: None
page: 260-266
publication: Ecology Letters
publication_identifier:
issn:
- 1461-023X
publication_status: published
publisher: Wiley
quality_controlled: '1'
status: public
title: Senescence and age-specific trade-offs between reproduction and survival in
female Asian elephants
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 15
year: '2012'
...
---
_id: '7748'
abstract:
- lang: eng
text: Female mate choice acts as an important evolutionary force, yet the influence
of the environment on both its expression and the selective pressures acting upon
it remains unknown. We found consistent heritable differences between females
in their choice of mate based on ornament size during a 25‐year study of a population
of collared flycatchers. However, the fitness consequences of mate choice were
dependent on environmental conditions experienced whilst breeding. Females breeding
with highly ornamented males experienced high relative fitness during dry summer
conditions, but low relative fitness during wetter years. Our results imply that
sexual selection within a population can be highly variable and dependent upon
the prevailing weather conditions experienced by individuals.
article_processing_charge: No
article_type: original
author:
- first_name: Matthew Richard
full_name: Robinson, Matthew Richard
id: E5D42276-F5DA-11E9-8E24-6303E6697425
last_name: Robinson
orcid: 0000-0001-8982-8813
- first_name: G.
full_name: Sander van Doorn, G.
last_name: Sander van Doorn
- first_name: Lars
full_name: Gustafsson, Lars
last_name: Gustafsson
- first_name: Anna
full_name: Qvarnström, Anna
last_name: Qvarnström
citation:
ama: Robinson MR, Sander van Doorn G, Gustafsson L, Qvarnström A. Environment-dependent
selection on mate choice in a natural population of birds. Ecology Letters.
2012;15(6):611-618. doi:10.1111/j.1461-0248.2012.01780.x
apa: Robinson, M. R., Sander van Doorn, G., Gustafsson, L., & Qvarnström, A.
(2012). Environment-dependent selection on mate choice in a natural population
of birds. Ecology Letters. Wiley. https://doi.org/10.1111/j.1461-0248.2012.01780.x
chicago: Robinson, Matthew Richard, G. Sander van Doorn, Lars Gustafsson, and Anna
Qvarnström. “Environment-Dependent Selection on Mate Choice in a Natural Population
of Birds.” Ecology Letters. Wiley, 2012. https://doi.org/10.1111/j.1461-0248.2012.01780.x.
ieee: M. R. Robinson, G. Sander van Doorn, L. Gustafsson, and A. Qvarnström, “Environment-dependent
selection on mate choice in a natural population of birds,” Ecology Letters,
vol. 15, no. 6. Wiley, pp. 611–618, 2012.
ista: Robinson MR, Sander van Doorn G, Gustafsson L, Qvarnström A. 2012. Environment-dependent
selection on mate choice in a natural population of birds. Ecology Letters. 15(6),
611–618.
mla: Robinson, Matthew Richard, et al. “Environment-Dependent Selection on Mate
Choice in a Natural Population of Birds.” Ecology Letters, vol. 15, no.
6, Wiley, 2012, pp. 611–18, doi:10.1111/j.1461-0248.2012.01780.x.
short: M.R. Robinson, G. Sander van Doorn, L. Gustafsson, A. Qvarnström, Ecology
Letters 15 (2012) 611–618.
date_created: 2020-04-30T11:01:07Z
date_published: 2012-06-01T00:00:00Z
date_updated: 2021-01-12T08:15:15Z
day: '01'
doi: 10.1111/j.1461-0248.2012.01780.x
extern: '1'
intvolume: ' 15'
issue: '6'
language:
- iso: eng
month: '06'
oa_version: None
page: 611-618
publication: Ecology Letters
publication_identifier:
issn:
- 1461-023X
publication_status: published
publisher: Wiley
quality_controlled: '1'
status: public
title: Environment-dependent selection on mate choice in a natural population of birds
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 15
year: '2012'
...