Three terminologies of Happened before Clock Transition-Causal Ordering and Concurrent

Three terminologies of Happened before Clock Transition Causal Ordering and Concurrent.

Happened Before Or Causal Precedence Logical Clocks And Causal Ordering Logical Time Lamport Clocks Causal Relationships In Distributed Computations Lamport Timestamp Distributed Systems Clocks Algorithms In Distributed Computing.

00:00

© 2018 Flowplayer ABAbout FlowplayerGPL based license

Causal Ordering Of Messages In Distributed System Which Event Is Concurrent With The Vector Clock Causal Ordering Example Lamport Clock Example Time, Clocks And The Ordering Of Events In A Distributed System Lamport Clock Vs Vector Clock.

Three Key Terminologies in Distributed Systems: Happened Before, Clock Transition, Causal Ordering, and Concurrency

In distributed systems, events occur in different processes that may not share a common clock. To understand the sequence of events, we use concepts like happened-before relation, clock transition, causal ordering, and concurrency.

 Happened Before (→) Relation (Lamport’s Happened-Before)

• Defined by Leslie Lamport, this relation helps establish an order of events in distributed systems.
• Denoted as: $A\to B$ (Event A happened before Event B)
• Rules:
  1. Same process rule: If two events occur in the same process, the one that appears earlier in execution order happens before the other.
  2. Message passing rule: If event A is a send message event, and event B is the corresponding receive event, then $A\to B$.
  3. Transitivity: If $A\to B$ and $B\to C$, then $A\to C$.

Example: If Process P1 sends a message to Process P2, then the “send event” in P1 happened before the “receive event” in P2.

 Clock Transition (Logical Clocks & Vector Clocks)

• In distributed systems, physical clocks may not be synchronized, so logical clocks are used to track event ordering.
• Two main clock types:
  • Logical Clocks (Lamport Timestamps): Each process maintains a counter that increments for each event. Message passing updates the receiver’s clock accordingly.
  • Vector Clocks: Each process maintains an array of counters representing the logical time of all processes. This captures causality more effectively than Lamport timestamps.

Example:

• If P1 executes an event at T=5 and sends a message, P2 may adjust its time based on received information.
• If P1’s timestamp is T=5 and P2’s was T=3, after receiving the message, P2 updates its time to T=max(5,3)+1=6.

 Causal Ordering & Concurrency

• Causal Ordering: Ensures that events are delivered in the order they were causally related. If $A\to B$, then B cannot happen before A in any observer’s perspective.
• Concurrency (‖): If neither $A\to B$ nor $B\to A$, then A and B are concurrent events. This means they are independent and do not affect each other.

Example:

• If P1 sends a message to P2 and then P2 responds, the second event is causally dependent on the first.
• If P1 and P2 perform independent computations without communicating, their events are concurrent.

Summary Table

Conclusion

These concepts are essential for ensuring correct event sequencing in distributed systems, preventing inconsistencies, and maintaining system synchronization.