TY - JOUR AB - 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. AU - Alistarh, Dan-Adrian AU - Gilbert, Seth AU - Guerraoui, Rachid AU - Travers, Corentin ID - 764 IS - 1-2 JF - Algorithmica (New York) TI - Of choices, failures and asynchrony: the many faces of set agreement VL - 62 ER - TY - CONF AB - 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. AU - Alistarh, Dan-Adrian AU - Bender, Michael AU - Gilbert, Seth AU - Guerraoui, Rachid ID - 766 TI - How to allocate tasks asynchronously ER - TY - JOUR AB - 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. AU - Alistarh, Dan-Adrian AU - Gilbert, Seth AU - Guerraoui, Rachid AU - Travers, Corentin ID - 767 IS - 4 JF - Theory of Computing Systems TI - Generating Fast Indulgent Algorithms VL - 51 ER - TY - JOUR AB - 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. AU - Robinson, Matthew Richard AU - Mar, Khyne U AU - Lummaa, Virpi ID - 7749 IS - 3 JF - Ecology Letters SN - 1461-023X TI - Senescence and age-specific trade-offs between reproduction and survival in female Asian elephants VL - 15 ER - TY - JOUR AB - 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. AU - Robinson, Matthew Richard AU - Sander van Doorn, G. AU - Gustafsson, Lars AU - Qvarnström, Anna ID - 7748 IS - 6 JF - Ecology Letters SN - 1461-023X TI - Environment-dependent selection on mate choice in a natural population of birds VL - 15 ER -