Byzantine Agreement Algorithm

The objective of the Byzantine margin of error is to protect against system component failures, with or without symptoms, preventing other components of the system from reaching an agreement if such an agreement is necessary for the system to function properly. At the beginning of the project, it was not known how many computers were needed to ensure that a conspiracy of defective computers could not “counteract” the efforts of computers that function properly to reach consensus. Shostak has shown that it takes at least 3n-1 and has developed a two-round 3n-1 messaging protocol that would work for No. 1. His colleague Marshall Pease generalized the algorithm for each > 0 and proved that the 3n-1 is both necessary and sufficient. These results, along with Leslie Lamport`s subsequent evidence on 3n sufficiency with digital signatures, were published in the groundbreaking Document, Reaching Agreement in the Presence of Faults. [9] The authors were awarded the 2005 W. Dijkstra Edsger Prize for this work. The aim of this presentation is to show how to solve the problem of consensus in synchronous and asynchronously distributed communication systems, which are sensitive to Byzantine failures. We represent some limits above the relationship of Byzantine processes that can be tolerated and how these limits evolve according to the expected complexity of the solutions received. In synchronous systems, we present the basic consensus algorithm eIG (exponential information collection) and show how to reduce its exponential complexity.

In the asynchronous model, consensus cannot be resolved in a deterministic way, we will show how to circumvent this impossibility by using timing hypotheses or randomization. To do this and to have more intuitive algorithms, we will introduce a series of primitive diffusion that help reduce noise due to the Byzantine behavior of some of the processes. It can also be relaxed in a more “realistic” problem where faulty components do not collide to attract others into errors. It is in this state of mind that practical algorithms have been developed. The algorithm is run in rounds and requires the clocks to be synchronized between all participating nodes. Each round begins in a constant period of time where recipients can pass a message. The algorithm must work for t-1 number of towers – t being the number of opposing or defective nodes that we can have on our network without reaching a consensus on a message (t is the constant that describes the basic acceptance of network security). In our implementation, each node is a sender and also a recipient for other attempts to agree on messages from other legitimate nodes. We use a modern standard program for cryptographic signatures to authenticate the sender of messages and prevent any changes to the content of messages by man-in-the-middle attacks.

If a sender wishes to reach a consensus on a specific payload in a network of other receiving nodes, the sender`s payload and public key are signed with the sender`s private cryptography key and the signature is added next to the payload. This allows the receiving nodes to verify the content and origin of this message. A resistant or Byzantine Byzantine protocol or algorithm is a robust algorithm for all types of errors mentioned above. For example, if a space shuttle with multiple redundant processors, when processors give conflicting data, what processors or sets of processors should be believed? The solution can be formulated as a Byzantine protocol tolerant of errors.