Review 001

OSI Model

Layers:

• physical: bit synchronization, bit rate control, bus, simplex/half-duplex/full-duplex (implemented by physical wires)

• data-link: Logical Link Control (LLC), Media Access Control (MAC) (implemented by switch)

• network (IP): routing, logical IP address (implemented by router)

• transport: port number, break message into segments and reassemble, TCP, UDP (implemented by operating system)

• session: maintaining sessions, authentications, security, HTTP, RPC (application-implemented)

• presentation: Translation layer, encryption/decryption, compression (application-implemented)

• application: your code (application-implemented)

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:

• master can sync with UTC server (assume no RTT), not necessary

• a group of servers are elected into 1 master and other slave servers.

• master send its current time master to all slaves.

• slaves respond with time differences dxs.

• master receive 2 things: time difference, and calculated roundtrip time RTT.

• master average (median) the time difference and add RTT/2, then broadcast the adjusted time to slaves.

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

• instead of sending command, we send p_i want to access critical region

• when processing command, we allow p_i to access critical region

• only ACK to one server (sender) instead of broadcasting ACK (only the requester need to know when it can access critical region, assuming no malicious server)

  • All server will have the same order of p_i want to access critical region, but might not have consistent ACKED status on every p_i want to access critical region.
  • The sender server will eventually get a ACK and have its p_i want to access critical region being the oldest in the queue

• broadcast RELEASE lock to all servers once sender has done with critical region

• upon receive RELEASE, remove element in the queue no matter whether p_i want to access critical region is ACKED

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:

• Atomicity: transaction either complete or abort. It should abort with no side-effect

• Consistency: Each transaction preserves a set of invariants about global

• Isolation: each transection executes as if it were the only one with the ability to read/write shared global state

• Durability: committed transaction's effect will persist

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:

• a <BEGIN> is written before every transaction start

• a <COMMIT> is written before every transaction commit

• a <DATA> is written for every change to a single object containing

  • Transaction ID
  • Object ID
  • Before Value (for UNDO)
  • After Value (for REDO)

• a <CHECKPOINT> is written once a while, stopping all transaction, to keep log short. (You still need to check for un-committed change before <CHECKPOINT> line)

• during recovery (REDO or UNDO), we also write to log so that we can handle failure during recovery too

• a <TXN-END> is written after <COMMIT> is successfully written to disk (so in recovery, if we see this tag, we can safely ignore this transaction), we don't need to flush this before <COMMIT>.

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

• transactionID that is active (not committed)

• lastLSN of transactionID

Dirty Page Table (DPT): in memory store

• pageID: ID of a dirty page

• recLSN: first LSN that made page dirty

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:

• Prepre Phrase

  • Proposer: choose a proposal number n and a value v
  • Proposer: broadcast PREPARE(n) to all acceptors
  • Acceptors: record n if greater then record it, since it only want to accept latest proposal. response with accepted proposal with value (n_acc, v_acc)
  • Proposer: Wait until majority responded. Replace v = max_{n_acc}(v_acc) if exist. (since v_acc is possibly be chosen already)

• Accept Phrase

  • Proposer: propose (n, v) to all acceptors
  • Acceptors: accept if n > n', reject and return current maximum proposal id n_acc.
  • Proposer: if rejected, try again with greater number

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