BFT-Metronome: A Novel Byzantine Fault-Tolerant Clock Synchronization Algorithm

Abstract

Distributed systems and blockchain consensus protocols rely on a clock synchronization algorithm to resolve any conflicts related to the state of data or resources. Faulty and adversarial peers make it challenging to achieve clock synchronization in a peer-to-peer distributed system. Clock-synchronization protocols such as the Network Time Protocol (NTP) and the Precision Time Protocol (PTP) are effective but only in a partially or fully trusted network. They fail to synchronize clocks in the presence of misbehaving peers who try to rewind or fast-forward time or introduce deadlocks purposely.This paper introduces BFT-Metronome, a Byzantine fault-tolerant clock synchronization algorithm for peer-to-peer distributed systems. The novel BFT-Metronome algorithm combines a sensor-fusion algorithm with a statistical outlier detection algorithm to enable participating peers to determine the most likely skew based on broadcast timestamps. The algorithm is designed to withstand up to $\frac{N}{3} - 1$ misbehaving participants in a network of N total participants, and the independently calculated offset is observed to be within 10 ms of precision vs. 40-100 ms in peer-to-peer distributed systems.The BFT-Metronome clock synchronization algorithm can also be applied to blockchain consensus protocols (such as Proof-of-Stake) that rely on weakly synchronized clocks. This is shown by integrating BFT-Metronome with the Lightweight Mining Algorithm to achieve consensus-round synchronization and timeouts. Then, generalization to other protocols is argued qualitatively. It can also be applied to large distributed systems to secure against insider threats during clock synchronization.