Abstract
In this paper we investigate deterministic leader election under the simple threshold model of omission dynamic faults: The computation is performed in synchronous steps; if the algorithm sends m messages in one particular step, then at most max {c G − 1,m − 1} of them may be lost without any notification to the sender, where c G is the edge-connectivity of the communication topology. Simple threshold and related models of dynamic faults have been mainly used in the study of information dispersal (broadcasting), while fault-tolerant leader election has been primarily considered in models with static faults.
In this paper we combine these lines of research and present efficient algorithms for leader election on rings and complete networks in the simple threshold model. Somewhat surprisingly, obtaining some leader election is rather straightforward even in this harsh model. However, getting an efficient solution working in general case (arbitrary wake-up, unknown n) involves intricate techniques and careful accounting.
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
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Chlebus, B., Diks, K., Pelc, A.: Broadcasting in synchronous networks with dynamic faults. Networks 27 (1996)
Chlebus, B.S., Diks, K., Pelc, A.: Optimal broadcasting in faulty hypercubes. In: FTCS, pp. 266–273 (1991)
Dobrev, S., Kralovic, R., Pardubska, D.: Leader election in extremely unreliable rings and complete networks. Technical report of Faculty of Mathematics, Physics, and Informatics, Comenius University, Bratislava, Slovakia, TR-2008-016 (2008), http://kedrigern.dcs.fmph.uniba.sk/reports/display.php?id=16
Dobrev, S., Královič, R., Královič, R., Santoro, N.: On fractional dynamic faults with threshold. In: Flocchini, P., Gąsieniec, L. (eds.) SIROCCO 2006. LNCS, vol. 4056, pp. 197–211. Springer, Heidelberg (2006)
Dobrev, S., Pelc, A.: Leader election in rings with nonunique labels. Fundam. Inform. 59(4), 333–347 (2004)
Dobrev, S., Vrťo, I.: Optimal broadcasting in hypercubes with dynamic faults. Information Processing Letters 71(2), 81–85 (1999)
Dobrev, S., Vrťo, I.: Optimal broadcasting in tori with dynamic faults. Parallel Processing Letters 12(1), 17–22 (2002)
Franklin, R.: On an improved algorithm for decentralized extrema finding in circular configurations of processors. Commun. ACM 25(5), 336–337 (1982)
Gasieniec, L., Pelc, A.: Broadcasting with linearly bounded transmission faults. Discrete Applied Mathematics 83(1–3), 121–133 (1998)
Goldreich, O., Shrira, L.: Electing a leader in a ring with link failures. Acta Inf. 24(1), 79–91 (1987)
Hromkovic, J., Klasing, R., Pelc, A., Ruzicka, P., Unger, W.: Dissemination of Information in Communication Networks: Broadcasting, Gossiping, Leader Election, and Fault-Tolerance. Texts in Theoretical Computer Science. An EATCS Series. Springer, New York (2005)
Liptak, Z., Nickelsen, A.: Broadcasting in complete networks with dynamic edge faults. In: Butelle, F. (ed.) OPODIS 2000, Studia Informatica Universalis, pp. 123–142. Suger, France (2000)
Mans, B., Santoro, N.: Optimal fault-tolerant leader election in chordal rings. In: FTCS, pp. 392–401 (1994)
Mans, B., Santoro, N.: Optimal elections in faulty loop networks and applications. IEEE Trans. Computers 47(3), 286–297 (1998)
Marchetti-Spaccamela, A.: New protocols for the election of a leader in a ring. Theor. Comput. Sci. 54, 53–64 (1987)
Marco, G.D., Vaccaro, U.: Broadcasting in hypercubes and star graphs with dynamic faults. Information Processing Letters 66(6), 321–326 (1998)
Peleg, D.: Time-optimal leader election in general networks. J. Parallel Distrib. Comput. 8(1), 96–99 (1990)
Singh, G.: Leader election in the presence of link failures: IEEE Transactions on Parallel and Distributed Systems 7(3), 231–236 (1996)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dobrev, S., Královič, R., Pardubská, D. (2008). Leader Election in Extremely Unreliable Rings and Complete Networks. In: Baker, T.P., Bui, A., Tixeuil, S. (eds) Principles of Distributed Systems. OPODIS 2008. Lecture Notes in Computer Science, vol 5401. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-92221-6_32
Download citation
DOI: https://doi.org/10.1007/978-3-540-92221-6_32
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-92220-9
Online ISBN: 978-3-540-92221-6
eBook Packages: Computer ScienceComputer Science (R0)