Logical Time in Distributed Computing

Origins and Significance of Logical Time

• Foundational Research: The concept of logical time originated from the seminal 1978 paper by Leslie Lamport titled ‐‐Time, Clocks, and the Ordering of Events in a Distributed System,‑‑ published in Communications of the ACM.

• Continued Relevance: The topic remains a central interest in distributed computing. A notable recent contribution is the paper ‐‐Capturing Causality in Distributed Systems‑‑ by Raynal and Singhal.

• Lamport's Recognition: Leslie Lamport's original paper received the PODC Influential Paper Award in 2000.

Applications of Logical Time

• Parallel Computations: Used in visualizations produced by parallel computations to maintain event order.

• Banker System Algorithm: Logical time is essential for the implementation of the banker system algorithm in distributed environments.

• Replicated Data Consistency: Used in efficient solutions for the Replicated Log and Replicated Dictionary problems, specifically the work of Wuu and Bernstein.

Background and Distributed System Model

• System Composition: A distributed computation consists of a set of processes that cooperate and compete to achieve a common goal.

• Communication Constraints: These processes do not share common global memory and communicate solely by passing messages over a communication network.

• Event Classification: Actions within a process are modeled as three types of events:     * Internal Events: These occur within a single process and affect only that process. Logic dictates that events at a process are linearly ordered by their occurrence.     * Message Send Events: Signify the flow of information leaving a process.     * Message Receive Events: Signify the intake of information from another process.

• Causal Dependency: Send and receive events establish a causal dependency from the sender process to the receiver process.

Causality and the Happen‐Before Relation

• Causal Precedence Relation: This is a formal concept used for reasoning, analyzing, and drawing inferences about distributed computations. It helps programmers and the system itself solve problems by knowing the relation between processes.

• Absence of Physical Time: Distributed systems have no built‐in physical time and can only approximate it. Because interactions occur in sporadic "spurts," logical clocks are used to accurately capture causality.

• Asynchronous Processes: Programs are composed of $n$ independent, asynchronous processes: $p_1, p_2, \dots, p_i, \dots, p_n$. These processes do not share a global clock.

• Spontaneity: Each process can execute an event spontaneously. When sending a message, a process does not wait for delivery to complete.

• Internal Sequencing: Each process $p_i$ produces a sequence of events $e_{i0}, e_{i1}, \dots, e_{ix}, e_{i,x+1}, \dots$. These are totally ordered by sequencing:     * $e_{ix} \rightarrow e_{i,x+1}$ (Read: "$e_{ix}$ happens before $e_{i,x+1}$").     * The relation is transitive: $e_{ii} \rightarrow e_{ij}$ for all i < j.

• Inter‐Process Causality: For every message $m$ exchanged between two processes $P_i$ and $P_j$:     * If $e_{ix} = ext{send}(m)$ and $e_{jy} = ext{receive}(m)$, then $e_{ix} \rightarrow e_{jy}$.

• Event Ordering Summary:     * Local events are totally ordered.     * Causality‐linked events are totally ordered.     * Unrelated events are unordered or concurrent ($e_1 || e_2$).     * For any two events $e_1$ and $e_2$, one of three conditions must hold: (i) $e_1 \rightarrow e_2$, (ii) $e_2 \rightarrow e_1$, or (iii) $e_1 || e_2$.

Logical Clock Conditions

• Clock Assignment: Every event is assigned a timestamp according to a specific protocol.

• Clock Consistency Condition: A system satisfies this if:     * If $e_1 \rightarrow e_2$, then C(e_1) < C(e_2), where $C(e_i)$ is the timestamp of event $e_i$.

• Strong Clock Consistency Condition: A clock is strongly consistent if it also satisfies the converse:     * If C(e_1) < C(e_2), then $e_1 \rightarrow e_2$.

Scalar Logical Clocks (Lamport Clocks)

• Protocol Implementation:     * Rule 1 (R1): Before executing any event (send, receive, or internal), process $p_i$ increments its clock: $C_i = C_i + d$ (where d > 0, usually $d = 1$).     * Rule 2 (R2): Every message carries the clock value of the sender at the time of sending ($C_{msg}$). Upon receiving a message, process $p_i$ performs:         * $\text{Ci} = \max(C_i, C_{msg})$.         * Execute Rule 1 (increment).         * Deliver the message.

• Properties:     * The logical clock is monotonically increasing.     * It satisfies the clock consistency condition.     * It does not necessarily satisfy the strong clock consistency condition (e.g., C(e_1) < C(e_2) does not prove $e_1 \rightarrow e_2$).

Vector Logical Clocks

• Structure: Each process $P_i$ out of $n$ processes maintains an integer vector $vti[1 \dots n]$.     * $vti[i]$ is the local logical clock of $p_i$.     * $vti[j]$ is $p_i$'s latest knowledge of $P_j$'s local time.

