Lesson 2.2: Clocks, events and process states
1. Processes and Events
Definition:
A distributed system consists of multiple processes (p₁, p₂, ..., pₙ) running on separate processors without shared memory. Communication occurs only via message passing.
Key Concepts:
- Process State (sᵢ):
Includes all variables, objects, and local OS resources (e.g., open files) managed by process pᵢ. - Actions:
- Communication: Send/receive messages.
- State Transformation: Modify local variables or resources.
- Events:
Atomic occurrences of actions (e.g., "client sent order" or "server updated log"). Each process orders its events linearly (denoted by →ᵢ).
Example:
In an eCommerce system:
- Event e₁: Client sends order (→ "send_message").
- Event e₂: Server receives order (→ "receive_message").
- Event e₃: Server updates inventory (→ "transform_state").
2. Physical Clocks and Challenges
Hardware Clocks:
- Count crystal oscillations (e.g., quartz at ~10⁶ Hz).
- Converted to software clocks (Cᵢ(t) = αHᵢ(t) + β), where Hᵢ(t) is the hardware reading at real time t.
Problems:
| Issue | Description | Impact |
|---|---|---|
| Clock Skew | Instantaneous difference between two clocks. | Timestamps may misorder events. |
| Clock Drift | Clocks count time at different rates (10⁻⁶–10⁻⁸ s/s). | Clocks diverge over time (e.g., ~1 sec/11.6 days for quartz). |
Example:
- Process p₁'s clock drifts +0.1 sec/day, p₂'s drifts -0.05 sec/day.
- After 10 days: p₁ is 1 sec ahead, p₂ is 0.5 sec behind → 1.5 sec skew.
3. Time Standards and Synchronization
UTC (Coordinated Universal Time):
- Based on atomic clocks (Cs133 oscillator, accurate to 1 part in 10¹³).
- Compensates for Earth's rotational changes via leap seconds.
Synchronization Methods:
| Source | Accuracy | Limitations |
|---|---|---|
| Radio (WWV) | 0.1–10 ms | Limited geographic coverage. |
| GPS Satellites | 1 μs | Requires line-of-sight to satellites. |
Use Case:
Financial systems use GPS-synchronized clocks to timestamp transactions accurately.
4. Logical Time (Lamport Clocks)
Purpose:
Order events without physical clocks using causality.
Algorithm:
- Each process maintains a counter (initialized to 0).
- On local event: Increment counter.
- On sending message: Include current counter in message.
- On receiving message: Set counter = max(local_counter, received_counter) + 1.
Example:
- Process p₁: (A) --send m→ (B) --local→ (C)
- Process p₂: (D) --recv m→ (E) --local→ (F)
Lamport timestamps: A(1), B(2), D(1), E(3), C(3), F(4).
→ Total order: A → D → B → E → C → F.
5. Global State Observation
Chandy-Lamport Snapshot Algorithm:
- Initiation: A process starts snapshot by recording its state and sending markers.
- Propagation: On receiving a marker, processes record their state and forward markers.
- Termination: All processes report states to initiator.
Use Case:
Detecting distributed garbage (no references to an object anywhere in the system).
Key Insights
✅ Physical Clocks: Useful but drift-prone; sync via UTC/GPS.
✅ Logical Clocks: Ensure causal order without physical time.
✅ Global Snapshots: Capture consistent system states for debugging/analysis.
💡 Design Tip: Use logical clocks (e.g., Lamport) when causality matters more than exact timestamps.