Bibliography

[09]

IEEE Std 802.11n-2009 – Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications Amendment 5: Enhancements for Higher Throughput. 2009. doi: 10.1109/IEEESTD.2009.5307322.

[Abr88]

Karl Abrahamson. ‘On achieving consensus using a shared memory’. In: Proceedings of the seventh annual ACM Symposium on Principles of distributed computing. 1988, pp. 291–302.

[Afe85]

Yehuda Afek. ‘Distributed algorithms for election in unidirectional and complete networks (traversal, synchronous, leader, asynchronous, complexity).’ PhD thesis. University of California, Nov. 1985.

[AG85]

Yehuda Afek and Eli Gafni. ‘Time and message bounds for election in synchronous and asynchronous complete networks’. In: Proceedings of the fourth annual ACM symposium on Principles of distributed computing. 1985, pp. 186–195.

[Agu+01]

Marcos Kawazoe Aguilera et al. ‘Stable Leader Election’. In: Distributed Computing, 15th Int. Conference, DISC 2001, Proc. 2001, pp. 108–122.

[Agu+03]

Marcos K Aguilera et al. ‘On implementing omega with weak reliability and synchrony assumptions’. In: The 22nd annual symposium on Principles of distributed computing. 2003, pp. 306–314.

[Agu+04]

Marcos K Aguilera et al. ‘Communication-efficient leader election and consensus with limited link synchrony’. In: Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing. 2004, pp. 328–337.

[Agu+08]

Marcos K Aguilera et al. ‘On implementing omega in systems with weak reliability and synchrony assumptions’. In: Distributed Computing 21.4 (2008), pp. 285–314.

[Agu04]

Marcos K Aguilera. ‘A pleasant stroll through the land of infinitely many creatures’. In: ACM Sigact News 35.2 (2004), pp. 36–59.

[AJR10]

Antonio Fernández Anta, Ernesto Jiménez, and Michel Raynal. ‘Eventual Leader Election with Weak Assumptions on Initial Knowledge, Communication Reliability, and Synchrony’. In: J. Comput. Sci. Technol. 25.6 (2010), pp. 1267–1281. doi: 10.1007/s11390-010-9404-3. url: https://doi.org/10.1007/s11390-010-9404-3.

[And00]

Gregory R Andrews. Foundations of multithreaded, parallel, and distributed programming. Vol. 11. Addison-Wesley Reading, 2000.

[Ang80]

Dana Angluin. ‘Local and global properties in networks of processors’. In: Proceedings of the twelfth annual ACM symposium on Theory of computing. 1980, pp. 82–93.

[Ara+13]

Luciana Arantes et al. ‘Eventual Leader Election in Evolving Mobile Networks’. In: Principles of Distributed Systems - 17th International Conference, OPODIS 2013, Nice, France, December 16-18, 2013. Proceedings. Ed. by Roberto Baldoni, Nicolas Nisse, and Maarten van Steen. Vol. 8304. Lecture Notes in Computer Science. Springer, 2013, pp. 23–37. doi: 10.1007/978-3-319-03850-6“˙3. url: https://doi.org/10.1007/978-3-319-03850-6%5C_3.

[Asc+10]

Nils Aschenbruck et al. ‘Bonnmotion: a mobility scenario generation and analysis tool’. In: Proceedings of the 3rd international ICST conference on simulation tools and techniques. 2010, pp. 1–10.

[AW04]

Hagit Attiya and Jennifer Welch. Distributed computing: fundamentals, simulations, and advanced topics. Vol. 19. John Wiley & Sons, 2004.

[Awe87]

Baruch Awerbuch. ‘Optimal distributed algorithms for minimum weight spanning tree, counting, leader election, and related problems’. In: The 19th annual ACM symposium on Theory of computing. 1987, pp. 230–240.

[Bab79]

László Babai. ‘Monte-Carlo algorithms in graph isomorphism testing’. In: Université tde Montréal Technical Report, DMS 79-10 (1979).

[Bav50]

Alex Bavelas. ‘Communication patterns in task-oriented groups’. In: The journal of the acoustical society of America 22.6 (1950), pp. 725–730.

[BBF16]

Ulrik Brandes, Stephen P Borgatti, and Linton C Freeman. ‘Maintaining the duality of closeness and betweenness centrality’. In: Social Networks 44 (2016), pp. 153–159.

