Unreliable Clocks

• Unreliable Clocks
  • Types of Clocks
    • Physical Clocks
      • Clock Synchronization
      • Time of Day Clocks
      • Monotonic Clock
    • Logical Clocks
      • Vector Clocks
  • Basically when a message is sent, the vector is updated to the node’s current time

Time basics:

• Unix Time begins on the 1st January 1970
• ISO 8601
  • Year:Month:Day:Hour:Min:Sec:TimezoneOffset

Types of Clocks

Physical Clocks

• Quartz clocks are cheap but inaccurate (drift)
  • Drift is measured in parts per million (ppm)
  • 1 ppm = 1microsecond/second
  • 32s/year
  • Most computer clocks write within 50ppm
• Atomic clocks used for accuracy
  • Need to handle Leap Seconds
• Most times, uncertainty is not exposed
• Non synced clocks can lead to ordering problems

Clock Synchronization

• Get time from Atomic Clock or GPS Receiver
• Protocols
  • Network Time Protocol
  • Precision Time Protocol
• Works by sending multiple requests to same server
• Use metrics to reduce network latency variance

Time of Day Clocks

• May suddenly shift due to clock sync (theoretically possible to have negative if unfortunate sync)
• Comparable across nodes, assuming synced

e.g. System.currentTimeMillis()

Monotonic Clock

• Moves forward at constant speed
• Good on a single node

e.g. System.nanoTimer()

Logical Clocks

• Lamport Clocks not handled

Vector Clocks

• Detection of Concurrent Events
• n nodes in a System
  • N = <N_1, N_2, ..., N_n>
• Vector timestamp of an event a is V(a) = <t_1, t_2, ..., t_n>
  • whereby t_i is the timestamp number of events observed by the node N_i
• Each vector timestamp is attached to each message

Basically when a message is sent, the vector is updated to the node’s current time