Logical Time in Distributed Systems

Summary

Logical time is a concept in distributed systems that enables processes to order events without relying on synchronized physical clocks. By using logical clocks, systems can establish a consistent event ordering, ensuring that causality is preserved across different processes, even in the absence of a global time reference.

Foundation of Logical Time

Processes and Actions

In a distributed system, multiple processes operate at the same time, each with its own internal state and clock. These processes perform various actions that affect their states and the overall system behavior. The key actions that processes can execute include sending and receiving messages, as well as performing internal operations that do not involve communication with other processes.

Processes: Denoted as $P_{1}$ , $P_{2}$ , …, $P_{N}$ , each with a unique clock ( $C_{i}$ ).
Actions: Processes can perform three types of actions:
- Send: Initiating communication by sending a message.
- Receive: Receiving a message from another process.
- Internal: Actions that do not involve communication but alter the process state.

Events and Histories

Each action executed by a process is associated with an event that represents a significant occurrence in that process’s timeline. The relationship between these events is essential for establishing the order in which they occurred. The history of a process is defined as the complete sequence of events that have taken place, allowing us to analyze the order and causality of actions within that process.

Event Definition: An event ( $e$ ) occurs at a process ( $p$ ) and has an associated action.
Event Ordering:
- A relation exists where an event $e$ precedes another event $e^{'}$ in process $p_{i}$ (denoted as $e \to_{i} e^{'}$ ).
- Events at a process $p_{i}$ forms a total order.
- The history $h_{i}$ of process $p_{i}$ is the complete sequence of events that have occurred, represented as: $hi s t ory (p) =< e_{0}, e_{1}, e_{2}, ... >$ .

Happened-Before Relation

The happened-before relation is a fundamental principle in logical time that helps to define causality between events. It establishes a way to determine the ordering of events based on their occurrence. Events that happen in the same process maintain a direct ordering, while events across different processes may be concurrent and thus not directly comparable. Understanding this relation is crucial for reasoning about the interactions and dependencies between processes in a distributed system.

Formal rules:

H-B 1 (Intra-process ordering)
- $e \to_{i} f$ then $e \to f$
- If event $e$ occurs before event $f$ within the same process $p_{i}$ , then $e$ happens before $f$ globally.
H-B 2 (Message passing rule)
- $se n d (m) \to rece i v e (m)$
- If a message $m$ is sent from one process and received by another, the send event happens before the receive event.
H-B 3 (Transitivity)
- $\forall e, f, g \in E : e \to f \land f \to g \Rightarrow e \to g$
- The happened-before relation is transitive. If event $e$ happens before event $f$ , and $f$ happens before $g$ , then $e$ happens before $g$ .
Concurrent Events
- $e ∥ b ⟺ \neg (e \to b) \land \neg (b \to e)$
- Two events $e$ and $b$ are concurrent if neither happened before the other, meaning they are independent of each other in time.

Event occurring at three processes Causal judgements on above event: $a \to b$ : True - a and b are in the same process. $a \to c$ : True - If we know a is before b and b is before c, then there’s a transitive closure. $a \to f$ : True - Transitive closure. $a \to e$ : False - We dont know because they are on difference processes and we can’t relate them. $e \to c$ : False - Same reason as above. $b \to a$ : False - We know a comes before b. $b \to f$ : True - Transitive closure.

Over approximates causality

Happens-before over-approximates causality, meaning that in reality, an event could have happened before another.

When $a \to b$ , the $a$ might have caused $b$ .
When $a ∣∣ b$ , we know that $a$ can not have caused $b$ . Let $S = s_{1}, ..., s_{n}$ be a total order of events (events in a specific order). If $s_{i} \to s_{j}$ (means that event $s_{i}$ happens before $s_{j}$ ), and $i < j$ (meaning $s_{i}$ comes earlier in the list than $s_{j}$ ), then $S$ is called a causal order.

Lamport Clock

Lamport clocks are a type of logical clock that establish a logical timestamp for each event in a distributed system. This method involves maintaining a counter that is incremented when processes send or receive messages. By using Lamport clocks, systems can create a total ordering of events, which helps in understanding the sequence of actions taken by different processes. However, while useful for ordering, Lamport clocks do not provide a definitive causal relationship between events occurring in separate processes. Time moves downwards instead of sideways. We have an event in process a (1,A). When a message is sent it increments the counter (2,A). When a message is received it increments the counter as well (3,B). It is just a counter and is not related to anything with seconds.

While useful for ordering, Lamport clocks cannot establish a definitive causal relationship between events in different processes. For example, we cannot know for sure that 1C happens before 3A, which is why lamport clocks doesn’t work.

Vector Clock

Vector clocks build upon the concept of Lamport clocks by maintaining a vector of counters—one for each process in the system. This approach allows for a more detailed representation of causality, as it enables processes to track the relationships between their events and those of other processes. Although vector clocks offer improved accuracy in representing event ordering, they come with the disadvantage of increased complexity and resource requirements, especially as the number of processes grows. Vector clocks extend Lamport clocks by maintaining a vector of counters, one for each process. In this example, we have $< A, B, C >$ . $< 2, 2, 0 >$ represents 2 events from $A$ , 2 events from $B$ and nothing from $C$ . If there is a lot of processes running, we have to send a vector as long as the number of processes. This is a big disadvantage if you have a lot of processes. 3 is fine but many is bad.

Vector clocks are better than Lamport clocks because they can detect causally concurrent events, while Lamport clocks can only determine the order of events without identifying concurrency.

Global State

(is in Lecture 07 DISYS)

INDBS Noter

Explorer