[BCT96]

Anindya Basu, Bernadette Charron-Bost, and Sam Toueg. Solving problems in the presence of process crashes and lossy links. Tech. rep. Cornell University, 1996.

[BE06]

Stephen P Borgatti and Martin G Everett. ‘A graph-theoretic perspective on centrality’. In: Social networks 28.4 (2006), pp. 466–484.

[Ber04]

Marin Bertier. ‘Service de détection de défaillances hiérarchique’. PhD thesis. Paris 6, 2004.

[BO99]

Bhargav Bellur and Richard G Ogier. ‘A reliable, efficient topology broadcast protocol for dynamic networks’. In: INFOCOM’99. Conference on Computer Communications. 18th Annual Joint Conference of the IEEE Computer and Communications Societies. Vol. 1. IEEE. 1999, pp. 178–186.

[Bor05]

Stephen P Borgatti. ‘Centrality and network flow’. In: Social networks 27.1 (2005), pp. 55–71.

[BP98]

Sergey Brin and Lawrence Page. ‘The anatomy of a large-scale hypertextual web search engine’. In: Computer networks and ISDN systems 30.1-7 (1998), pp. 107–117.

[Bra01]

Ulrik Brandes. ‘A faster algorithm for betweenness centrality’. In: Journal of mathematical sociology 25.2 (2001), pp. 163–177.

[BRS12]

Martin Biely, Peter Robinson, and Ulrich Schmid. ‘Agreement in directed dynamic networks’. In: International Colloquium on Structural Information and Communication Complexity. Springer. 2012, pp. 73–84.

[Bur80]

James E Burns. ‘A formal model for message-passing systems’. In: Technical Report 91 (1980).

[Cal15]

Carlos Gómez Calzado. ‘Contributions on agreement in dynamic distributed systems’. PhD thesis. Universidad del País Vasco-Euskal Herriko Unibertsitatea, 2015.

[Cam20]

Christian Robert Fernandez Campusano. ‘Distributed eventual leader election in the crash-recovery and general omission failure models’. PhD thesis. Universidad del País Vasco-Euskal Herriko Unibertsitatea, 2020.

[Cas+11]

Arnaud Casteigts et al. ‘Time-varying graphs and dynamic networks’. In: Int. Conference on Ad-Hoc Networks and Wireless. Springer. 2011, pp. 346–359.

[CBD02]

Tracy Camp, Jeff Boleng, and Vanessa Davies. ‘A survey of mobility models for ad hoc network research’. In: Wireless communications and mobile computing 2.5 (2002), pp. 483–502.

[CBL18]

Rodolfo WL Coutinho, Azzedine Boukerche, and Antonio AF Loureiro. ‘Design guidelines for information-centric connected and autonomous vehicles’. In: IEEE Communications Magazine 56.10 (2018), pp. 85–91.

[CGR11]

Christian Cachin, Rachid Guerraoui, and Luís Rodrigues. Introduction to reliable and secure distributed programming. Springer Science & Business Media, 2011.

[Cha82]

Ernest J. H. Chang. ‘Echo algorithms: Depth parallel operations on general graphs’. In: IEEE Transactions on Software Engineering 4 (1982), pp. 391–401.

[CHT96]

Tushar Deepak Chandra, Vassos Hadzilacos, and Sam Toueg. ‘The weakest failure detector for solving consensus’. In: Journal of the ACM (JACM) 43.4 (1996), pp. 685–722.

[Coh+14]

Edith Cohen et al. ‘Computing classic closeness centrality, at scale’. In: Proceedings of the second ACM conference on Online social networks. 2014, pp. 37–50.

[Com99]

Standards Comnittee. Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications. IEEE Standard 802.11. 1999.

[Cor+09]

Thomas H Cormen et al. Introduction to algorithms. MIT press, 2009.

[CR79]

Ernest Chang and Rosemary Roberts. ‘An improved algorithm for decentralized extrema-finding in circular configurations of processes’. In: Communications of the ACM 22.5 (1979), pp. 281–283.

[CT85]

Francis Chin and HF Ting. ‘An almost linear time and O (nlogn+ e) messages distributed algorithm for minimum-weight spanning trees’. In: 26th Annual Symposium on Foundations of Computer Science (sfcs 1985). IEEE. 1985, pp. 257–266.

[CT96]

