> For the complete documentation index, see [llms.txt](https://sliu583.gitbook.io/blog/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://sliu583.gitbook.io/blog/specific-work/seminar-and-talk/fall-21-reading-list/sundial-fault-tolerant-clock-synchronization-for-datacenters.md).

# Sundial: Fault-tolerant Clock Synchronization for Datacenters

* Need for synchronized clocks in datacenter
  * Simplify or improve existing applications 
    * Disributed databases, consistent snapshots 
  * Enable new applications 
    * Network telemetry
    * One-way delay measurement for congestion-control
    * Distributed logging and debugging 
  * And now, no synchronized clocks with tight bound are available 
* Need for time-uncertainty bound 
  * Wait: a common op for ordering & consistency 
    * Time-uncertainty bound to decides how long to wait to guarantee correctness 
* Need for tighter time-uncertainty bound 
  * Sundia: \~100ns time-uncertainty bound even under failures; 2-3 orders of magnitude better than existing designs 
* State-of-the-art clock synchronization 
  * Calculate offset between 2 clocks (exchanging messages, RTT)
  * Path of messages 
    * Variable and asymmetric delay (forward vs. reverse paths, queuing delay)
    * Best practice: sync between neighboring devices 
  * Network-wide synchronization
    * Spanning tree: clock values distributed along tree edges
  * Periodic sync: clocks can drift apart over time, so periodic synchronization is needed 
* Calculation of time-uncertainty bound 
  * How long has it been since the last time it has synchronized
    * Root's direct children: large bound when affected by failure 
    * Nodes in the sub-tree: large bound all the time to prepare for unnoticed failures 
    * Need **fast recovery** from connectivity failures 
  * How fast the clock can drift away
    * Clocks drift as oscillator frequencies vary with temperature, voltage, and so on 
    * Max drift rate is set conservatively in production (200 ppm in Google TrueTime)
    * Reason: must guarantee correctness 
      * What if we set it more aggressively? A large number of clock-related errors (application consistency etc.) during cooling failures! 
      * Need **very frequent synchronization**
  * Both factors can be very large because of failures: 
    * Frequency-related failures: cooling, voltage fluctuations 
    * Connectivity failures: link/device failure that break the spanning tree 
  * HW-SW codesign
    * HW: message sending & processing, failure detection 
      * Frequent messages \~100 microseconds 
      * Fast failure detection with small timeout 
      * Remote failure detection: synchronous messaging 
    * SW: enable the backup plan (re-configure the HW) 
      * Pre-compute the backup plan (by centralized controller)
        * 1 backup parent per device: multiple options for the backup parent, and device cannot distinguish different failures --> must design backup plan to be generic to different failures 
          * Any single link failure 
          * Any single device failure 
          * Root device failure 
          * Any fault-domain (e.g., rack, pod, power) failure: multiple devices / links go down 
        * Backup plan
          * 1 backup parent per device 
          * 1 backup root: elect itself as the new root when root fails 
            * How to distinguish root failure from other failures? 
            * Key: get independent observation from other nodes
            * 2nd timeout: elect itself as the new root
          * Backup plan that handles fault-domain failures 
            * If one domain failure, Breaks connectivity, takes down backup parent 
            * Avoid this case when computing the backup plan 
    * Two salient features 
      * Frequent synchronization 
      * Fast recovery from connectivity failures 
    * Evaluation 
      * Testbed 
      * Compare with state-of-the-art 
      * Metrics 
      * Scenarios: normal time (no failure), inject failure: link, device, domain 
    * Summary
      * Time-uncertainty bound is the key metric 
        * Existing sub-microsecond solutions fall short because of failures
      * Sundial: HW-SW codesign
        * Device HW: frequent message, sync messaging, fast failure detection
        * Device SW: fast local recovery based on the backup plan
        * Controller: pre-compute the backup plan generic to different failures 
        * First system: \~100 ns time-uncertainty bound, improvements on real applications