第25個冬天

時間、時脈與事件排序 分散式系統中時間的重要性-歷史重大事件 2012 年 6 月 30 日至 7 月 1 日（英國時間），全球許多線上服務和系統曾同時崩潰 (crashed simultaneously)，伺服器鎖定並停止回應。航空公司數小時無法處理預訂或登機手續。 時間測量的應用 (Clocks and time in distributed systems) ► Schedulers, timeouts, failure detectors, retry timers ► 效能量測、統計、效能剖析 Performance measurements, statistics, profiling ► Log files & databases: record when an eventoccurred ► Data with time-limited validity (e.g. cache entries) ► 跨多個節點判定事件的先後順序 Determining order of events across several nodes 時脈的區分，兩種時脈： • 實體時脈 (physical clocks)：計算經過的秒數 (count number of seconds elapsed)。 • 邏輯時脈 (logical clocks)：計算事件數，例如發送的訊息數。(count events, e.g. messages sent) 注意：數位電子產品中的時脈（振盪器 (oscillator)） 並不等同於分散式系統中的時脈(時間戳記的來源 (source of timestamps)) 1.石英時脈 (Quartz clocks) ->日常使用時鐘(手機、手錶、掛鐘、數位顯示器內建) 基於石英(二氧化矽)晶體經雷射修剪 (laser-trimmed)，以特定頻率機械共振 (mechanically resonate) 利用壓電效應 (Piezoelectric effect) : 一塊石英若用槌子敲打或稍微彎曲，會發出微小電脈衝。若施加一些電流，也類似讓其被彎曲或敲打般。 振盪器電路 (Oscillator circuit) 在共振頻率 (resonant frequency) 產生訊號，計算循環次數來測量經過時間。 就好比如手錶的心臟會跳...

Logical vs. physical clocks Physical clock: count number of seconds elapsed Logical clock: count number of events occurred , 沒有與Physical time有直接關係 被設計用來捕抓因果關係，常用到的是採用 Lamport clocks 跟Vector clocks 做個課堂筆記紀錄，因為坐在教室後面會照到前面同學後腦杓。歹勢.... 分散式系統中的 Lamport Clock 與 Vector Clock Lamport Clock（Lamport 時鐘） 用途： 用來在分散式系統中決定事件（Event）的先後順序，避免物理時鐘不同步所造成的混亂。 結構與運作： 每個節點都維護一個整數計數器（Lamport Clock）。 當本地有事件發生時，計數器加一。 發送訊息時，附加目前的 Lamport Clock 值。 接收訊息時，將本地計數器設為收到時鐘值與本地時鐘的最大值後再加一。 Vector Clock（向量時鐘） 用途： 用來追蹤每個節點彼此之間的事件先後關係，比 Lamport Clock 更進一步，可以判斷事件是否真正平行（concurrent）。 結構與運作： 每個節點都維護一個長度為 N（節點數）的向量，每個元素分別表示此節點對自己和其他節點事件次數的看法。 本地事件發生時，將自己對應的一格加一。 發送訊息時，附上自己的 Vector Clock（整個向量）。 接收訊息時，將收到的 Vector Clock 與本地 Vector Clock 逐格比較，大者為新值，再把自己格加一。 總結 Lamport clock 只能粗略判斷時間順序（數字比大小），但無法區分平行事件或真實先後。 Vector clock 若 v1 < v2（全小於），就可以明確判定 v1 happens-before v2；若無法比較，就是平行事件。 第10題.一起修課的班代幫忙上台作答-Lamport Clock 給出四個節點 (A、B、C、D) 之間的訊息交換（m1 ~ m9），要求在每個訊息送出或接收事件標記 Lamport 時間戳（timestamp）。 初始值：每個節點的 Lamport Clock 都是 0。 送出訊息：本地 Lamport ...