Tushar Deepak Chandra and Sam Toueg. ‘Unreliable failure detectors for reliable distributed systems’. In: Journal of the ACM (JACM) 43.2 (1996), pp. 225–267.

[Dal77]

Yogen Kantilal Dalal. Broadcast protocols in packet switched computer networks. Stanford University, 1977.

[Dem+87]

Alan Demers et al. ‘Epidemic algorithms for replicated database maintenance’. In: Proceedings of the sixth annual ACM Symposium on Principles of distributed computing. 1987, pp. 1–12.

[DKR82]

Danny Dolev, Maria Klawe, and Michael Rodeh. ‘An O (n log n) unidirectional distributed algorithm for extrema finding in a circle’. In: Journal of algorithms 3.3 (1982), pp. 245–260.

[DLS88]

Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. ‘Consensus in the presence of partial synchrony’. In: Journal of the ACM (JACM) 35.2 (1988), pp. 288–323.

[Du19]

Donglei Du. ‘Social network analysis: Centrality measures’. In: University of New Brunswick (2019).

[Dub11]

Swan Dubois. ‘Tolerating Transient, Permanent, and Intermittent Failures’. PhD thesis. Université Pierre et Marie Curie-Paris VI, 2011.

[Ein56]

Albert Einstein. Investigations on the Theory of the Brownian Movement. Courier Corporation, 1956.

[Fav+19]

Arnaud Favier et al. ‘Un algorithme d’élection de leader cross-layer pour réseaux mobiles ad hoc (résumé)’. In: COMPAS 2019 - Conférence d’informatique en Parallélisme, Architecture et Système. Anglet, France, June 2019. url: https://hal.inria.fr/hal-03471426.

[Fav+20a]

Arnaud Favier et al. ‘Topology Aware Leader Election Algorithm for Dynamic Networks’. In: 25th IEEE Pacific Rim International Symposium on Dependable Computing, PRDC 2020, Perth, Australia, December 1-4, 2020. IEEE, 2020, pp. 1–10. doi: 10.1109/PRDC50213.2020.00011. url: https://doi.org/10.1109/PRDC50213.2020.00011.

[Fav+20b]

Arnaud Favier et al. ‘Topology Aware Leader Election Algorithm for MANET’. In: COMPAS 2020 - Conférence francophone d’informatique en Parallélisme, Architecture et Système. Lyon, France, June 2020. url: https://hal.inria.fr/hal-03471423.

[Fav+21]

Arnaud Favier et al. ‘Centrality-Based Eventual Leader Election in Dynamic Networks’. In: 20th IEEE International Symposium on Network Computing and Applications, NCA 2021, Boston, MA, USA, November 23-26, 2021. Ed. by Mauro Andreolini, Mirco Marchetti, and Dimiter R. Avresky. IEEE, 2021, pp. 1–8. doi: 10.1109/NCA53618.2021.9685390. url: https://doi.org/10.1109/NCA53618.2021.9685390.

[Fer+17]

Christian Fernández-Campusano et al. ‘A distributed leader election algorithm in crash-recovery and omissive systems’. In: Information Processing Letters 118 (2017), pp. 100–104.

[Fer04]

Afonso Ferreira. ‘Building a reference combinatorial model for MANETs’. In: IEEE network 18.5 (2004), pp. 24–29.

[FJR06]

Antonio Fernández, Ernesto Jiménez, and Michel Raynal. ‘Eventual Leader Election with Weak Assumptions on Initial Knowledge, Communication Reliability, and Synchrony’. In: (2006), pp. 166–178. doi: 10.1109/DSN.2006.34. url: https://doi.org/10.1109/DSN.2006.34.

[FL84]

Greg N Frederickson and Nancy A Lynch. ‘The impact of synchronous communication on the problem of electing a leader in a ring’. In: The 16th annual ACM symposium on Theory of computing. 1984, pp. 493–503.

[FLP85]

Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. ‘Impossibility of Distributed Consensus with One Faulty Process’. In: J. ACM 32.2 (Apr. 1985), pp. 374–382.

[FMS09]

Paola Flocchini, Bernard Mans, and Nicola Santoro. ‘Exploration of periodically varying graphs’. In: International Symposium on Algorithms and Computation. Springer. 2009, pp. 534–543.

[Fra82]

Randolph Franklin. ‘On an improved algorithm for decentralized extrema finding in circular configurations of processors’. In: Communications of the ACM 25.5 (1982), pp. 336–337.

