# 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 


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://sliu583.gitbook.io/blog/specific-work/seminar-and-talk/fall-21-reading-list/sundial-fault-tolerant-clock-synchronization-for-datacenters.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.