[閱讀筆記] Algorithms to Live By - 網路 (Networking)

 網路 (Networking) — 我們如何互通聲息

1. 人類互通訊息的基礎是通訊協定 (protocol)，也就是程序和預期的共通慣例，例如，握手、打招呼和禮儀、禮貌、以及各種社會規範，機器間的聯繫也不例外。從電報到簡訊，通訊科技雖然提供人與人之間溝通的新管道，但人與人之間仍有溝通障礙。Internet 問世後，電腦不僅是溝通管道，也是負責交談的聯絡點，因此它們必須負責解決本身的溝通問題。機器間的這類問題 (以及解決方案)，跟人與人之間的問題相仿，很快變成我們借鏡的對象。

2. 拜占庭將軍 (Byzantine Generals Problem) 問題

問題描述

一組拜占庭將軍分別各率領一支軍隊共同圍困一座城市。為了簡化問題，將各支軍隊的行動策略限定為進攻或撤離兩種。因為部分軍隊進攻部分軍隊撤離可能會造成災難性後果，因此各位將軍必須通過投票來達成一致策略，即所有軍隊一起進攻或所有軍隊一起撤離。因為各位將軍分處城市不同方向，他們只能通過信使互相聯絡。在投票過程中每位將軍都將自己投票給進攻還是撤退的資訊通過信使分別通知其他所有將軍，這樣一來每位將軍根據自己的投票和其他所有將軍送來的資訊就可以知道共同的投票結果而決定行動策略。

解決方案

