Saltar al contenido ForoHackers

Lamport clocks vs vector clocks, with a timeline you can check by hand

AlgoritmosSistemas distribuidos
#1015 · mutex_mike · · Denunciar

Two processes, P1 and P2, one message. Each event gets a Lamport counter L and a vector V.

Rules. Lamport: tick on every event; on receive, L = max(local, msg) + 1. Vector: each process owns one slot; tick your own slot on every event; on receive, take the element-wise max and then tick your own slot.

P1:  e1(send) ----------- e2(local)
          \
           \  msg
            v
P2:  f1(local) ---- f2(receive e1)

e1: L=1 V=[1,0]
f1: L=1 V=[0,1]
f2: L=2 V=[1,2]    (max(1,1)+1 = 2; max([1,0],[0,1]) then tick slot 2)
e2: L=2 V=[2,0]

Look at e2 and f2. Lamport gives both L=2. Tie-break on process id and you get a total order that says "e2 before f2", which looks meaningful and is not. With vectors, [2,0] and [1,2] are incomparable (neither is element-wise <= the other), so the events are concurrent. That is the whole point:

  • Lamport: if a -> b then L(a) < L(b). The converse is false.
  • Vector: a -> b iff V(a) < V(b). You can detect concurrency, which is what you need to spot conflicting writes.

Cost: a vector is O(number of writers). Fine for 3 replicas, painful for a million clients, which is why real systems prune or use variants.

#1441 · race_condition_rita · · Denunciar

Good example. What I always add: neither clock tells you anything about real time. If your requirement is "the later write wins by wall clock", you are building a different system with different failure modes (skew, leap seconds, VM pauses). Say which one you want before you pick.

#1442 · mutex_mike · · Denunciar

Agreed, Rita. Lamport and vector clocks capture causality only. "Concurrent" here means "neither could have influenced the other", not "at the same instant".

#1443 · r3l1c_0f_bbs · · Denunciar

FidoNet never had clocks at all. Each message carried a PATH line with the nodes it had crossed, and a SEEN-BY line so a system could tell it had already seen a copy. Loop detection by breadcrumbs. Not causality, but the same spirit: carry the history with you.

#1444 · lambda_llama · · Denunciar

In Haskell the vector clock is a Map ProcessId Int with a Semigroup instance (pointwise max), and the "happened-before" check is a partial order. Concurrent events are simply the ones where compare has no answer. Partial orders are lovely.

Inicia sesión o únete para responder.