Project Topics
Get Complete Project Material File(s) Now! »
Topology Aware Leader Election Algorithm for Dynamic Networks
The first proposed algorithm, denoted Topology Aware, assumes reliable communication links with an underlying probe system to detect connection and disconnection of nodes. An incremental update mechanism is used to improve propagation cost of messages over the network. Experiments were conducted on the PeerSim simulator [MJ09], comparing our algorithm to a flooding leader algorithm [VKT04] with Random Waypoint and a periodic single point of interest mobility models. Performance results show that the Topology Aware algorithm outperforms the flooding one considering leader choice stability, number of messages, and average distance to the leader metrics.
Centrality-Based Eventual Leader Election in Dynamic Networks
The first contribution assumes reliable communication channels, which are not suitable for communication environments prone to interference and message collisions. The second proposed eventual leader election algorithm for dynamic networks is the Centrality-based Eventual Leader (CEL), that, similarly to Topology Aware, exploits topological information to improve the choice of a central leader and reduce message exchanges. However, rather than assuming an underlying probe system, CEL has a cross-layer neighbors detection, with a neighbor-aware mechanism, to improve the dissemination of topological knowledge and elect a central leader faster. It uses a self-pruning mechanism based on the topological knowledge, combined with probabilistic gossip, to improve the performance of information propagation.
Evaluationswere conducted on theOMNeT++/INET environment [VH08; MVK19], simulating realistic MANET following the IEEE 802.11n specifications with interference, collision, and messages loss. CEL was compared to Gómez-Calzado et al. algorithm [Góm+13], with Random Walk and Truncated LévyWalk mobility models. Results show that CEL presents better performance than the latter, including fewer message exchanges, shortest paths to the leader, and better stability.
Failures of Communication Channels
There exist different modes of failures for communication channels in the literature.
Section 2.3 presents a similar classification of failure modes for processes that can be adapted to communication channels. As shown in Figure 2.5, crash failures are included in omission failures, which are included in arbitrary failures.
I Crash: in case of a crash of a communication channel, the latter is down and stops transmitting messages.
I Channel omission failure: it corresponds to a message loss in a communication channel, i.e. failing to transmit the message from the outgoing buffer to the incoming one.
I Arbitrary failures: for communication channels, arbitrary failures include messages corruption, messages omission, messages creations or multiple message deliveries. Some arbitrary failures in communication channels can be detected and fix by using error detection and correction, such as checksums or cyclic redundancy checks (CRC).
Therefore, information exchanged by processes on communication channels is not reliable anymore, and security steps may be then required.
Eventual Leader Election Algorithms
As presented in Section 2.9.2, Chandra et al. [CHT96] introduced in 1996 the failure detector, which provides a primitive Leader() satisfying the following property: there is a time after which all correct processes trust the same correct process ?, i.e. the process returned by the Leader() primitive. As cannot be implemented in an asynchronous distributed system where process crashes arise (otherwise it would solve the consensus in such system, which is known to be impossible as seen in Section 2.9.2), any asynchronous system has to be enriched with some assumptions in order to implement [Lar+12]. Note that an algorithm is communication efficient if after some time, the eventual leader is the only process to send messages to all other processes, forever [Agu+01].
Node states and failures
Every node always follows the specification of the algorithm, until a potential fail. It is considered correct if it never fails and never leaves the system during the whole execution. Otherwise, it is considered faulty, until it comes back to the system.
A node can fail by crashing and a failed node can recover, joining the system again with the same unique identifier, i.e. two nodes cannot have the same identifier, as detailed in Section 2.3. Therefore, a node keeps its identifier regardless of its state. However, the node does not recover its state neither the knowledge of the network membership and, thus, is initialized again.
Communication graph
The system is modeled as an undirected graph, as presented in Section 2.6. Two nodes can communicate directly if they are in the transmission range of each other, i.e. a receiver node is located inside the emission range of a sender node. The system assumes that the emission range is the same as the reception range. Therefore, if node 8 can communicate with node 9, node 9 can also communicate with node 8 (bidirectional links). A given node belongs to a connected graph formed by its neighbors, neighbors of its neighbors, and so on, which is called a connected component. Due to the movement, failure, and disconnection of nodes, the system can be divided into two (or more) different connected components. Each of them is considered to be a fully-fledged network in itself, and therefore, eventually elects one leader. Both partial synchrony and algorithmensure that, regardless of topology changes, if the changes cease, each connected component will eventually elect a single leader.
Table of contents :
Abstract
Acknowledgments
Summary
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
