Logical Time: A Way to Capture Causality in Distributed Systems

Question 1

What problems does knowledge of casual precedence of events (i.e., events ordered by logical time) help us solve?

Answer 1

Distributed algorithms design: Knowing the order of events helps us: 1) ensure liveliness and fairness in mutual exclusion algorithms, 2) helps maintain consistency in replicated databases, and 3) helps design correct deadlock algorithms to avoid phantom and undetected deadlocks.

Tracking of dependent events: 1) In distributed debugging, knowing the order of events helps us construct consistent state for reexamination 2) In failure recovery it helps build a checkpoint 3) In replicated databases it helps detect file inconsistencies in the event of network partitioning

Knowledge about the process: Knowing the order of events helps a process measure of the progress of other processes in a distributed computation, which lets us discard obsolete information, perform garbage collection, and do termination detection

Concurrency measure: The knowledge of how many events are casually dependent is useful for measuring the amount of concurrency in a computation. All events that are not casually related can be executed concurrently.

Question 2

Why are physical clocks insufficient in distributed systems? What is the alternative?

Answer 2

It’s difficult to keep physical clocks precisely synchronized.

Logical clocks are sufficient to capture the causality relation between events.