The aim of the book is therefore to present a comprehensive overview of correspondence problems, the algorithms that solve them and the associated computability limitations in synchronous distributed messaging systems. In the last section, we saw that there is no completely correct consensus protocol for asynchronous processes. So, to have fault tolerance, we need to make assumptions about the system or the type of errors we can expect. So we assume a synchronous system of processes in which we can detect the absence of a message in one way or another (for example.B. expiration times). Understanding distributed computing is not an easy task. This is due to the many facets of uncertainty that you need to manage and master in order to produce proper distributed software. A previous book Communication and Agreement Abstraction for Fault-tolerant Asynchronous Distributed Systems (published by Morgan & Claypool, 2010) examined problems caused by failures in asynchronous message transmission systems. Being able to effectively solve these fundamental problems with provable guarantees allows application designers to give a precise meaning to the words “cooperate” and “accept” despite errors and to write distributed synchronous programs with properties that can be specified and proven. This book focuses on dealing with the uncertainty created by process errors (crash, omission error, and Byzantine behavior) in synchronous message transfer systems (i.e., systems whose progression is determined by the passage of time). To this end, the book examines the fundamental problems that distributed synchronous processes need to solve.
These fundamental problems concern the correspondence between processes (if processes are unable to agree in some way in the event of errors, no non-trivial problems can be solved). These are consensus, interactive coherence, K-set agreement and non-blocking atomic engagement. We can discuss such an algorithm using the problem of the Byzantine generals. One city is surrounded by Byzantine generals and their armed forces. The generals must agree on a plan of action; that is, they must agree on whether to attack the city or retreat. Some of these generals are traitors and want to prevent loyal generals from reaching a consensus (or worse, getting them to agree on another plane). Any general can send a message directly to any other general and can send oral or written messages through other generals. (Oral messages can be edited by intermediate generals, while written messages are signed and cannot be edited.) Messengers are reliable. It is important to realize here that we are not trying to determine who is traitor and who is not, but we are simply trying to get loyal generals to agree on a value. The worst types of mistakes are those that follow a malicious plan. They are the most troubling because if there is a particular scenario in which the consensus protocol fails, we must assume that malicious processes will experience that scenario.
If we can develop an algorithm to handle malicious errors, this algorithm will also be able to handle random errors, shutdown errors in case of failure or other types of errors. The question now is, “How many traitor generals are needed before a consensus among loyal generals is impossible?” The question provides a different answer for oral and written messages. In arguably the best-known use of anthropomorphism in distributed computing, Lamport et al. [12] introduced the Byzantine general problem paradigm as a model for the problem of consensus in the face of faulty processes sending false messages. Table of Contents: Table of Figures / Synchronous Model, Error Patterns and Correspondence Issues / Consensus and Interactive Consistency in Crash Error Model / Accelerated Decision in Crash Error Model / Simultaneous Consensus despite Crash Errors / From Consensus to K-set Agreement / Non-Blocking Atomic Validation on Crash Errors / K-set Agreement Despite Errors of Omission / Consensus Despite Byzantine Failures / Byzantine Consensus in Models Enriched….
