Fault-Tolerant Networks and Graph Connectivity

Let the vertices of a graph denote computer processes which communicate by passing messages along edges. It has been a standard Computer Science problem to provide algorithms that let the processes solve problems jointly (e.g. leader election, clock synchronization). What if some of the processes are maliciously faulty, i.e. send messages calculated to sabotage joint algorithms? Here we review a few “byzantine agreement” algorithms with interesting graph-theoretic features and raise questions about graph connectivity and diameter (with a few answers).