On implementing omega with weak reliability and synchrony assumptions Export

@inproceedings{citeulike:4021641, abstract = {We study the feasibility and cost of implementing \Ω---a fundamental failure detector at the core of many algorithms---in systems with weak reliability and synchrony assumptions. Intuitively, \Ω allows processes to eventually elect a common leader. We first give an algorithm that implements \Ω in a weak system S where processes are synchronous, but: (a) any number of them may crash, and (b) only the output links of an unknown correct process are eventually timely (all other links can be asynchronous and/or lossy). This is in contrast to previous implementations of \Ω which assume that a quadratic number of links are eventually timely, or systems that are strong enough to implement the eventually perfect failure detector P . We next show that implementing \Ω in S is expensive: even if we want an implementation that tolerates just one process crash, all correct processes (except possibly one) must send messages forever; moreover, a quadratic number of links must carry messages forever. We then show that with a small additional assumption---the existence of some unknown correct process whose asynchronous links are lossy but fair---we can implement \Ω efficiently: we give an algorithm for \Ω such that eventually only one process (the elected leader) sends messages.}, address = {New York, NY, USA}, author = {Aguilera, Marcos K. and Gallet, Carole D. and Fauconnier, Hugues and Toueg, Sam}, booktitle = {PODC '03: Proceedings of the twenty-second annual symposium on Principles of distributed computing}, citeulike-article-id = {4021641}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=872081}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/872035.872081}, doi = {10.1145/872035.872081}, isbn = {1-58113-708-7}, keywords = {2003, failure\_detectors, implementation, model, omega, synchronous}, location = {Boston, Massachusetts}, pages = {306--314}, posted-at = {2009-02-07 13:14:58}, priority = {2}, publisher = {ACM}, title = {On implementing omega with weak reliability and synchrony assumptions}, url = {http://dx.doi.org/10.1145/872035.872081}, year = {2003} }

TY - CONF ID - citeulike:4021641 L3 - citeulike-article-id:4021641 N2 - We study the feasibility and cost of implementing Ω---a fundamental failure detector at the core of many algorithms---in systems with weak reliability and synchrony assumptions. Intuitively, Ω allows processes to eventually elect a common leader. We first give an algorithm that implements Ω in a weak system S where processes are synchronous, but: (a) any number of them may crash, and (b) only the output links of an unknown correct process are eventually timely (all other links can be asynchronous and/or lossy). This is in contrast to previous implementations of Ω which assume that a quadratic number of links are eventually timely, or systems that are strong enough to implement the eventually perfect failure detector P . We next show that implementing Ω in S is expensive: even if we want an implementation that tolerates just one process crash, all correct processes (except possibly one) must send messages forever; moreover, a quadratic number of links must carry messages forever. We then show that with a small additional assumption---the existence of some unknown correct process whose asynchronous links are lossy but fair---we can implement Ω efficiently: we give an algorithm for Ω such that eventually only one process (the elected leader) sends messages. CY - Boston, Massachusetts SN - 1-58113-708-7 AD - New York, NY, USA EP - 314 TI - On implementing omega with weak reliability and synchrony assumptions PB - ACM T2 - PODC '03: Proceedings of the twenty-second annual symposium on Principles of distributed computing SP - 306 KW - 2003 KW - failure_detectors KW - implementation KW - model KW - omega KW - synchronous AU - Aguilera, Marcos AU - Gallet, Carole AU - Fauconnier, Hugues AU - Toueg, Sam PY - 2003/// UR - http://dx.doi.org/10.1145/872035.872081 ER -