Distributed Computing Through Combinatorial Topology

Chapter 6

Byzantine-Resilient Colorless Computation

Abstract

We consider the Byzantine failure model, in which a faulty process can display arbitrary, even malicious, behavior. A faulty process may fall silent; it may also lie about its input, or it may lie about the information it has received from other processes.

Keywords

Byzantine failures; Reliable broadcast; Witnesses

We now turn our attention from the crash failure model, in which a faulty process simply halts, to the Byzantine failure model, in which a faulty process can display arbitrary, even malicious, behavior. We will see that the colorless task computability conditions in the Byzantine model are similar to those in the crash failure model except that , the number of failures that can ...