[Fre77]

Linton C Freeman. ‘A set of measures of centrality based on betweenness’. In: Sociometry (1977), pp. 35–41.

[Fre78]

Linton C Freeman. ‘Centrality in social networks conceptual clarification’. In: Social networks 1.3 (1978), pp. 215–239.

[Gaf85]

Eli Gafni. ‘Improvements in the time complexity of two message-optimal election algorithms’. In: The 4th annual ACM symposium on Principles of distributed computing. 1985, pp. 175–185.

[Gal77]

Robert G Gallager. ‘Finding a leader in a network with O (e)+ O (n log n) messages’. In: Unpublished Note (1977).

[Gar82]

Hector Garcia-Molina. ‘Elections in a distributed computing system’. In: IEEE transactions on Computers 31.01 (1982), pp. 48–59.

[Gha18]

Marwan Ghanem. ‘Temporal centralities: a study of the importance of nodes in dynamic graphs’. PhD thesis. Sorbonne Universites, UPMC University of Paris 6, 2018.

[GHS83]

Robert G. Gallager, Pierre A. Humblet, and Philip M. Spira. ‘A distributed algorithm for minimum-weight spanning trees’. In: ACM Transactions on Programming Languages and systems (TOPLAS) 5.1 (1983), pp. 66–77.

[GL08]

Rachid Guerraoui and N Lynch. ‘A general characterization of indulgence’. In: ACM Transactions on Autonomous and Adaptive Systems (TAAS) 3.4 (2008), pp. 1–19.

[Góm+13]

Carlos Gómez-Calzado et al. ‘Fault-tolerant leader election in mobile dynamic distributed systems’. In: 19th Pacific Rim Int. Symposium on Dependable Computing. IEEE. 2013, pp. 78–87.

[GR04]

Rachid Guerraoui and Michel Raynal. ‘The information structure of indulgent consensus’. In: IEEE Transactions on Computers 53.4 (2004), pp. 453–466.

[GR06]

Rachid Guerraoui and Luis Rodrigues. Introduction to reliable distributed programming. Springer Science & Business Media, 2006.

[Hal15]

Saurav Haloi. Apache zookeeper essentials. Packt Publishing Ltd, 2015.

[Hat+99]

Kostas P Hatzis et al. ‘Fundamental control algorithms in mobile networks’. In: Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures. 1999, pp. 251–260.

[HHL02]

Zygmunt J Haas, Joseph Y Halpern, and Li Li. ‘Gossip-based ad hoc routing’. In: Proceedings. Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies. Vol. 3. IEEE. 2002, pp. 1707–1716.

[HP93]

Lisa Higham and Teresa Przytycka. ‘A simple, efficient algorithm for maximum finding on rings’. In: Int. Workshop on Distributed Algorithms. Springer. 1993, pp. 249–263.

[HS80]

Daniel S. Hirschberg and James B Sinclair. ‘Decentralized extrema-finding in circular configurations of processors’. In: Communications of the ACM 23.11 (1980), pp. 627–628.

[HT94]

Vassos Hadzilacos and Sam Toueg. A modular approach to fault-tolerant broadcasts and related problems. Tech. rep. Cornell University, 1994.

[Hum83]

Pierre Humblet. ‘A distributed algorithm for minimum weight directed spanning trees’. In: IEEE Transactions on Communications 31.6 (1983), pp. 756–762.

[Hut+08]

Martin Hutle et al. ‘Chasing the weakest system model for implementing Ω and consensus’. In: IEEE Transactions on Dependable and Secure Computing 6.4 (2008), pp. 269–281.

[Ing+09]

Rebecca Ingram et al. ‘An asynchronous leader election algorithm for dynamic networks’. In: Int. Symposium on Parallel & Distributed Processing. IEEE. 2009, pp. 1–12.

[Ing+13]

Rebecca Ingram et al. ‘A leader election algorithm for dynamic networks with causal clocks’. In: Distributed computing 26.2 (2013), pp. 75–97.

[IR81]

Alon Itai and Michael Rodeh. ‘Symmetry breaking in distributive networks’. In: 22nd Annual Symposium on Foundations of Computer Science (sfcs 1981). IEEE. 1981, pp. 150–158.

[JAF06]

