Paxos issues Also apply to Chubby ZooKeeper All requests go to master Bad scalability High latency when geo-replicate (remote master) Sensitive to load spikes & network delay Master down -> system down (for a while) EPaxos Goal Optimal commit latency in the wide area Optimal load balancing across all replicas Graceful performance degradation So… Every replica need to act as proposers or else the latency will be high imply no leader Minimize proposer’s communication with remote Quorum composition must be flexible to avoid slow nodes Key Ordering Old: Leader choose order or choose pre ordered command slot EPaxos: dynamic & decentralized Not necessary to enforce a consistent ordering for non-interfering commands Non-interfering 1 RTT Need fast-past quorum of node $F + \lfloor\frac{F+1}{2}\rfloor$ $F$ = min# tolerable node failure R1: PreAccept C1 R5: PreAccept C2 R2, 3, 4: OK => Commit Interfering 2 RTT quorum size $F+1$ R5: PreAccept C4 R3: OK C4 R1: PreAccept C3 R3: OK C3 should go after C4 R1: Receive inconsistent response, second phase R1: Accept C3 -> C4 R 2 3: OK, Commit Protocol Commit Protocol (Unoptimized version, fast-path quorum = $2F$) Replica $L$ receive a request Replica choose the next available instance Attach attrs deps: list of all instances that interfere seq: number for breaking dependency cycles, larger than max(seq deps) Replica forwards command and attr to at least fast-path quorum of nodes (PreAccept) If quorum responds and attr same => commit else update attr (union deps, set max seq) => tell simple majority to accept => commit Execution Algorithm find strongly connected components topo sort bla bla bla Paper 4....

最近在學寫程式 剛好遇到費氏數列的問題 覺得很有趣 就記錄下來 費氏數列的定義應該不用多說 $$F_0 = 0, F_1 = 1$$ $$ F_n = F_{n-1} + F_{n-2} $$ 那扣要怎麼寫呢 最直觀當然就是照著定義寫遞迴了 def fib(n): if n == 0: return 0 if n == 1: return 1 return fib(n-1) + fib(n-2) 但是這樣數字一大就會很慢 為什麼呢？ 因為很多數字都重複算了 例如算 fib(6) 的時候 由下圖可以看到 f(4) 被算了兩次 f(3) 被算了三次 解決辦法就是把算的結果記起來 就不用再算一次了 可以這樣寫 from functools import cache @cache def fib(n): if n == 0: return 0 if n == 1: return 1 return fib(n-1) + fib(n-2) 不過這樣浪費記憶體空間...

寫了 UWMadison 修課心得 - CS642 突然想到的 故事發生在我去拿 Midterm 1 的考卷的時候 我用原子筆寫 用立可帶塗 一個台灣人覺得再正常不過的事 但 Professor 看到居然說：「挖 你怎麼這麼用心 還拿這種東西塗掉」 （具體講什麼我忘了 反正他很驚訝就對了） 我：「？？？！？」 不過我好像真的沒看過外國人拿野生的立可帶 附上用了五年的立可帶圖結束這個很爛的故事 他後面還有擦布 好方便捏

基本資料 Name: Introduction to Information Security Professor: Rahul Chatterjee 印度人 Credit: 3 Score distribution: Introduction to Information Security - Madgrades 內容 密碼學 Hash, SHA, RSA, Diffie-Hellman Web Security XSS, SQLi, CSRF Network Security TLS, Tor Operating system security Unix Permission Low-Level security x86, Buffer overflow Protection: Stack canary, ASLR Hardware security Intel SGX, Bitlocker, TPM Virtual Machine 計分方式 Homework 50% Midterm-1 20% Midterm-2 20% Class participation 10% - 只要在論壇(piazza)有說說話就有分了 好像沒有調分 上課方式 前半學期實體 後半學期Zoom...

Introduction No blocking primitives (e.g. locks) FIFO Client ordering of all operations linearizable writes leader-based atomic broadcast - Zab ZooKeeper Service Hierarchy Regular/Ephemeral node Watch trigger if data changed Data model Simplify Full read/write filesystem API Offer async and sync access via full path setData delete contain a version para ignore if not match Example Leader configuration change New leader delete ready node New leader async update configuration nodes Leader create ready node Clients check if ready exist Configuration Management Processes share same configuration node Rendezvous Master want to share info with worker but master does not know info until started Master pass node path to worker and write to the node Group Membership Create parent node Children in node = member Simple Lock Clients create Ephemeral lock fail Only one will succeed Others watch Implementation idempotent transaction Read - Any servers weak consistency use sync if needed Write - forward to a single server leader calculate state Client server exchange zxid (last transaction id) Client connect only to servers with same or greater zxid VS Chubby No lock No blocking primitives Chubby blocks update while invalidating others’ cache Access via full path (vs fh) Chubby redirect all operations to master Chubby stricter consistency Chubby slower