Abstract
We assume that a message may be delivered by packets through multiple hops and investigate the feasibility and efficiency of an Omega Failure Detector implementation. We prove the existence and sustainability of a leader is exponentially more probable in a multi-hop than in a single-hop implementation.
An implementation is: message efficient if all but finitely many messages are sent by a single process; packet efficient if the number of packets used to transmit a message in all but finitely many messages is linear w.r.t. the number of processes; super packet efficient if the number of channels used by packets to transmit all but finitely many messages is linear.
Our results for deterministic algorithms implementing Omega follow. If reliability and timeliness of messages do not correlate, packet efficiency is impossible. We establish necessary and sufficient conditions for the existence of message and packet efficiency and prove correct our deterministic implementation. We prove the eventuality of channels’ timeliness makes super packet efficiency impossible.
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
Notes
- 1.
In literature, the detector is usually denoted by the Greek letter. However, we use the letter to denote the complexity lower bound. To avoid confusion, we spell out the name of the failure detector in English.
References
Aguilera, M.K., Delporte-Gallet, C., Fauconnier, H., Toueg, S.: On implementing omega in systems with weak reliability and synchrony assumptions. Distrib. Comput. 21(4), 285–314 (2008)
Anta, A.F., Raynal, M.: From an asynchronous intermittent rotating star to an eventual leader. IEEE Trans. Parallel Distrib. Syst. 21(9), 1290–1303 (2010)
Biely, M., Widder, J.: Optimal message-driven implementations of omega with mute processes. ACM Trans. Auton. Adapt. Syst. (TAAS) 4(1), 4 (2009)
Bollobás, B.: Random Graphs, 2nd edn. Cambridge University Press, Cambridge (2001)
Bramas, Q., Foreback, D., Nesterenko, M., Tixeuil, S.: Packet efficient implementation of the omega failure detector, Research Report. UPMC Université Paris VI; Kent State University, February 2016. arXiv:1505.05025
Chandra, T.D., Hadzilacos, V., Toueg, S.: The weakest failure detector for solving consensus. J. ACM 43(4), 685–722 (1996)
Chandra, T.D., Toueg, S.: Unreliable failure detectors for reliable distributed systems. J. ACM 43(2), 225–267 (1996)
Charron-Bost, B., Függer, M., Nowak, T.: Approximate consensus in highly dynamic networks. arXiv preprint arXiv:1408.0620 (2014)
Delporte-Gallet, C., Devismes, S., Fauconnier, H., Larrea, M.: Algorithms for extracting timeliness graphs. In: Patt-Shamir, B., Ekim, T. (eds.) SIROCCO 2010. LNCS, vol. 6058, pp. 127–141. Springer, Heidelberg (2010). doi:10.1007/978-3-642-13284-1_11
Erdös, P., Rényi, A.: On random graphs I. Publ. Math. Debrecen 6, 290–297 (1959)
Fischer, M.J., Lynch, N.A., Paterson, M.S.: Impossibility of distributed consensus with one faulty process. J. ACM 32(2), 374–382 (1985)
Gilbert, E.N.: Random graphs. Ann. Math. Stat. 30(4), 1141–1144 (1959)
Hutle, M., Malkhi, D., Schmid, U., Zhou, L.: Chasing the weakest system model for implementing \(\omega \) and consensus. IEEE Trans. Dependable Secur. Comput. 6(4), 269–281 (2009)
Lafuente, A., Larrea, M., Soraluze, I., Cortiñas, R.: Communication-optimal eventually perfect failure detection in partially synchronous systems. J. Comput. Syst. Sci. 81(2), 383–397 (2015)
Larrea, M., Fernández, A., Arévalo, S.: On the implementation of unreliable failure detectors in partially synchronous systems. IEEE Trans. Comput. 53(7), 815–828 (2004)
Malkhi, D., Oprea, F., Zhou, L.: \(\omega \) meets paxos: leader election and stability without eventual timely links. In: Fraigniaud, P. (ed.) DISC 2005. LNCS, vol. 3724, pp. 199–213. Springer, Heidelberg (2005). doi:10.1007/11561927_16
Mostefaoui, A., Mourgaya, E., Raynal, M.: Asynchronous implementation of failure detectors. In: 43rd Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN), pp. 351–351. IEEE Computer Society (2013)
Mostéfaoui, A., Raynal, M., Travers, C.: Time-free and timer-based assumptions can be combined to obtain eventual leadership. IEEE Trans. Parallel Distrib. Syst. 17(7), 656–666 (2006)
De Prisco, R., Lampson, B.W., Lynch, N.A.: Revisiting the PAXOS algorithm. Theor. Comput. Sci. 243(1–2), 35–91 (2000)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing AG
About this paper
Cite this paper
Bramas, Q., Foreback, D., Nesterenko, M., Tixeuil, S. (2016). Packet Efficient Implementation of the Omega Failure Detector. In: Bonakdarpour, B., Petit, F. (eds) Stabilization, Safety, and Security of Distributed Systems. SSS 2016. Lecture Notes in Computer Science(), vol 10083. Springer, Cham. https://doi.org/10.1007/978-3-319-49259-9_6
Download citation
DOI: https://doi.org/10.1007/978-3-319-49259-9_6
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-49258-2
Online ISBN: 978-3-319-49259-9
eBook Packages: Computer ScienceComputer Science (R0)