Review

OSI Model

Layers:

Time

Cristian's Time Sync: The accuracy is \pm (RTT/2-\min)

  1. client request time from server at time T_0
  2. server received request, it reply back with time t
  3. client receive result from server at time T_1
  4. client set its clock to t + \frac{T_1 - T_0}{2} where the round trip time is RRT = T_1 - T_0

Berkeley Algorithm:

Network Time Protocol (NTP): hierarchy of server using Cristian's

Mutual Exclusion

Decentralized Mutual Exclusion: ask for majority

Bully Leader Election: Nobody want to be the leader, but everybody can appoint a leader. Everybody must accept appointment unless you can hand the task of the leader to other people.

  1. Assume servers are enumerated from S_0, S_1, ..., S_n
  2. Everything is fine until one server S_i notice a leader does not respond
  3. The server S_i appoint new leader \{S_j | j > i\}
  4. Whoever received the appointment try to hand the task to other. Say S_j \in \{S_j | j > i\} received the appointment, it need to appoint new leader \{S_k | k > j\}.
  5. Repeat the process until one cannot appoint his own leader task to someone else.

Ring Algorithm Election: passing paper around, write names on it, select at the end.

Total Ordered Multicast using Total Order Lamport (TO-Lamport) Clock: mark command with lamport clock, keep a queue to process in order by broadcast send and ack to all server.

Lamport Mutual Exclusion: Total Ordered Multicast with slight change, assuming no replicate data among servers

Ricart & Agrawala Mutual Exclusion: assume no message lost, mul

  1. When a server want to access critical region, it broadcast REQUEST to all servers
  2. The server is automatically granted permission when all server respond YES
  3. Receiver, upon receive RESUEST:
    1. Reply YES if it is not interested in data.
    2. Does not reply if it is currently accessing data.
    3. Reply YES if it is interested in data, but has not gotten permission, and the lamport clock is the current REQUEST is lower than itself's REQUEST.
    4. Does not reply if it is interested in data, but has not gotten permission, and the lamport clock is the current REQUEST is greater than itself's REQUEST.

Token Ring Algorithm: critical section by passing key

Concurrency

ACID Properties:

2-phase Locking (2PL): growing, shrinking

Strong Strict 2-phase Locking (SS2PL): we only release all locks at once after all operations finished (still need acquire in order)

One-phase Commit: coordinator force everybody to commit

2-phase Commit: request, vote, broadcast. (blocking when fail after vote "yes")

Database

Log contains:

Name Where Definition
flushedLSN Memory Last LSN in log on disk (change every flush)
pageLSN page lastest LSN to page (change every record)
recLSN page first LSN that is dirty (change every flush)
lastLSN Transaction lastest LSN to txn (every txn's record)
MasterRecord Disk latest checkpoint (change every checkpoint)
prevLSN Transaction LSN pointer during reverse, per transaction
undoNext Transaction what to undo next during recovery (prevLSN)

Transaction Table (TT): in memory, store

Dirty Page Table (DPT): in memory store

Recovery Phrases:

  1. Analysis: scan through database to build TT and DPT
    1. TNX-END: remove txn from ATT
    2. UPDATE, UNDO: add txn to ATT (if not already in, set recLSN = LSN)
    3. COMMIT: change status to COMMIT
    4. CHECKPOINT_END: add ATT/DPT infomation of checkpoint to current ATT/DPT
    5. ATT: all transaction that is active during crash
    6. DPT: dirty pages that might not have made it to disk
  2. Redo: redo everything (even for aborted transaction), restore to exact state when log saved before crash
    1. Redo unless: affected page is not in DPT, or
    2. affected page is in DPT, but LSN less than recLSN (already made into disk)
  3. Undo: undo for transactions (only a portion of all transaction) that has net yet committed
    1. When a transaction completely UNDO: sync to disk and don't need to UNDO again for next crash 1. write log to disk 2. write page to disk 3. append CLR: <TXN-END> to disk
    2. If you have a CLR in log (that is not already <TNX-END>) during UNDO, don't UNDO it. Because you already REDO it in redo phrase. Instead, go to undoNext field in the record and start UNDO from there.

Paxos

Phrases:

// TODO: review practice exam, do cheatsheet, review homework

Table of Content