6.1 Contributions

Topology Aware and Centrality-based Eventual Leader (CEL) election algorithms consider dynamic networks, where nodes can move, fail by crash, join and leave the system, and partial synchronous system where network partitions can happen.

The algorithms progressively build and maintain a local knowledge of the network topology and rely only on broadcasts within the transmission range of nodes. They do not require any election communication phase: by using its current topological knowledge, each node can directly deduce at any moment which node is the current leader, by choosing the most central node of its connected component according to the closeness centrality.

The Topology Aware algorithm assumes reliable communication channels, and an underlying probe system to detect connection and disconnection of nodes. It uses an update mechanism to improve propagation cost of messages over the network. Evaluation experiments on top of PeerSim simulator [MJ09] were conducted with Topology Aware to a flooding algorithm based on [VKT04]. Performance results show that, compared to the flooding leader algorithm, Topology Aware improves the leader stability up to 82% depending on mobility models, sends half as many messages, and nodes reach the leader by 11% shorter paths.

Compared to Topology Aware, the Centrality-based Eventual Leader (CEL) algorithm assumes eventually reliable communication channels, closer to realistic environments with interference and message collisions. Communication follows the IEEE 802.11 [09] standard and message loss is handled by CSMA/CA protocol, included in the standard. CEL implements a cross-layer neighbors detection which exploits the beacon messages of the underlying data-link layer and accesses the MAC addresses of the nodes, which are used to construct the topological knowledge of the connected component. In addition, CEL improves communication performance through a self-pruning mechanism combined with a probabilistic gossip. Finally, a neighbor-aware mechanism reduces the sending of redundant knowledge information on the network, which was not the case in the first contribution.

CEL was extensively evaluated on the OMNeT++/INET [Var10; MVK19] environment using both Random Walk and Truncated Lévy Walk mobility models, simulating, therefore, a realistic Mobile Ad Hoc Network (MANET) with interference, collision, and messages loss. Results of performance comparison with [Góm+13] show that CEL presents a good trade-off between the number of messages exchanged, stability of the leader, and the closeness of the leader to the other nodes.

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