Chord 演算法 提出單位：麻省理工學院 (MIT)  核心概念：The Chord protocol supports just one operation: given a key, it maps the key onto a node. 採用 雜湊法 (Hashing) 將資料分配到對應的節點 透過這種方式，可以快速定位並搜尋資源所在位置 屬於結構化的P2P查詢 (Structured Peer-to-Peer Lookup) 演算法 用環狀架構 (Ring Topology) 來組織節點 Chord選擇SHA-1作為雜湊函數，SHA-1會產生一個2^160 的空間 每項為一個16位元組(160bit)的大整數。 特色 效能表現：查詢資源時，節點在空間與時間複雜度上皆為 O(log N) 具有完全分散式、負載平衡、可用性及可擴展性好、命名方式靈活等特點。 分散式雜湊表(Distributed Hashing Table, DHT) 拓樸建立方式 每個新加入的節點，會將其 IP 位址 經由 雜湊函數 (Hashing function) 轉換為一個 節點代碼 (Node ID)，這些節點代碼會映射到一個 邏輯代碼環 (Identifier Circle) 上。 透過此環狀結構，節點之間能夠進行高效率的查詢與資源定位。 缺點與面臨的挑戰 當鄰近節點發生變動時，需要進行大量通訊來更新與維護鄰近節點資訊。 在 Grid Computing 環境中，節點變動頻繁，這會造成額外的網路負擔。 Ref: Distributed Hash Tables https://courses.cs.washington.edu/courses/cse550/17au/notes/lect14.pdf https://www.cs.princeton.edu/courses/archive/fall22/cos418/docs/L9-dht-chord.pdf Distributed Hash Tables:An Overview http://www.cs.cmu.edu/~ashu/talks/DHT.pdf Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications https...

https://physics.stackexchange.com/questions/402591/quantum-solution-to-the-two-army-problem 兩軍問題(Two Generals' Problem) https://www.youtube.com/watch?v=IP-rGJKSZ3s 兩支軍隊由不同將軍領導，準備進攻一座堅固的城市。軍隊在城市附近的兩個山谷紮營。由於有另一個山谷將兩山隔開，兩名將軍只能透過派信使穿越山谷通信，但這山谷由城市護衛佔領，有可能俘虜途徑山谷傳遞消息的任何信使。 雖然兩軍已約定同時進攻，但尚未約定進攻時間。要順利攻擊，兩軍必須同時進攻。如果同一時間只有一支軍隊進攻就會戰敗，因此兩名將軍須約定攻擊時間，並確保對手知道自己同意了進攻計畫。 拜占庭將軍問題(The Byzantine generals problem) 由矽谷科學家Robert Shostak於1978年提出的情境難題。 古代某個大城市「拜占庭」正經歷一場戰爭，四位將軍散落在城內各處，必須在短時間內決定進攻還是撤退。條件在於，不論進攻或撤退，都必須四位將軍一致同意，才能保證最後勝利。 四位將軍決定各自寫信予其他三人，告知相關決定。當每位將軍都寄出信息，又同時收到其他三名將軍的來信後，就會知道決定是否一致，到底是進攻還是撤退。 https://www.youtube.com/watch?v=-D8aXZvzzww https://www.youtube.com/watch?v=gJqmOf4mFEU 背後探討的延伸問題 如何防止其中一位將軍叛變？ 又可能其中一位將軍已被暗殺，寄信的其實是間諜？ 此外，寄出信件後也可能被敵方截取並篡改扭曲事實的內容，從而阻止四位將軍達成共識？ 拜占庭容錯 第一種解套方式.Oral Messages 安排一個Leader發送進攻/撤退信號給另外三位將軍 情境1.三位將軍中剛好有一個判將，試圖分別給另外兩位將軍不同錯誤訊息。 然而引入了指揮官，因此將軍A、B各自所收到的進攻比撤退比例均為2:1，兩人皆發起進攻。 進攻就成功。 情境2.引入的指揮官是叛徒，其中一位傳入進攻訊息。 然而三位將軍都相互傳遞沒被竄改過的指令訊息，因此三人收到的撤退比進攻比例都是2:1。 撤退就成功。 第二種解套方式.消息簽名Sign...