Abstract
Motivation. In recent years, the quest for weak system assumptions, which add just enough synchrony resp. failure information to purely asynchronous systems to circumvent impossibility results, has been an active research topic in distributed computing. Most work in this area has been devoted to (1) identifying weak(est) failure detectors (FDs), and (2) identifying synchrony assumptions just strong enough to implement these weak FDs.
Due to the FLP impossibility result [1], the first focus of this research has been the consensus problem. More recently, k-set agreement (termed set agreement for k = n−1) has been identified as a promising target for further exploring the solvability border in asynchronous systems. As for (1), anti- \({\it \Omega}\) [2] was shown to be the weakest FD for set agreement in shared memory systems: Whereas \({\it \Omega}\) (the weakest FD for solving consensus [3]) outputs the id of one correct process infinitely often, anti-\({\it \Omega}\) outputs the id of one correct process only finitely often. Subsequently, a generalization called anti-\({\it \Omega}_k\) that returns n−k processes has been shown to be the weakest FD for k-set agreement in shared memory system [4,5]. For message passing systems, only the weakest FD for set agreement is known, namely, the “loneliness” failure detector \(\cal{L}\) [6]. Concerning (2), a class of shared memory models for implementing anti-\({\it \Omega}_k\) was presented in [7].
This research was supported by the Austrian BM:vit’s FIT-IT programme (proj. no. 812205) and by Austrian Science Foundation (FWF) (proj. no. P20529).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Fischer, M.J., Lynch, N.A., Paterson, M.S.: Impossibility of distributed consensus with one faulty process. JACM 32, 374–382 (1985)
Zieliński, P.: Automatic classification of eventual failure detectors. In: Pelc, A. (ed.) DISC 2007. LNCS, vol. 4731, pp. 465–479. Springer, Heidelberg (2007)
Chandra, T.D., Hadzilacos, V., Toueg, S.: The weakest failure detector for solving consensus. JACM 43(4), 685–722 (1996)
Gafni, E., Kuznetsov, P.: The weakest failure detector for solving k-set agreement. In: ACM Symposium on Principles of Distributed Computing (2009)
Delporte Gallet, C., Fauconnier, H., Guerraoui, R., Tielmann, A.: Brief announcement: The Disagreement Power of an Adversary. In: ACM Symposium on Principles of Distributed Computing (2009)
Delporte-Gallet, C., Fauconnier, H., Guerraoui, R., Tielmann, A.: The weakest failure detector for message passing set-agreement. In: Taubenfeld, G. (ed.) DISC 2008. LNCS, vol. 5218, pp. 109–120. Springer, Heidelberg (2008)
Aguilera, M.K., Delporte-Gallet, C., Fauconnier, H., Toueg, S.: Partial synchrony based on set timeliness. In: ACM Symposium on Principles of Distributed Computing, PODC 2009 (to appear, 2009)
Biely, M., Robinson, P., Schmid, U.: Weak synchrony models and failure detectors for message passing (k-)set agreement. Research Report 182-51/2009, Inst. f. technische Informatik, TU Wien (2009), http://www.vmars.tuwien.ac.at/php/pserver/docdetail.php?DID=2657&viewmode=paper
Mostéfaoui, A., Raynal, M.: Unreliable failure detectors with limited scope accuracy and an application to consensus. In: Foundations of Software Technology and Theoretical Computer Science, pp. 329–340 (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Biely, M., Robinson, P., Schmid, U. (2009). Brief Announcement: Weak Synchrony Models and Failure Detectors for Message Passing (k-)Set Agreement. In: Keidar, I. (eds) Distributed Computing. DISC 2009. Lecture Notes in Computer Science, vol 5805. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-04355-0_38
Download citation
DOI: https://doi.org/10.1007/978-3-642-04355-0_38
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-04354-3
Online ISBN: 978-3-642-04355-0
eBook Packages: Computer ScienceComputer Science (R0)