Ernesto Jiménez, Sergio Arévalo, and Antonio Fernández. ‘Implementing unreliable failure detectors with unknown membership’. In: Information Processing Letters 100.2 (2006), pp. 60–63.

[Jel+07]

Márk Jelasity et al. ‘Gossip-based peer sampling’. In: ACM Transactions on Computer Systems (TOCS) 25.3 (2007), 8–es.

[Kan78]

P Kanellakis. ‘An election problem in a network’. In: Term paper, MIT (May 1977-1978).

[KKK02]

David Kempe, Jon Kleinberg, and Amit Kumar. ‘Connectivity and inference problems for temporal networks’. In: Journal of Computer and System Sciences 64.4 (2002), pp. 820–842.

[KLO10]

Fabian Kuhn, Nancy Lynch, and Rotem Oshman. ‘Distributed computation in dynamic networks’. In: Proceedings of the forty-second ACM symposium on Theory of computing. 2010, pp. 513–522.

[KMG03]

A-M Kermarrec, Laurent Massoulié, and Ayalvadi J. Ganesh. ‘Probabilistic reliable dissemination in large-scale systems’. In: IEEE Transactions on Parallel and Distributed systems 14.3 (2003), pp. 248–258.

[KMZ84]

Ephraim Korach, Shlomo Moran, and Shmuel Zaks. ‘Tight lower and upper bounds for some distributed algorithms for a complete network of processors’. In: Proceedings of the third annual ACM symposium on Principles of distributed computing. 1984, pp. 199–207.

[Kos09]

Vassilis Kostakos. ‘Temporal graphs’. In: Physica A: Statistical Mechanics and its Applications 388.6 (2009), pp. 1007–1023.

[KW13]

ChongGun Kim and Mary Wu. ‘Leader election on tree-based centrality in ad hoc networks’. In: Telecommunication Systems 52.2 (2013), pp. 661–670.

[Lam77]

Leslie Lamport. ‘Proving the correctness of multiprocess programs’. In: IEEE transactions on software engineering 2 (1977), pp. 125–143.

[Lam78]

Leslie Lamport. ‘Time, Clocks, and the Ordering of Events in a Distributed System’. In: Commun. ACM 21.7 (1978), pp. 558–565.

[Lam87]

Leslie Lamport. distribution. 1987. url: https://lamport.azurewebsites.net/pubs/distributed-system.txt. (accessed: 10.09.2021).

[Lam98]

Leslie Lamport. ‘The part-time parliament’. In: ACM Transactions on Computer Systems (TOCS) 16.2 (1998), pp. 133–169.

[Lar+12]

Mikel Larrea et al. ‘Specifying and implementing an eventual leader service for dynamic systems’. In: International Journal of Web and Grid Services 8.3 (2012), pp. 204–224.

[Le 77]

Gérard Le Lann. ‘Distributed Systems-Towards a Formal Approach.’ In: IFIP congress. Vol. 7. 1977, pp. 155–160.

[LFA00]

Mikel Larrea, Antonio Fernández, and Sergio Arévalo. ‘Optimal Implementation of the Weakest Failure Detector for Solving Consensus’. In: 19th IEEE Symposium on Reliable Distributed Systems, SRDS’00, Proc. 2000, pp. 52–59.

[LK01]

Hyojun Lim and Chongkwon Kim. ‘Flooding in wireless ad hoc networks’. In: Computer Communications 24.3-4 (2001), pp. 353–363.

[LKF07]

Jure Leskovec, Jon M. Kleinberg, and Christos Faloutsos. ‘Graph evolution: Densification and shrinking diameters’. In: ACM Trans. Knowl. Discov. Data 1.1 (2007), p. 2. doi: 10.1145/1217299.1217301. url: https://doi.org/10.1145/1217299.1217301.

[LM10]

Avinash Lakshman and Prashant Malik. ‘Cassandra: a decentralized structured storage system’. In: ACM SIGOPS Operating Systems Review 44.2 (2010), pp. 35–40.

[LMS11]

Mikel Larrea, Cristian Martín, and Iratxe Soraluze. ‘Communication-efficient leader election in crash-recovery systems’. In: Journal of Systems and Software 84.12 (2011), pp. 2186–2195.

[LSP19]

Leslie Lamport, Robert Shostak, and Marshall Pease. ‘The Byzantine generals problem’. In: Concurrency: the Works of Leslie Lamport. 2019, pp. 203–226.

