上个学期的 CS5223 Distributed Systems ，Prof. Li 讲的蛮好，尽管实现了 Basic Paxos 和 Multi Paxos（多亏了 Junhui 的 cheatsheet¹），但是耐不住时间的拷打，写的 Paxos 都快忘光了…

所以，赶紧开一篇博客把想法都记录下来，以便之后的复习。

首先简单过一下这些基础概念

# Happens-before relationship

• Within a process, A comes before B then A→B, it also means

  B could have been influenced by A

• If a → b, then b !→ a

  What about a!→b, does that mean b→a? NO

• If a → b, and b → c, then a → c (transitivity)

• a !→ b and b !→ a, means a and b are concurrent

  no one can tell whether a or b happened first!

# Lamport clock

We can use clocks to implement a lock.

Our goals are:

1. Only one process can hold the lock at a time.
2. Grant the lock in request order.
3. Requesting processes eventually get the lock.

Our assumptions are:

1. In order point-to-point message delivery.
2. No failures.

Implementation:

1. Each message carries a timestamp $T_m$
2. Three message types:
   • request
   • release
   • acknowledge
3. Each node’s state:
   • A queue of requested messaged, ordered by $T_m$.
   • The latest timestamp it received from each node.

On receiving

1. receiving a request
   • record the timestamp
   • add the request to the queue
   • send an acknowledge
2. receiving a release
   • record the timestamp
   • remove the request from the queue
3. receiving an acknowledge
   • record the timestamp

To perform

1. To acquire a lock
   • send request to every node, including itself
2. To release a lock
   • send release to every node, including itself

The lock is acquired when

1. My request is at the head of the queue.
2. I’ve received higher timestamp from every node.
3. So my request must be the earliest.

# Vector clock

Clock is a vector C, length = # of nodes.

(0, 0, 0) for a 3-node system

On node i, increment C[i] on each event.

node 0 (3,5,2), after event: (4,5,2)

On node i, received a message, increment C[i], and take the max of each element.

node 0 (4,5,2), received message (2,7,0): (4,7,2)

If Cx[i] < Cy[i] and Cx[j] > Cy[j] for some i, j

• Cx and Cy are concurrent

if Cx[i] <= Cy[i] for all i, and there exist j such that Cx[j] < Cy[j]

• Cx happens before Cy

# Lab 1

实现一个 at-most-once 的 KV Store

• RPC 要么最多执行一次，要么不执行

# Reference