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 \rightarrow 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) \lt C_j(b)$ or
    • (ii) $C_i(a) = C_j(b)$ and $Pi \lt 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.
  • 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^{*}$
    • 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
  • 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