Scalable Byzantine-Fault-Quantifying Clock Synchronization

We present a scalable protocol for establishing bounds on clock synchronization in the presence of Byzantine faults. The worst a faulty participant can do to a correct host is cause the correct host to establish (arbitrarily) weak but correct bounds; because the correct hosts knows what those bounds are, we refer to the protocol as Byzantine-fault quantifying. Correct hosts can use the quantified bounds to inform path selection, enabling them to route around misbehaving hosts.

We describe how to employ the protocol in a practical environment that makes use of Byzantine-fault tolerant replicated state machines.