Logical Clocks, Global Snapshots

Clocks

Partial Ordering

• Define “happened before” (->) without clock
  • If a and b are events in the same process, and a comes before b, then a -> b
  • If a is the sending of a message and b is the receipt of the same message, then a -> b
  • If a -> b and b ->c then a ->
  • Concurrent: a -/> b and b -/> a

Logical Clocks

• For any events $a$, $b$: if $a\to b$ then $C(a)<C(b)$
• C1. If $a$ and $b$ are events in process $P$, and $a$ comes before $b$, then $C_i(a)<C_i(b)$.
• C2. If $a$ is the sending of a message by process $P_i$ and $b$ is the receipt of that message by process $P_i$, then $Ci(a)<Ci(b)$.
• IR1. Each process $P_i$ increments $C_i$ between any two successive events.
• IR2.
  • (a) If event $a$ is the sending of a message $m$ by process $P_i$, then the message $m$ contains a timestamp $T_m=Ci(a)$.
  • (b) Upon receiving a message m, process $P_j$ sets $C_j$ greater than or equal to its present value and greater than $T_m$.

Ordering the Events Totally

• define $\Rightarrow$
  • (i) $C_i(a)<C_j(b)$ or
  • (ii) $C_i(a)=C_j(b)$ and $Pi<Py$ (arbitrary total ordering)
• Mutual exclusion problem
  • (I) A process which has been granted the resource must release it before it can be granted to another process.
  • (II) Different requests for the resource must be granted in the order in which they are made.
  • (III) If every process which is granted the resource eventually releases it, then every request is eventually granted.
• Solution
  • Initial: Request queue contains “$T_0$: $P_0$ request resources”
  • Request: $P_i$ send $T_m$: $P_i$ request to everyone, place the message to its queue
  • Other process place to their queue and ACK
  • Release: $P_i$ remove request message, send release msg to everyone
  • Other process remove req msg from queue
  • Process i is granted the resource if
    • $T_m$: $P_i$ request msg in first of queue
    • $P_i$ received a message from every other process latter than $T_m$

Global Snapshot

• Determine global state

Model of a Distributed System

• event e: (p, s, s', M, c)
  • p: process $p$
  • s: state before
  • s’: state after
  • M: message
  • c: message channel cl3l

Algorithm

• Marker-Sending Rule
  • p sends a marker along c after p records its state and before sending any other messages
• Marker-Receiving Rule

  if q has not recorded its state then
      begin q records its state;
            q records the state c as the empty sequence
      end
  else q records the state of c as the sequence of messages received along c after q’s state was recorded and before q received the marker along c.
  copy

• If graph is strongly connected and one process spontaneously records its state, all processes will record their states in finite time
• Recorded global state might not be any of the occurred global state
  • But the system could have passed through the recorded global states in some equivalent executions
• Run marker algorithm and capture snapshot $S^{\ast }$
  • if $S^{}$stable($y(S^{}) = true$), then the system the stable property holds when the algorithm terminates.
  • else the stable property does not hold when the algorithm is initiated.

In-Class

Motivation

• Synchronization - child fork, wait
• Make, compiles
• distributed debugging
• bank transaction (deposit, withdrawal)

Approach 1: Physical Clock

• Central timeserver
  • + single coordinated time
  • - performance bad
• Local clocks (gettimeofday)
  • Not synchronized
  • Oscillate at different rate
  • drift even if start together
• What if clock is running faster
  • can’t adjust clocks backwards
  • causes problems if process aware of time
• Typical skew
  • ~50 microseconds in data center

Approach 2: Logical Clocks

• Key idea
  • Precise, absolute time doesn’t matter
• Process
  • Sequence of events
    • instructions
    • send msg
    • recv msg
  • events within process have total ordering
• Partial Ordering
  • a, b within process; a comes before b
    • a -> b
  • if a is send of msg + b is recv of msg
    • a -> b
  • if a -> b & b -> c, then
    • a -> b
• Concurrent?
  • If a -/> and b -/> then a||b (Concurrent)
  • Do not know which happened first
  • Not possible for a to casually effect b
• Concurrent is not transitive
  • P1: a -> c, P2 b
  • a||b, b||c but a->c
• Logical clocks
  • Build system of clocks to assign time events such that respect casuality
    • See top [[#Logical Clocks]]

  if C(a) == C(b), a||b? Yes
  if C(b) > C(a), a->b? No
  if a||b, c(a) == c(b)? No
  copy

• Total Ordering
  • Use logical clocks to obtain total ordering across all events
  • partial ordering is unique
  • total ordering is not
• Mutual Exclusion
  • Only 1 process can grab lock at a time
  • Safety - Only 1 process acquires
  • Liveness - All request granted
  • Fairness - grant in order of request
• Anomalous Behavior
  • Can see inconsistencies if other channels exist between processes
• Clock sync algorithm
  • Check instructor note (vector clock)

Distributed Snapshots

• Can’t simultaneously record state everywhre at once

Idea

• Record local state oat different times and combine into meaningful picture
• Make “consistent cut” in logical time to combine
  • Consistent: if all recv have corresponding send
• Reconstruct valid picture of system from snapshots taken at diff points in time
• Consistent cut
• Use to determine if stable property holds