--- res: bibo_abstract: - Set agreement [4] is a fundamental problem in distributed computing, in which processes collectively choose a small subset of values from a larger set of proposals. Set agreement has been extensively studied in both synchronous and asynchronous systems [10,11,3,5,8,9]. Real world distributed systems, however, are neither purely synchronous nor purely asynchronous. To describe such a system, Dwork et al. [6] introduced the idea of partial synchrony. They assume for every execution some (unknown) time GST (global stabilization time), after which the system is synchronous. In a recent paper [1,2], we study the complexity of set agreement in the context of partially synchronous systems, determining the minimum-sized window of synchrony in which set agreement can be solved. We show that at least ⌊t/k⌋ + 2 synchronous rounds are required for k-set agreement, where t < n is the number of crashes, and k is the agreement parameter of the set agreement task. We then introduce an algorithm that terminates in any window of synchrony of size at least ⌊t/k⌋ + 4 rounds. Together, these results tightly bound the inherent price of tolerating some asynchrony.@eng bibo_authorlist: - foaf_Person: foaf_givenName: Dan-Adrian foaf_name: Alistarh, Dan-Adrian foaf_surname: Alistarh foaf_workInfoHomepage: http://www.librecat.org/personId=4A899BFC-F248-11E8-B48F-1D18A9856A87 orcid: 0000-0003-3650-940X - foaf_Person: foaf_givenName: Seth foaf_name: Gilbert, Seth foaf_surname: Gilbert - foaf_Person: foaf_givenName: Rachid foaf_name: Guerraoui, Rachid foaf_surname: Guerraoui - foaf_Person: foaf_givenName: Corentin foaf_name: Travers, Corentin foaf_surname: Travers bibo_doi: 10.1007/978-3-642-15763-9_40 bibo_volume: 6343 LNCS dct_date: 2010^xs_gYear dct_language: eng dct_publisher: Springer@ dct_title: 'Brief announcement: New bounds for partially synchronous set agreement@' ...