Distributed Systems Clocks

• A clock in a distributed system is a mechanism that tracks time across nodes without a central clock.
• Due to multiple machines or locations, maintaining synchronized time across all components can be challenging

Common Approaches to Handling Clocks

• Physical Clock Synchronization synchronizes physical clocks of all nodes using Network Time Protocol (NTP).
• NTP synchronizes computer clocks using a reliable source such as an atomic clock.
• Logical Clocks order events without physical time synchronization, using algorithms like Lamport clocks.
• Lamport clocks assign timestamps to events based on causality, ensuring correct relative ordering.
• Vector Clocks extend logical clocks to capture causality and concurrency.
• Vector clocks assign a vector of timestamps to each event, representing the timestamp from each node.
• Vector clocks help detect and resolve conflicts, such as concurrent updates.
• Hybrid Approaches combine physical clock synchronization with logical or vector clocks, potentially using NTP and logical clocks.
• External Time Services rely on services from third-party providers for high-accuracy time synchronization using atomic clocks.

Logical Clocks for Partial Ordering

• Logical clocks establish a partial ordering of events based on causality, without synchronized physical clocks.
• Logical clocks maintain consistency and ordering in distributed systems where nodes have different notions of time.
• The Lamport logical clock is a well-known algorithm for logical clocks.
• Event Timestamping involves timestamping each event with a logical time value, used to establish a partial ordering.
• Rules for Timestamping include timestamping events at a node with its current logical time.
• When a message is sent, the sender includes its current logical time.
• Upon receiving a message, the receiver updates its logical time to be greater than the maximum of its current logical time and the timestamp received.
• Partial Ordering is provided by logical clocks, where a lower timestamp means an event happened before another however it can't be causal relationship if the timestamps are same or unordered.
• Causality Preservation is ensured by the Lamport logical clock, guaranteeing that the timestamp of an event is less than the timestamp of a subsequent event.
• While providing a straightforward way to establish event ordering the Lamport clock does not reflect real-time order and cannot handle concurrent events without additional mechanisms.
• Logical clocks are fundamental for tasks like debugging, event ordering, and coordination and ensure events are processed consistently across nodes.

Event Timestamping

• Event timestamping assigns timestamps to events across nodes, which is essential for establishing order, causality, and consistency within the system
• Approches include physical timestamps, logical clocks, hybrid approaches and external time services

Physical Timestamps

• Physical timestamps use local clocks, but sole reliance on physical timestamps is challenging due to drift and synchronization issues as they may not accurately reflect the order of events across the system.

Logical Clocks

• Logical Clocks such as Lamport and vector clocks provides an alternative for timestamping in distributed systems, these assign based on causality rather than physical time which allows partial ordering across nodes.
• Lamport Clocks assign each event a unique timestamp based on the local logical time, events are then ordered based on the Lamport timestamps which may not correspond to real-time but ensure causal ordering.
• Vector Clocks exend Lamport clocks and associate a vector of timestamps with each event where each component corresponds to a different process or node for detecting causality and concurrency.

Hybrid Approaches

• Hybrid approaches uses a combination of physical timestamps and logical clocks for event timestamping using local physical clocks and then logical clocks to ensure causality and ordering.

External Time Services

• External Time Services, such as NTP, for event timestamping providing synchronized time across nodes allowing for consistent event ordering based on physical time.
• Event timestamping is crucial for tasks such as distributed transaction processing, distributed consensus, event logging, and debugging.
• Factors such as system requirements, scalability, fault tolerance, and the level of precision are needed for choosing a timestamping approach.