Lecture

• multi-core processor
  • is it a distributed system? no
  • the whole processor crashes (we cannot have one core working and other one crashed)
• partial failure
  • in a distributed system, the components may fail independently
  • „distribuovaný systém je to tehdy, když můj počítač přestane fungovat, protože se rozbil počítač, o kterém jsem ani nevěděl, že existuje“
• sharing information, taking a common decision
• why do we want/have a distributed system?
  • users are in different places → it is a distributed system by nature
  • better performance, stability (if one server fails, we have another)

Ordering of Events

• notation
  • set of processes $P=\set{p_1,\dots,p_n}$
  • they communicate through channels (channel from $p_i$ to $p_j$ … $C_{ij}$)
  • event $\# k$ on process $p_i$ … $e_i^k$
    • event changes the state of the process
  • states of the process $\sigma_i^0,\sigma_i^1,\dots$
    • event $e_i^1$ performs the transition from $\sigma^0_i$ to $\sigma_i^1$ on process $p_i$
  • local history $h_i=e^1_i e^2_i e^3_i \dots$
  • global history $H=h_1\cup h_2\cup h_3\dots$
• happened_before ($\to$) relation between two events
  • first case: $e_i^k\to e_i^\ell$ iff $k\lt\ell$
  • second case: send($m$) $\to$ recv($m$)
    • we can receive a message $m$ only after we send it
  • transitivity: $e\to e'\land e'\to e''\implies e\to e''$
  • antisymmetry: $e\to e'\implies e'\not\to e$
  • it is a partial ordering of events
  • if there is no relation between $e$ and $e'$, we say they are concurrent
    • $e||e'$
• global state $(\sigma_1^{k_1},\sigma_2^{k_2},\sigma_3^{k_3},\dots)$
  • global state is composed of the local state of every process
• cut
  • cut $C$ … subset of the global history $H$ that includes a prefix of each local history
  • consistent cut … the global state could have existed
    • cut $C$ is consistent iff $e'\in C\land e\to e'\implies e\in C$
• Chandy-Lamport
  • we assume FIFO channels
  • to save a snapshot, we need an initiator process which is the first to save its state and broadcast the message SNAPSHOT
  • when process $p_i$ receives the SNAPSHOT message, it saves its state and also broadcasts SNAPSHOT (there are no other events in between)
  • the state of channel $c_{ji}$ corresponds to the messages that the process $p_i$ received from $p_j$ between broadcasting SNAPSHOT and receiving SNAPSHOT from $c_j$
  • after $p_i$ receives SNAPSHOT from all processes, it knows that the computation of the snapshot is terminated

Time

• how to put timestamps on events to have guarantees that one event happened before another event?
  • I would like a timestamp function $TS$ such that $e\to e'\iff TS(e)\lt TS(e')$
  • we are assuming an asynchronous system
    • no bound on message delays
    • no bound on relative speed of processes
• Lamport Clock $LC$
  • algorithm
    • initial state … $LC_i\leftarrow 0$
    • for any internal event … $LC_i\leftarrow LC_i+1$
    • on $\mathrm{send}(m)$ … $LC_i\leftarrow LC_i+1$
      • • attach $LC_i$ to $m$, so that $ts(m)=LC_i(\mathrm{send}(m))$
    • when $p_j$ receives $m$
      • $LC_j\leftarrow\max(LC_j,ts(m))+1$
  • what can we say about LC?
    • $e\to e'\implies LC(e)\lt LC(e')$
      • we don't have $\impliedby$
    • $LC_i(e)$ corresponds to the length of the longest chain of events leading to $e$
• vector clocks
  • definition
    • for $i=j:VC(e_i)[j]=$ number of events on $p_i$ up to and including $e_i$
    • for $i\neq j:VC(e_i)[j]=$ number of events on $p_j$ that happened_before $e_i$
  • algorithm
    • if $e_i$ is internal or $\mathrm{send}(m)$
      • $VC(e_i)[i]\leftarrow VC_i[i]+1$
      • $VC(e_i)[j]\leftarrow VC_i[j]$
    • if $e_i$ is $\mathrm{recv}(m)$
      • $VC(e_i)\leftarrow\max(VC_i,ts(m))$
      • $VC(e_i)[i]\leftarrow VC(e_i)[i]+1$