[LT87]

Jan van Leeuwen and Richard B. Tan. ‘An improved upperbound for distributed election in bidirectional rings of processors’. In: Distributed Computing 2.3 (1987), pp. 149–160.

[Lul+15]

Alessandro Lulli et al. ‘Distributed current flow betweenness centrality’. In: 2015 IEEE 9th International Conference on Self-Adaptive and Self-Organizing Systems. IEEE. 2015, pp. 71–80.

[Lyn96]

Nancy A Lynch. ‘Distributed algorithms’. In: Elsevier, 1996. Chap. 4.1, pp. 52–56.

[MA+06]

Salahuddin Mohammad Masum, Amin Ahsan Ali, et al. ‘Asynchronous leader election in mobile ad hoc networks’. In: 20th International Conference on Advanced Information Networking and Applications-Volume 1 (AINA’06). Vol. 2. IEEE. 2006, 5–pp.

[MB12]

Leila Melit and Nadjib Badache. ‘An Ω-Based Leader Election Algorithm for Mobile Ad Hoc Networks’. In: Networked Digital Technologies - 4th International Conference, NDT 2012, Dubai, UAE, April 24-26, 2012. Proceedings, Part I. Ed. by Rachid Benlamri. Vol. 293. Communications in Computer and Information Science. Springer, 2012, pp. 483–490. doi: 10.1007/978-3-642-30507-8“˙41. url: https://doi.org/10.1007/978-3-642-30507-8%5C_41.

[MJ09]

Alberto Montresor and Márk Jelasity. ‘PeerSim: A Scalable P2P Simulator’. In: The 9th Int. Conference on Peer-to-Peer (P2P’09). 2009, pp. 99–100.

[MK99]

Jeff Magee and Jeff Kramer. State models and java programs. Vol. 10. 1999.

[MLJ09]

Cristian Martín, Mikel Larrea, and Ernesto Jiménez. ‘Implementing the omega failure detector in the crash-recovery failure model’. In: Journal of Computer and System Sciences 75.3 (2009), pp. 178–189.

[MMR03]

Achour Mostefaoui, Eric Mourgaya, and Michel Raynal. ‘Asynchronous implementation of failure detectors’. In: 2003 International Conference on Dependable Systems and Networks, 2003. Proceedings. Citeseer. 2003, pp. 351–351.

[Mos+05]

Achour Mostefaoui et al. ‘From static distributed systems to dynamic systems’. In: 24th IEEE Symposium on Reliable Distributed Systems (SRDS’05). IEEE. 2005, pp. 109–118.

[MOZ05]

Dahlia Malkhi, Florin Oprea, and Lidong Zhou. ‘Ω meets paxos: Leader election and stability without eventual timely links’. In: International Symposium on Distributed Computing. Springer. 2005, pp. 199–213.

[MRT04]

Achour Mostefaoui, Michel Raynal, and Corentin Travers. ‘Crash-resilient time-free eventual leadership’. In: Proceedings of the 23rd IEEE International Symposium on Reliable Distributed Systems, 2004. IEEE. 2004, pp. 208–217.

[MRT06]

Achour Mostéfaoui, Michel Raynal, and Corentin Travers. ‘Time-Free and Timer-Based Assumptions Can Be Combined to Obtain Eventual Leadership’. In: IEEE Trans. Parallel Distrib. Syst. 17.7 (2006), pp. 656–666.

[MVK19]

Levente Mészáros, Andras Varga, and Michael Kirsche. ‘Inet framework’. In: Recent Advances in Network Simulation. Springer, 2019, pp. 55–106.

[MWV00]

Navneet Malpani, Jennifer L Welch, and Nitin Vaidya. ‘Leader election algorithms for mobile ad hoc networks’. In: The 4th int. workshop on Discrete algorithms and methods for mobile computing and communications. ACM. 2000, pp. 96–103.

[Nak08]

Satoshi Nakamoto. ‘Bitcoin: A Peer-to-Peer Electronic Cash System’. In: (Oct. 2008). url: https://bitcoin.org/bitcoin.pdf.

[NT09]

Mikhail Nesterenko and Sébastien Tixeuil. ‘Discovering network topology in the presence of byzantine faults’. In: Transactions on Parallel and Distributed Systems 20.12 (2009), pp. 1777–1789.

[OO14]

