Brief Announcement: New Bounds for Partially Synchronous Set Agreement

Dan Alistarh, Seth Gilbert, Rachid Guerraoui, Corentin Travers

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 $\lfloor{{t}\over{k}}+2\rfloor$ 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 $\lfloor{{t}\over{k}}+4\rfloor$ rounds. Together, these results tightly bound the inherent price of tolerating some asynchrony.
BibTeX
@inproceedings{alistarh2010brief,
  author = {Dan Alistarh and Seth Gilbert and Rachid Guerraoui and Corentin Travers},
  title = {{Brief Announcement: New Bounds for Partially Synchronous Set Agreement}},
  booktitle = {DISC},
  year = {2010},
  doi = {10.1007/978-3-642-15763-9\_40},
}

Loading related content...

Figure