The problem of consensus can be taken into account in asynchronous or synchronous systems. While in the real world, communication is often asynchronous in nature, it is more convenient and often easier to model synchronous systems, because asynchronous systems naturally involve more problems than synchronous systems. An example of a polynomial consensus protocol that tolerates Byzantine errors is Garay and Berman`s King phase algorithm. The algorithm resolves consensus in a message flow model that is synchronous with n processes and up to f errors, provided that n > 4f. In the phase king algorithm, there are f + 1 phases with 2 turns per phase. Each process follows its preferred output (first equal to the input value of the process). In the first round of each step, each process sends its own preferred value to all other processes. It then receives the values of all processes and determines the value of the majority and its number. In the second round of the phase, the process whose id corresponds to the current phase number is designated king of the phase. The king sends the value of the majority he observed in the first round and serves as a tie-breaker. Each process then updates its preferred value as follows. If the number of the majority observed by the process in the first round is greater than n/2 + f, the process changes its preference to this majority value. Otherwise, the value of the phase king will be used.
At the end of phases f+1, the processes give their preferred values. Three problems of the agreement are interesting: 12 Distributed Agreements Byzantine Agreement: The Problem of the Byzantine Generals (continued) Assuming that any general can reliably disseminate his opinion, loyal generals can reach an agreement! How and under what conditions? 11 Distributed agreement Byzantine agreement: The problem of the Byzantine generals (basic idea) For each loyal general to receive the same set of values, it is enough for each loyal general to use the same value V j for any other general G j to decide The problem of the Bizantine generals is then reduced to the concordance of the generals on the value sent by a certain general: We must have a commanding training general: 1. . . .