---
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@'
...