• Protocol Rules:     * Local Update: Before an event, $vti[i] = vti[i] + d$.     * Message Piggybacking: The sender attaches its current vector clock $vt$ to the message $m$.     * Reception Update: Process $P_i$ updates its vector:         * For $1 \le k \le n: vti[k] = \max(vti[k], vt[k])$.         * $vti[i] = vti[i] + d$.

• Strong Consistency: Vector clocks are strongly consistent.     * e_1 \rightarrow e_2 \iff vt(e_1) < vt(e_2).

• Vector Comparison Logic:     * V_1 < V_2 if for all $i$, $V_1[i] \le V_2[i]$ AND there exists at least one $k$ such that V_1[k] < V_2[k].     * Example 1: $V_1 = {1, 2, 3, 4}$, V_2 = {2, 3, 4, 5} \implies V_1 < V_2.     * Example 2: $V_1 = {1, 2, 3, 4}$, V_2 = {2, 2, 4, 4} \implies V_1 < V_2.     * Example 3: $V_1 = {1, 2, 3, 4}$, $V_2 = {2, 3, 4, 1} \implies$ Unordered/Concurrent.

Matrix Logical Time

• Development: Proposed by Michael and Fischer in 1982.

• Structure: Process $P_i$ maintains an $n \times n$ matrix $mti[1 \dots n, 1 \dots n]$.     * $mti[i, i]$ is the local logical clock of $P_i$.     * Row $i$ corresponds to the vector clock of $P_i$.     * $mti[i, j]$ is the latest knowledge $P_i$ has regarding $P_j$'s local clock ($mtj[j, j]$).     * $mti[j, k]$ represents what $P_i$ knows about $P_j$'s knowledge of $P_k$'s local clock.

• Protocol Rules:     * Local Event: $mti[i, i] = mti[i, i] + d$.     * Reception from $P_j$:         1. Update $P_i$'s knowledge of others via message matrix $mt$: For $1 \le k \le n: mti[i, k] = \max(mti[i, k], mt[j, k])$.         2. Update transitive knowledge for all processes: For $1 \le k \le n$, for $1 \le q \le n: mti[k, q] = \max(mti[k, q], mt[k, q])$.         3. $mti[i, i] = mti[i, i] + d$.

• Comparison Logic:     * M_1 < M_2 if for all $i, j$, $M_1[i, j] \le M_2[i, j]$ AND there exists some $k, p$ such that M_1[k, p] < M_2[k, p].     * Provides strong consistency to determine causal relations.

Replicated Dictionary Problem (Wuu and Bernstein)

• The Problem: A dictionary is replicated across multiple nodes over an unreliable network. Nodes must maintain independent views that are eventually consistent.

• Approach: Unlike standard databases using serializability/locking, Wuu and Bernstein propose a logic‐based algorithm.

• Operations:     * $\text{insert}(x)$: Can be issued by only one node.     * $\text{delete}(x)$: Can be issued by multiple nodes. Invoked at $N_i$ only if $x$ is currently in internal view $V_i$.

• Dictionaries and History:     * $e_x$: The unique insertion event.     * $x‐delete$ event: An event deleting $x$.     * Logic: $x$ is in view $V(e)$ iff $e_x \rightarrow e$ and there exists no $x‐delete$ event $g$ such that $g \rightarrow e$.

• The Log: Each node maintains a log $L$ of events. Each log entry $e_R$ contains: (operation, time, nodeID). Example: (add a, 3, 2).

Wuu and Bernstein Solutions

• Trivial Fault-Tolerant Solution:     * Every event adds a record to local log $L_i$.     * Every message includes the entire log $L_i$.     * Reception involves applying all events in the log to the dictionary view $V_j$.     * Drawbacks: Logs grow unboundedly; excessive communication, computation, and storage costs.

• Improved Solution using Matrix Time:     * Uses matrix clocks $T_i$ to purge records seen by all participants.     * The hasrec Predicate: boolean hasrec(Ti, eR, k) returns true if Ti[k, eR.node] > eR.time. This determines if process $k$ has already seen record $e_R$.     * Node Initialization: Dictionary view $V_i = {}$, Partial Log $Pl_i = {}$, all matrix values = 0.

• Operational Rules for Improved Solution:     * On locally issuing insert/delete: Update matrix clock, add event to $Pl_i$, update $V_i$.     * On sending to node $k$: Create subset $NP$ of $Pl_i$ containing only entries where hasrec(Ti, eR, k) is false. Send $NP$ and matrix clock $T_i$ to node $k$.     * On receiving from node $k$:         1. Extract subset $NE$ from received log where hasrec(Ti, eR, i) is false (new events for node $i$).         2. Update $V_i$ based on $NE$.         3. Update matrix clock $T_i$.         4. Add to $Pl_i$ those records from the received log where hasrec(Ti, eR, j) is false for at least one participant $j$. This ensures the record is kept until everyone has seen it.

• Result: Efficiently minimizes log size in messages and memory while remaining fault‐tolerant and ensuring eventual consistency.