China
Africa
Explore chapters and articles related to this topic
Distributed Consensus and Fault Tolerance Mechanisms
Published in Kuan-Ching Li, Xiaofeng Chen, Hai Jiang, Elisa Bertino, Essentials of Blockchain Technology, 2019
The goal of Basic Paxos is to achieve consensus on a single value among processes, and once this value is chosen, it cannot be changed in the future. Paxos defines three roles: Proposer, Acceptor, and Learner. A proposer receives client requests asking for a specific value (e.g., a state machine command) to be chosen, proposes the value to acceptors, and actively moves forward the protocol in order to convince acceptors to choose the value. Acceptors vote for a proposed value from proposers, and their votes are collected by proposers to decide which value has been chosen. Learners take action (e.g., execute a code piece) based on the chosen value and return results to clients and, therefore, must be informed once a value is chosen. A single processor can play one or more roles at the same time.
Security and Privacy in IoT
Published in Brojo Kishore Mishra, Sanjay Kumar Kuanar, Sheng-Lung Peng, Daniel D. Dasig, Handbook of IoT and Blockchain, 2020
Neelamani Samal, Debasis Gountia
The first ever consensus algorithm, Paxos, was proposed by Lamport with the objective of choosing a single value under crash or network fault. The idea behind Paxos is very simple: All the nodes in the network have been categorized into three types; namely the proposers, the acceptors and the learners. Everyone is a learner in the network that learns the consensus value. The proposer initially prepares a proposal with a proposal number known as a prepare message and sends it to the acceptors. This proposal number forms a timeline and the biggest number is considered up to date. Each acceptor compares received proposal number with current known values for each proposer’s proposal message. If it gets a higher number, then it accepts the proposal or otherwise declines it. Then the acceptor prepares a response message of the following form: Prepare response where the proposal number is the biggest number the acceptor has seen and accepted values are the already accepted values from another proposer. Next a vote is taken based on the majority decision. The proposer checks whether the majority of the acceptors have rejected the proposal. If yes, then the proposer updates it with the latest proposal number. If no, then the proposer further checks whether the majority of the acceptors have already accepted values. If yes then the proposer’s value cannot be selected or otherwise it sends an accept message. Finally, the proposer sends an accept message with the following format to all the acceptors. Whenever the acceptor accepts a value, it informs the learner nodes about it so that everyone will learn about the accepted value. If more than (Nonce/2 – 1) acceptors fail, then no proposer will get enough reply messages to form a conclusion and we cannot reach consensus. Even though the concept behind Paxos is very simple to understand, the theoretical proof is very complicated. Real-life application of this may need to go for a sequence of selections which is known as a multi-Paxos system. Multi-Paxos systems need a repeated application of Paxos which increases the system complexity. This is because the number of messages exchanged between the nodes also increases. There is also a chance of livelock or starvation in Paxos-based systems.
An election algorithm to ensure the high availability of leader in large mobile ad hoc networks
Published in International Journal of Parallel, Emergent and Distributed Systems, 2018
Shantanu Sharma, Awadhesh Kumar Singh
The LE is a prerequisite for numerous applications. For example, the classical consensus algorithm, Paxos [23], requires a distinguished node as a leader that is responsible for progress of the algorithm. Several applications in MANETs such as intrusion detection [20,28], group communication and data exchange [33], token generation in the token passing system [26], key distribution [25], consensus [4], virtual cellular backbone [10], and routing coordination [1,19] require the presence of a leader. Hence, the LE is a widely studied problem of distributed systems. A large MANET involves around a thousand or more mobile nodes (for a special military-rescue mission, emergency scenario, etc.). Thus, in a large MANET, whenever the leader fails, it is cumbersome to trigger an entirely new instance of the LE algorithm. This fact entails that the higher availability of a leader is a necessity of any large MANET, in order to avoid the application discontinuity between initiation and termination of an LE algorithm, in case the current leader fails. Furthermore, the higher availability of a leader avoids overheads due to the repeated invocation of LE algorithm. Thus, it ensures the application continuity and efficient utilization of node’s resources.