Common use of THE PARTIALLY SYNCHRONOUS CASE Clause in Contracts

THE PARTIALLY SYNCHRONOUS CASE. remains to show that agreement is impossible when ℓ > 3t and ℓ ≤ n+3t . To derive a contradiction, assume a Byzan- tine agreement algorithm A exists for such a system. We construct three executions of this algorithm, α, β and γ. In α, process identifiers are assigned as shown in the upper left portion of Figure 4. In this diagram, a process labelled Ai has identifier i and runs the algorithm A correctly, and a process labelled Bi has identifier i and is Byzantine. Note that there are n processes in total. The t Byzantine pro- cesses send no messages and all messages sent by correct processes are delivered. All correct processes have input 0 in α and must therefore decide 0 by some round rα. Execution β is defined similarly, as shown in the upper right 2 Here we prove that having ℓ > 3t+n is necessary and suf- portion of Figure 4. Again, the t Byzantine processes send ficient for solving Byzantine agreement in a partially syn- chronous system, regardless of whether the processes are numerate or innumerate. Intuitively, this condition means that at least 3t+1 of the identifiers must each be assigned to a single process (since 2ℓ − n > 3t). We shall see in Section