Clock Synchronization

- What's the goal of clock sync?
  - What level of sync can you have over WANs? (ms)
    - How much clock skew is there?  30-70 nanosec/hour? 1/2 second drifts per
      day!
   - Clock sync works with a masterthat gives out "correct"
     time, and a bunch of slaves that use it to sync their
     clocks
  - Whatdoes it mean to be correct? Internal consistency, external consistency
    of clocks.
  - Quartz crystall oscillators: dfferent sizes of crystalls, impurities in the
    crystalls, changes in the oscillation paths due to tmp, result in slightly different oscillation patterns, hence skew.
   - Exists a bounded and known drift rate in each clock.

  - Exists very few authoritative clocks in the world, those are engineered to
    be as identical as possible, with atomic oscillations.

- Simple algorithm:  Passive receivers.
  - Have the master broadcasts its time using radio, which is bounded by speed of light.  Hence some skew.  But more than that, how off
  - Can back in time.
  - Speed of light ensures that I don't get external consistency.
  - Doesn't give internal consistency (I may be situated in a different place
    than you, hence our distances to master may vary and cause internal inconsistency.

- Option 2: Use the Internet to get the time (NTP).
  - Even more skew b/c of unpredictability in bounds at which messages are
    delivered.
  - Min: hard to know it over the Internet and with loaded computers, so it's
    hard to be exact about the min. Different paths can have different minima.
  - Medium: .
  - Max: we shouldn't assume a max.
  - So: issue: variable propagation delay, unknown to the receiver, so it has no
    way of compensating for that.
  - So: how to engineer a protocol for time sync, how do we do that w/o knowing
    the propagation delay.  Solution: the slave interogates master and measures stuff locally.

- Solution: Interrogation-based protocols
  - Draw diagram, show simple
  - If propagation is symmetric, then you can get exact: T2 = T1 + (T2-T0)/2
  - But: - Master takes non-zero delay to process.  That processing delay can be
    variable.  NTP paper separates that into 4 times.  But ignore
         - Another but: asymmetric delays can screw up.

= Why is clock sync hard?
  - Draw propagation delays x axis, % messages y axes. 
    - There is a min, a common mode of operation (common xdelay), and then an
      unbounded maximum.

- Requirements for clock sync:
    - clock should grow incrementally (think of timeouts, consistency issues)
    - 



LOGICAL CLOCKS:
- Example: distributed make, with FTC file and client timestamps.
- Problem: clocks aren't sync'ed, so src may go back in time and object
  files will not get re-generated.
- Soluton? Place your 

DISTRIBUTED SNAPSHOTS:
Application: I want to check some stable property of a distributed
system (e.g., deadlock).  But I need global state for that.
Example: distributed particle simulation application.