SD9.2 · LESSON 2 OF 6

Logical ordering

Explain consensus, logical ordering, leases and fencing under stated failure and timing assumptions.

THE IDEA

Logical ordering

Without trustworthy synchronised clocks, order events logically. A Lamport clock increments on every event and, on receiving a message stamped m, jumps to max(local, m) + 1: if A caused B then A's stamp is smaller. The converse fails: a smaller stamp does not prove causation. Vector clocks keep one counter per process and can say whether two events are ordered or concurrent: [1, 0] and [0, 1] are concurrent, [1, 0] is before [2, 1].

Event 1 of 4

1. P1: local event a → Lamport 1, vector [1, 0]

a = [1, 0] and b = [0, 1]: concurrent (neither could have caused the other) Lamport stamps a = 1 and b = 1; if b were 2 you could not tell "after" from "merely numbered later" so a smaller timestamp never proves causation; vector clocks can detect concurrency

Logical clocks preserve the implication "if A caused B then A's stamp is smaller", not its converse. Wall-clock order also needs synchronisation assumptions you may not have.

Send or withhold a message and watch both clocks.

Predict first. Does timestamp A < B alone prove A caused B?

Chapter context

Coordination lets multiple processes agree on selected shared decisions even though messages can be delayed or lost and participants can stop. Agreement is achieved by a protocol, not by adding a shared timestamp or an informal majority rule.

TRY IT YOURSELF

Part 1. Do it hands-on

Apply the clock rules by hand, then implement Lamport and vector clocks.

Event 1 of 4

1. P1: local event a → Lamport 1, vector [1, 0]

Logical clocks preserve the implication "if A caused B then A's stamp is smaller", not its converse. Wall-clock order also needs synchronisation assumptions you may not have.

P2's Lamport clock after receiving [1,0] vs [0,1] [1,0] vs [2,1] A < B proves A caused B? (yes/no)

To do: Lamport clocks: on receiving a message stamped m, set local = max(local, m) + 1. P2's clock is 1 (after a local event); a message from P1 arrives stamped 2. P2's clock after receiving?
To do: Vector clocks: P1 has [1, 0] and P2 has [0, 1], neither having seen the other. Compare them: before, after, equal or concurrent?
To do: [1, 0] compared with [2, 1]?
To do: Does timestamp A < B alone prove that A caused B? Type yes or no

Part 2. Do it in code

class Lamport: self.t starts at 0. tick() increments and returns the new time (a local event); send() ticks and returns the timestamp to attach; receive(msg_t) sets t = max(t, msg_t) + 1 and returns it.
vc_new(n): a vector of n zeros. vc_tick(vc, i): a NEW vector with component i increased by 1. vc_receive(vc, i, msg_vc): merge (component-wise max) with the message's vector, then tick component i; return the new vector.
vc_compare(a, b): "equal" if identical, "before" if a <= b everywhere and differs somewhere, "after" if a >= b everywhere and differs, otherwise "concurrent".
happened_before(a, b): True only if vc_compare(a, b) == "before".
lamport_implies_causal(ta, tb): ALWAYS False: a smaller Lamport timestamp does not prove causation (it only says A cannot have been caused by B).

class Lamport:
    def __init__(self):
        self.t = 0

    def tick(self):
        pass

    def send(self):
        pass

    def receive(self, msg_t):
        pass

def vc_new(n):
    pass

def vc_tick(vc, i):
    pass

def vc_receive(vc, i, msg_vc):
    pass

def vc_compare(a, b):
    pass

def happened_before(a, b):
    pass

def lamport_implies_causal(ta, tb):
    pass

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

Does timestamp A<B alone prove A caused B?

ANoBYes

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

For a fixed n-member majority group, quorum size is $\lfloor n/2\rfloor+1$ . A 2f+1-member group can lose f members while retaining a majority, provided the remaining participants can communicate and the protocol's other assumptions hold. Fencing requires monotonically ordered tokens and enforcement at the resource.

Worked example

Five members require three votes, allowing two unavailable members while a communicating majority remains. Separately, a resource has already accepted token 8 from a new owner. An old owner's delayed operation bearing token 7 must be rejected, regardless of whether the old process still believes it owns the lease.

Reference code

The following example uses the Python standard library and does not call a remote service.

members=5
quorum=members//2+1
assert quorum == 3 and members-quorum == 2
highest=8
def accept(token):
    global highest
    if token < highest: return False
    highest=token
    return True
assert not accept(7)
assert accept(8)
assert accept(9)

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

A timeout cannot establish a remote process's state. Quorums require full protocol rules. Fencing is ineffective if the resource accepts stale tokens or an attacker can invent authorized tokens.