Lamport 用數學證明，叛徒數必須少於總數的1/3，才能達成共識。 各節點（將軍）送訊給所有節點（將軍），各節點（將軍）根據收到的所有消息決策，如何避免惡意節點（叛徒）影響共識的達成？在過程中，若節點故意拒絕合作（惡意節點）或根本沒有說任何事情（錯誤節點），就是叛徒。在比特幣的區塊鏈網路設計中 ， 中本聰藉由密碼學與工作量證明機制 （Proof of Work，PoW）等方法來制約這些叛徒。透過 PoW，節點必須付出大量的工作量（算力）去證明自己的忠誠，之後才能打包交易，送訊給其他節點。最長鏈機制則是各節點都沿著已知的最長鏈進行。所以即使惡意節點試圖破壞，也會付出很大的代價（付出超過整體系統一半的算力）， 只要每個節點都足夠理性、想讓自己利益最大化的情況下 ，工作量證明機制 PoW 的確有效抑制了叛徒作惡的動機，進而解決了拜占庭問題。。(Ref: https://reurl.cc/0Dd5Vx, https://reurl.cc/OXrl2D )

3. 工作量證明 PoW (Proof of Work)：(Ref: https://reurl.cc/e9yqoW, https://reurl.cc/nnvkMd )

PoW (Proof of Work, 工作量證明) 說明

網路上的節點可以簡單地透過工作量證明，快速驗證彼此是否擁有記帳權。就像是我們求學時期，大學四年熬夜苦讀就是為了獲得那張畢業證書，求職時，面試官透過那張畢業證書，快速驗證你大學的成果。畢業證書就是你的 PoW。

以比特幣為例介紹 PoW

每 10~15 分鐘比特幣網路上全體礦工會互相競爭，運用大量的運算能力去解一道複雜的數學題的答案，這個答案是一個隨機數，可以想像題目大概長這樣：Hash｛（前一個區塊的 Hash 值）,（當前區塊的交易資訊）,（隨機數）｝＝當前區塊的 Hash 值。 礦工必須找出一串數字，代入上述公式，讓當前區塊的 Hash 值開頭為 18 個 0 ，例如：0000000000000000001583447dd74c13c09280a9218827244089adadaba8c8c9 解答的過程沒有軌跡可循，礦工只能不斷代入隨機數，透過暴力法找出答案。

挖礦難度

最先解開的人就能獲得下一個區塊的記帳權並獲得比特幣作為獎勵。比特幣固定 10~15 分鐘出塊一次，但是如果節點越來越多、全網算力增加，會縮短算出答案的時間。因此，比特幣協議每 2016 個區塊會調整一次挖礦難度，大約兩個禮拜調整一次。挖礦難度提高時，就必須找出有更多個 0 的當前區塊 Hash 值，例如從原先的 18 個 0 增加到 19 個 0，難度降低時則相反。 挖礦的過程其實像是擲一顆 20 面的骰子，誰先骰到 < 2 的數字誰就能獲得計帳權，換句話說，礦機的硬體運算能力再強大，也只能提高獲得計帳權的機率（骰骰子手速比較快），算力差的礦工不代表沒有機會。

比特幣經濟與獎勵

中本聰所開發的比特幣為了避免貨幣發行太多或太快，有設計出一套抑制通貨膨脹的機制並最終只會發行 2,100 萬個比特幣。為鼓勵節點幫忙驗證營運，設計了挖掘新區塊的獎勵，區塊獎勵從 2009 年開始每個區塊可獲得 50 個比特幣的獎勵，但此一獎勵區塊回報每產出 21 萬個區塊減半一次，即每 4 年減半，2013 年到 2016 年 6 月則是 25 個比特幣，2016 年 7 月 9 日區塊獎勵再度折半到 12.5 個比特幣，估計到 2021 年時會再度折半到 6.25 個，在 2022 年中就會挖出超過 90％，因為比特幣最小單位是 0.00000001，所以 2140 年之後區塊獎勵就會小於最小單位，即不會再生成比特幣產生。

優缺點

優點 容易實現，節點可自由進入，去中心化程度高。 破壞系統需要投入極大的成本，安全性極高。 缺點 為了保證去中心化程度，區塊的確認時間難以縮短。 透過礦工的計算能力以及硬體成本確保礦工立意良善，挖礦過程中過多的能源消耗，使得此機制非常不環保。

4. TCP 三向交握 (Three-way Handshake) (Ref: https://reurl.cc/WENprD )

Three-way Handshake 說明

傳輸控制協定 (Transmission Control Protocol, TCP) 不像 UDP， TCP 是一種 連接導向 (connection-oriented) 的通訊協定，三向交握 (Three-way Handshake)， 是其建立虛擬連線 (virtual connection) 的方式。  又稱為 三向式握手、三路交握 …，其實就是 三次訊息的交換。

Three-way Handshake 圖示

5. 網路傳輸並不保證送達，面對不可靠的人或電腦，我們所面臨的問題

不可靠傳輸的問題	說明
中斷多久被視為真的中斷	📞若是電話，中斷幾秒鐘，我們就會擔心是不是斷話了； 📧 若是 e-mail，過了好幾天收件者沒回信，就會擔心對方是否沒收到。 訊息在發送者與收件者間往返時間越長，沒消沒息的時間也要越長才會引人注意。
中斷後如何因應 (間隔多久做 retry)	指數退讓法 (Exponential backoff) 是處理各種網路失敗或不可靠性的預設方法。 Using exponential backoff - Geocasts 當我們的電腦試圖連線一台顯然已停機的網站，就會使用指數退讓法 (Exponential backoff)，起先是一秒鐘後 retry，接著是幾秒鐘後 retry，如此不斷拉長，對 client 或 server 端都有好處，不僅可防止停機的伺服器重新上線時因 HTTP Requests 太多而停擺，也可防止 client 端浪費太多時間白做工，而且此法也不會迫使我們的電腦完全放棄。

6. 指數退讓法 (Exponential backoff) 在網路安全也扮演要角，有人藉著連續輸入密碼試圖 login 失敗時，它會以指數方式延長鎖定時間，防止 hacker 利用「字典式攻擊」入侵帳號，不斷輸入可能的密碼，直到成功為止。

7. TCP 壅塞控制 (congestion control) 的核心，稱為加法遞增乘法遞減演算法 (AIMD, additive-increase/multiplicative-decrease)。在 AIMD 中，一批封包完整接收後，不會讓傳送封包數加倍，而只會 +1，而發生封包遺失時，則會使傳輸率降一半。實質上， AIMD 的策略就是：「多一點、多一點、多一點、阿太多趕快減少、多一點、多一點 …。」它產生的頻寬變化圖形稱為 TCP 鋸齒圖 (TCP sawtooth)，先逐步緩升，穿插幾次陡然下降。保守主義在此非常重要，所有使用者的速度都不能超過網路過載的速度，如此才能維持網路穩定。同樣地，加法遞增有助於穩定整體狀況，防止出現劇烈過載和復原循環。

(Ref: https://reurl.cc/qmnDxR )

8. 許多動物的覓食行為類似 TCP 流量控制與特殊的鋸齒曲線。追逐人類食物碎屑的松鼠與鴿子，每次都會往前走一步，偶爾退後好幾步，然後再往前走一步。

9. TCP 鋸齒圖 (TCP sawtooth) 告訴我們，在無法預料與不斷變化的環境中，要充分運用全部資源，最好與唯一的方法，就是把狀況推出到出現錯誤。最重要是確定錯誤、反應迅速，而且很快就能恢復。在 AIMD 演算法中，沒有中斷的連線會加速到中斷為止，接著減速一半，又立刻加速。在 TCP 中，沒有單向傳輸，一旦沒有持續的回饋，發送者會立刻減緩發送速度。

10. 彼得理論 (Peter Principal) 提到「所有員工通常都會升到無法勝任的職」，套用 AIMD 演算法，假設有間公司的員工不是每年晉升一級，就是降階若干級，如此就不會有人抱怨一直沒獲得升遷，也不會有人憂心長期負擔過重。

11. buffer / queue 的概念：當你與另一位客戶幾乎同時走進一間甜甜圈店，收銀員由於一時忙不過來，於是請你們其中一個人排隊稍後。如此一來，可以確保收銀員不會過勞，請客戶排隊可確保店裡的平均處理量可達最大處理量，這是好事。但這種優秀的資源運用方式，必須付出「延遲代價」。當排隊人數越多，隊伍越長，等待時間就越久；若店家在目前隊伍末端，立個標示牌表示本日 sold out，這對顧客與店家可謂皆大歡喜，店家表示已達本日最大產量，顧客也不用浪費時間排隊，可以去買其他東西。出於策略刻意讓球落地，是在負擔過大時完成工作的重要方法。

12. 當緩衝區已滿，通常會出現 tail drop 現象，代表在此之後到達的封包都會直接拒絕並刪除。隨著科技進步，記憶體價格下跌，處處充滿了大型緩衝區的網路設備，這對基於遺失  (lost-based) 的壅塞控制演算法造成巨大的問題。大型的緩衝區，使封包不易被丟棄，而是在佇列中緩慢地等待，TCP 傳送端 並不知道 壅塞的發生，仍持續成長傳輸速率，使網路產生高延遲、吞吐量下降的惡性循環，這就是惡名昭彰的 — 緩衝區膨脹 (bufferbloat)。(Ref: https://reurl.cc/v5paRL, https://reurl.cc/xgpa7V )

13. 運用「Tail drop 概念」於 e-mail 自動回覆功能

14. 許多公司強調的「高速網際網路」，指的是高頻寬，而非低延遲；網路工程師早該將「低延遲」視為最優先的問題。我們需要更多協和式客機 (Concorde)，而非更大台的波音。例如，對線上遊戲玩家而言，即使 50ms 的延遲，都可能影響到他幹掉別人，還是別人幹掉他。

[閱讀筆記] Algorithms to Live By - 隨機性 (Randomness)

 隨機性 (Randomness) — 什麼時候該讓機率決定

1. 乍看之下，隨機性似乎與理性背道而馳，代表我們放棄此問題，被迫採取的手段。其實不是這樣，隨機性在電腦科學中扮演令人驚訝的角色，且越來越重要，且證明在面對極為困難的問題時，運用機率可能是謹慎又有效的解決方法。事實上，有時我們別無選擇。

2. 隨機性演算法未必能提出最佳解，但它不用像確定性演算法那麼辛苦，只要有計畫地丟幾個硬幣，就能在短短時間內提出相當接近最佳解的答案。隨機性演算法用於特定問題的效果，甚至超越最好的確定性演算法。問題的最佳解決方法有時候是交給機率決定，而不是自己試圖推出答案。這章將要告訴你依靠機率的時機、方式，以及仰賴的程度。

3. Estimate Pi by Chance (以機率估算圓周率)：統計學家很喜歡認為任何重要的事都可透過統計學來發現。實際上可能是真的，因為我們發現，你甚至可以使用統計學來估計科學中最重要的基本數值，也就是 pi (圓周率)。Buffon’s Needle Problem 發現，針與線相交的機率是 2。

Buffon’s Needle Problem (布豐的掉針問題)

想像有一根針，隨機落在畫有兩條平行水平線上的圖。這兩條線之間的距離比針的長度還要長。這根針落在其中，並觸碰到其中一條線的機率為何？

計算機率考量的因素

任何給定的隨機掉落位置有以下關鍵因素 針的中心位於何處； 針與最接近的直線之垂直線所組成的角度。 透過上述兩個關鍵因素，簡化問題為 若針的中心點剛好落在其中一條線上，無論角度為何，一定有碰到那條線； 若針的中心點足夠接近一條線，在針的長度一半內，有可能會碰到一條線，一切要看其落下角度 若針的中心點與一條線的距離 > 針的長度的一半，不管角度為何，永遠不會碰到線； 落下的位置越接近線，針碰觸到線的機率就越大。

計算針落到直線的機率

針落下的所有可能位置可被繪製成一條曲線，代表著與一條直線的所有可能距離，以及針與垂直線的所有可能角度。這需要用到三角學 (Trigonometry)，而數學家使用方程式來定義這條曲線 （假設針的長度是 3 英吋、兩條直線間的距離為 4 英吋）：機率=(2)(針的長度)()(直線間的距離)=(2)(3)(3.1459)(4)=.477，代表有 48% 的機率會碰到一條線。 機率和 𝛑：=(2)(針的長度)(機率)(直線間的距離)=(2)(3)(.477)(4)=3.1447

用機率估計 pi

假設你被困在荒島上，不知道 pi value為何。你可以設置兩條水平線的區域，丟下針，然後記錄結果。測量你的水平線的距離以及針的長度，從多次落下的針，收集大量樣本。假設針有 7 英吋，兩條線間的距離是 8 英吋，經過實驗 1000 次，針碰到線的機率是 55%： ＝(2)(針的長度)(機率)(直線間的距離))=(2)(7)(.55)(8)=3.18

4. 抽樣過程一定會有誤差，但我們可透過確保樣本為隨機，以及取得更多樣本，以減少誤差。在沒有其他方法能得出答案時，抽樣至少可以提供答案，就這點而言，抽樣優於執行分析。隨機性最令人驚奇的能力，是它可用在機率似乎無用武之地的地方，即使我們想知道的答案只有是否或真假，沒有模糊空間，擲幾次骰子似乎也能提供部分解答。

5. 蒙地卡羅模擬法 (Monte Carlo Simulation) 是一種數值方法，利用亂數取樣 (Random Sampling) 模擬來解決數學問題。在數學上，所謂產生亂數，就是從一開始給定的數集合中選出的數，若從集合中不按順序隨機選取其中數，稱為亂數，若是被選到的機率相同時，稱為均勻亂數。例如擲骰子， 1 點至 6 點骰子出現機率均等。 舉凡在所有目前具有隨機效應的過程，均可能以蒙地卡羅方法大量模擬單一事件，藉統計上平均值獲得某設定條件下實際最可能測量值。 蒙地卡羅模擬法，是基於大數法則的實證方法，當實驗的次數越多，其平均值也就會越趨近於理論值。

Step 1. 取得 0050 近 10 年歷史績效

Step 2. 根據歷史資料，用亂數跑 1000 次可能的報酬結果

礙於版面，僅擷取前 20 筆模擬資料 NORMINV 傳回指定值、平均值和標準差的反常態分佈函式值。 【語法】NORMINV(x, mean, standard_deviation) x 常態分佈函式的輸入內容，此處帶入亂數 rand()。 平均值 常態分佈函式的平均值 (mu)。 標準差 - The standard deviation (sigma) of the normal distribution function.

Step 3. 計算常態分配函數與報酬發生次數

NORMDIST 傳回指定值、平均值和標準差的常態分佈函式值 (或常態累積分佈函式值)。 【語法】NORMDIST(x, mean, standard_deviation, cumulative) x 常態分佈函式的輸入內容。 平均值 常態分佈函式的平均值 (mu)。 標準差 - The standard deviation (sigma) of the normal distribution function. 累積 - Whether to use the normal cumulative distribution function rather than the distribution function.

Step 4. 繪製常態分配圖

https://reurl.cc/bzV376

6. 我們已習慣數學是個說一是一的領域，說某個數字「可能是質數」或「幾乎可能是質數」，會讓人感到奇怪。實際上，在網際網路連線和數位交易用來加密的現代密碼系統中，偽陽性 (false positive) 比例不到 1024 分之一，這個數字是小數點後有 24 個 0，也就是數目等於地球上所有砂粒的質數中，只有不到一個假質數。透過 Miller-Rabin 質數測試，確實不能 100% 確定，但能夠很快地確定一個數字很可能是質數。

7. 要理解一個過於複雜、無法理解的事物，仔細研究隨機樣本可能是最有效的方法。碰到接龍遊戲、核分裂、質數性測試或公共政策等，這類數字龐大到無法掌握、複雜棘手到無法直接處理的事物，蒙地卡羅法的電腦科學家提出的「抽樣方法」，可以說是最簡單且最好的解決方案。

8. John Stuart Mill (英國哲學家與經濟學家)：沒有事情是絕對確定的，但事情的確定程度已經足夠人活下去了。

9. 布隆過濾器 (Bloom filter) 是1970年由 Bloom 提出的。它實際上是一個很長的二進位向量和一系列隨機對映函式。布隆過濾器可以用於檢索一個元素是否在一個集合中。Bloom filter 的優點是空間效率和查詢時間都遠遠超過一般的演算法，缺點是有一定的誤辨識率和刪除困難。Bloom filter 是一個 data structure 用來提升速度及記憶體使用的效率。這個 data structure 是 probabilistic data structure，它可以判斷某個元素 (element) 是否在某個 set 內。此方法雖然存在誤差率，有可能把不屬於這個 set 的元素誤認為屬於這個 set (False Positive)，但不會把屬於這個 set 的元素誤認為不屬於這個 set (False Negative)。【應用1】 Tinder 會根據你身處的地方及個人要求作出配對，為了避免重複出現同一選擇 (已和你配對或已被你拒絕的對象)，系統會將已經出現的選擇加入 Bloom filter。這樣用戶就不用又再次見到相同的對象；【應用 2】任何一個 Unique ID 系統都會為新的註冊用戶產生獨一無二的號碼。假如在短時間有大量用家來註冊成為用戶，就會為數據庫帶來負擔。為了減輕數據庫負擔，可以利用 Bloom filter 來檢查某個註冊號碼是否已經存在。(Ref: https://reurl.cc/e9zKnQ)

10. 運用隨機法，想辦法從局部最大值，變成整體最大值

11. 無論是抖動、隨機重新開始、或是接受解決方案偶而變糟，隨機性用於避免局部最大值的效果都很好。機率不只是處理困難最佳化問題的可行方法，在許多狀況下還是必要方法。從模擬退火法可以得知，你應盡早使用隨機性，並快速離開隨機的狀態，隨時間而降低隨機性，停留在接近結冰的時間最久。壓住火氣，不要急躁。

12. 1971年出版的小說《骰子人》（Dice Man）講述了一位精神科醫生根據擲骰子做​​出日常決策的故事。小說中的敘事者因總是擲骰子做決定，最後很快陷入絕境。作者 George Cockcroft 的人生有段時間也處於「擲骰子」狀態，跟家人一起開著帆船，在地中海漫無目的旅行，然而到某一天，他的退火程序結束，停留在某個局部最大值，在某個湖過著愜意的日子，現在以 80 多歲，依然知足地住在那裏。他向《衛報》表示：「你一旦到了讓你感到快樂的地方，再大幅改變就太傻了 (stupid to shake it up and further)。」

[閱讀筆記] Algorithms to Live By - 鬆弛 (Relaxation)

 鬆弛 (Relaxation) — 放鬆點，不求完美才有解

1. 柯布漢-艾德蒙斯假說 (Cobham–Edmonds thesis)：如果一個演算法花費的時間是多項次時間 (polynomial time)，也就是 O(n2)、O(n3) 或 n 的任何次方，則這個演算法應被視為「有效率」。因此，如果我們知道如何以有效率的演算法在多項次時間內解決問題，此問題是「可解問題」；若無法在多項次時間內解決問題，此問題是「難解問題」。除了是規模極小的難解問題，不管是運算能力多大的電腦，都無法解決難解問題。

2. 要解決「難解問題」，就必須先「放鬆問題的限制」。電腦科學中相當簡單的放鬆方式，是限制鬆弛法 (Constraint Relaxation)。研究人員運用此技巧時，會先移除問題的某些限制，再著手解決問題，有了一定進展之後，再慢慢加回限制。也就是說，數學家先簡化問題，讓問題容易處理後，再把它改回實際狀況。限制鬆弛法是先讓難解的問題變成可解，取得理想化版本的進展後，再思考現實世界的版本。此法不保證可找到最佳解答，但可以幫助在時間限制與決策品質間做出取捨，只要願意接受近似次佳解，再棘手的問題都有適當技巧可以求解。

3. 遇到難解問題，即使擁有超級電腦也無用武之地。我們要學會放鬆 (Relaxation)，電腦才派得上用場。

放鬆方法	說明
① 限制鬆弛法 (Constraint Relaxation)	直接去除某些限制，求出比較鬆弛問題的解，再把結果套用到真實狀況。
② 連續鬆弛法	把離散或二元選擇轉化成連續體，例如決定點冰紅茶或檸檬水時，先想像混合兩種飲料的冰檸檬紅茶，再決定要進位或捨去；又如飲料從加糖與不加糖，變成一到十分糖。
③ 拉式鬆弛法 (Lagrangian Relaxation)	把不可能變成高昂代價，教我們改變規則 (或是先違反規則、再接受後果)，例如，演唱會稍微超過限制時間並支付罰款，會比嚴格限制表演時間來得好，以換取歌迷滿意度。

4. 鬆弛法的優點與必要性

優點與必要性	說明
① 為真實解答設下品質界線	透過放鬆限制條件的 trade-off 有助於讓人看見問題的全貌與合理設定自己的期待。
② 能與現實互相調和	提出一個與現實調和的參考解，讓人知道最佳解存在的範疇，在那個範疇附近都算OK。
③ 追求完美是一種浪費資源與生命的行為	先假設比較容易的問題，並加以解決，才是取得進展的最佳策略。