Diego Ongaro and John Ousterhout. ‘In search of an understandable consensus algorithm’. In: 2014 {USENIX} Annual Technical Conference ({USENIX}{ATC} 14). 2014, pp. 305–319.

[Pap+16]

Michela Papandrea et al. ‘On the properties of human mobility’. In: Computer Communications 87 (2016), pp. 19–36.

[PC97]

Vincent Douglas Park and M Scott Corson. ‘A highly adaptive distributed routing algorithm for mobile wireless networks’. In: Proceedings of INFOCOM’97. Vol. 3. IEEE. 1997, pp. 1405–1413.

[Pel90]

David Peleg. ‘Time-optimal leader election in general networks’. In: Journal of parallel and distributed computing 8.1 (1990), pp. 96–99.

[Pet82]

Gary L Peterson. ‘An O (n log n) unidirectional algorithm for the circular extrema problem’. In: ACM Transactions on Programming Languages and Systems (TOPLAS) 4.4 (1982), pp. 758–762.

[PKR82]

Jan K Pachl, Ephraim Korach, and Doron Rotem. ‘A technique for proving lower bounds for distributed maximum-finding algorithms (Preliminary Version)’. In: Proceedings of the fourteenth annual ACM symposium on Theory of computing. 1982, pp. 378–382.

[RAC08]

Muhammad Rahman, M Abdullah-Al-Wadud, and Oksam Chae. ‘Performance analysis of leader election algorithms in mobile ad hoc networks’. In: Int. J. of Computer Science and Network Security 8.2 (2008), pp. 257–263.

[Ray07]

Michel Raynal. ‘Eventual leader service in unreliable asynchronous systems: Why? how?’ In: Sixth IEEE International Symposium on Network Computing and Applications (NCA 2007). IEEE. 2007, pp. 11–24.

[Ray13]

Michel Raynal. Distributed algorithms for message-passing systems. Vol. 500. Springer, 2013.

[Rhe+11]

Injong Rhee et al. ‘On the levy-walk nature of human mobility’. In: IEEE/ACM transactions on networking 19.3 (2011), pp. 630–643.

[Sab66]

Gert Sabidussi. ‘The centrality index of a graph’. In: Psychometrika 31.4 (1966), pp. 581–603.

[SGK11]

Giovanna Di Marzo Serugendo, Marie-Pierre Gleizes, and Anthony Karageorgos. Self-organising Software. Springer, 2011.

[SM01]

Miguel Sánchez and Pietro Manzoni. ‘ANEJOS: a Java based simulator for ad hoc networks’. In: Future generation computer systems 17.5 (2001), pp. 573–583.

[Spi77]

P Spira. ‘Communication complexity of distributed minimum spanning tree algorithms’. In: The 2nd Berkeley conference on distributed data management and computer networks. 1977.

[Tan+10]

John Tang et al. ‘Characterising temporal distance and reachability in mobile and online social networks’. In: ACM SIGCOMM Computer Communication Review 40.1 (2010), pp. 118–124.

[Tap15]

Tapiocozzo-Wikipedia. Centrality - Wikipedia. 2015. url: https://en.wikipedia.org/wiki/Centrality. (accessed: 06.12.2021).

[TB10]

Sara Tucci-Piergiovanni and Roberto Baldoni. ‘Eventual leader election in infinite arrival message-passing system model with bounded concurrency’. In: 2010 European Dependable Computing Conference. IEEE. 2010, pp. 127–134.

[Tel00]

Gerard Tel. Introduction to distributed algorithms. Cambridge university press, 2000.

[TW+96]

Andrew S Tanenbaum, David J Wetherall, et al. Computer networks. 1996.

[Var10]

Andras Varga. ‘OMNeT++’. In: Modeling and tools for network simulation. Springer, 2010, pp. 35–59.

[VH08]

András Varga and Rudolf Hornig. ‘An overview of the OMNeT++ simulation environment’. In: Proceedings of the 1st international conference on Simulation tools and techniques for communications, networks and systems & workshops. 2008, pp. 1–10.

[VKT04]

Sudarshan Vasudevan, Jim Kurose, and Don Towsley. ‘Design and analysis of a leader election algorithm for mobile ad hoc networks’. In: The 12th int. Conference on Network Protocols, ICNP. IEEE. 2004, pp. 350–360.

[VT17]

