Clock Distribution with Gradient TRIX

Abstract

Gradient clock synchronization (GCS) algorithms minimize the worst-case clock offset between the nodes in a distributed network of diameter D and size n. They achieve optimal offsets of ⊙(log D) locally, i.e., between adjacent nodes [14] and ⊙(D) globally [2]. A key open problem in this area is to achieve fault tolerance at minimal edge replication overhead.In this work, we achieve this goal under the assumption of an average-case distribution of faults, i.e., nodes fail with independent probability p ϵ o(n-1/2). In more detail, we present a self-stabilizing GCS algorithm for a grid-like directed graph with in- and out-degrees of 3. Note that even for tolerating a single fault, this degree is necessary, and if p was larger, it would not hold with probability 1 - o (1) that each node has at most one faulty in-neighbor. Our algorithm achieves asymptotically optimal local skew of ⊙(log D) with probability 1 - o(1); this holds under general worst-case assumptions on link delay and clock speed variations, provided they change slowly relative to the speed of the system.On the one hand, our results are of practical interest. As we discuss, the fault model is suitable for synchronously clocked hardware. Since our algorithm can simultaneously sustain a constant number of arbitrary changes due to faults in each clock cycle, it achieves sufficient robustness to dramatically increase the size of synchronously clocked systems.On the other hand, our results are of a theoretical interest. We show that for a worst-case distribution of f faulty nodes within our fault model's locality constraints, our algorithm achieves local skew O(5f log D). With probabilistically distributed faults, this becomes O(log D). Moreover, our work opens up avenues for further investigation of fault-tolerant synchronization, in particular trade-offs between fault distribution and edge density.