Maarten Van Steen and Andrew S Tanenbaum. Distributed Systems. 3. Maarten van Steen Leiden, The Netherlands, 2017. url: distributed-systems.net.

[Woo+14]

Gavin Wood et al. ‘Ethereum: A secure decentralised generalised transaction ledger’. In: Ethereum project yellow paper 151.2014 (2014), pp. 1–32.

[WT15]

Wei Wang and Choon Yik Tang. ‘Distributed estimation of closeness centrality’. In: 2015 54th IEEE Conference on Decision and Control (CDC). IEEE. 2015, pp. 4860–4865.


Table of Contents

1 Introduction
1.1 Contributions
1.1.1 Topology Aware Leader Election Algorithm for Dynamic Networks
1.1.2 Centrality-Based Eventual Leader Election in Dynamic Networks
1.2 Manuscript Organization
1.3 Publications
1.3.1 Articles in International Conferences
1.3.2 Articles in National Conferences
2 Background
2.1 Properties of Distributed Algorithms
2.2 Timing Models
2.3 Process Failures
2.4 Communication Channels
2.5 Failures of Communication Channels
2.6 Distributed Systems
2.6.1 Static Systems
2.6.2 Dynamic Systems
2.7 Centralities
2.8 Messages Dissemination
2.9 Leader Election
2.9.1 Classical Leader Election
2.9.2 Eventual Leader Election
2.10 Conclusion
3 Related Work
3.1 Classical Leader Election Algorithms
3.1.1 Static Systems
3.1.2 Dynamic Systems
3.2 Eventual Leader Election Algorithms
3.2.1 Static Systems
3.2.2 Dynamic Systems
3.3 Conclusion
4 Topology Aware Leader Election Algorithm for Dynamic Networks
4.1 System Model and Assumptions
4.1.1 Node states and failures
4.1.2 Communication graph
4.1.3 Channels
4.1.4 Membership and nodes identity
4.2 Topology Aware Leader Election Algorithm
4.2.1 Pseudo-code
4.2.2 Data structures, variables, and messages (lines 1 to 6)
4.2.3 Initialization (lines 7 to 11)
4.2.4 Periodic updates task (lines 12 to 16)
4.2.5 Connection (lines 20 to 23)
4.2.6 Disconnection (lines 24 to 27)
4.2.7 Knowledge reception (lines 28 to 38)
4.2.8 Updates reception (lines 39 to 53)
4.2.9 Pending updates (lines 54 to 65)
4.2.10 Leader election (lines 17 to 19)
4.2.11 Execution examples
4.3 Simulation Environment
4.3.1 Algorithms
4.3.2 Algorithms Settings
4.3.3 Mobility Models
4.4 Evaluation
4.4.1 Metrics
4.4.2 Instability
4.4.3 Number of messages sent per second
4.4.4 Path to the leader
4.4.5 Fault injection
4.5 Conclusion
5 Centrality-Based Eventual Leader Election in Dynamic Networks
5.1 System Model and Assumptions
5.1.1 Node states and failures
5.1.2 Communication graph
5.1.3 Channels
5.1.4 Membership and nodes identity
5.2 Centrality-Based Eventual Leader Election Algorithm
5.2.1 Pseudo-code
5.2.2 Data structures, messages, and variables (lines 1 to 4)
5.2.3 Initialization (lines 5 to 7)
5.2.4 Node connection (lines 8 to 17)
5.2.5 Node disconnection (lines 18 to 23)
5.2.6 Knowledge update (lines 24 to 34)
5.2.7 Neighbors update (lines 35 to 41)
5.2.8 Information propagation (lines 42 to 47)
5.2.9 Leader election (lines 48 to 52)
5.3 Simulation Environment
5.3.1 Algorithms Settings
5.3.2 Mobility Models
5.4 Evaluation
5.4.1 Metrics
5.4.2 Average number of messages sent per second per node
5.4.3 Average of the median path to the leader
5.4.4 Instability
5.4.5 Focusing on the 60 meters range over time
5.4.6 A comparative analysis with Topology Aware
5.5 Conclusion
6 Conclusion and Future Work
6.1 Contributions
6.2 Future Directions
A Appendix
A.1 Energy consumption per node
A.1.1 Simulation environment
A.1.2 Algorithms settings
A.1.3 Mobility Models
A.1.4 Metric
A.1.5 Performance Results