Two General's Problem

想起唸博班時，讀到Nancy Lynch寫的Distributed Algorithms。這本書在還沒談任何分散式演算法之前，就列出了不少的impossibility result。其中最令我吃驚的定理是，若兩個程序純粹以訊息交換(message passing)的方式溝通，那麼在訊息可能遺失的前提下，沒有任何協定可以保證這兩個程序能達成完全一致的共識(consensus)。不能達成共識的原因並非溝通的事情太複雜。例如，可以想像這兩個程序只是很單純地想共同確定某個二元變數A的值是0還是1。

如果兩個程序連單一變數的值都無法達成共識，那麼其他fancy的演算法(leader election, termination detection, gloal snapshot, self-stabilization, ...)都是建立在隨時可能垮掉的基礎上。

在網路的課程中，我們通常稱這個困境為Two General's Problem。根據這個定理，TCP的three-way handshake可能導致client與server兩端對TCP連線是否已經建立起來有不同的看法。例如，three-way handshake的最後一個ack如果沒有被server收到，則client會認為連線已建立，而server會認為未建立。而這個問題理論上是沒有辦法解決的。

理論與現實的差異就在這裡。這個理論上不完美的TCP three-way handshake已經為網際網路貢獻幾十年了，而每年學生都還是要從頭開始認識它的不完美。

萬能資料壓縮演算法

有一個定理說，不存在一個萬能的無損資料壓縮演算法，總是能把任何長度的輸入字串，壓縮到比原來的長度還小。

這個定理的證明也不難。以長度為n的位元串(bit string)為例，總共有2ⁿ個，而長度小於等於n-1的位元串有2^n-1個。資料壓縮演算法可以視作一個將輸入字串對應到輸出字串的函數，而無損壓縮的要求是這個函數必須為一對一(injective)，否則解壓縮會有問題。但是，不存在從n個元素到n-1個函數的一對一函數，所以推論不存在這種演算法。

事實上，如果存在這樣的壓縮演算法，那把它的壓縮結果用同樣演算法再壓縮一次，豈不可以再縮得更小? 重複此動作，資料大小終究會為0。

換句話說，對於任何無損資料壓縮演算法，我們總是可以找到某個輸入字串， 使得壓縮後的結果沒有更好。

我不記得我唸書的時候有沒有學過這個定理，但說真的我們應用時好像不太care(?) zip 程式好像偵測到原始資料的entropy高到一種程度，就直接原文照登不壓縮，加上表頭後最後產生的檔案比原始檔還大。

部落格原作者的講解真不錯。

Line貼圖的左右鏡像建議

在line的對話框中，對方的文字出現在左邊，自己的文字出現在右邊。所以有向對方鞠躬道謝之類的貼圖時，圖中人物是由右邊向左邊彎腰鞠躬的。從傳送者的角度來看，這是很合理的。

不過，貼圖出現在接收者的對話框中時，會變成一個出現在左邊且向左邊鞠躬的圖樣。這樣子變得很奇怪，因為這時候接收者是在右邊啊。如果雙方都傳送類似這樣的貼圖，就會出現兩個彷彿向左膜拜致敬的貼圖。

如果line公司可以提供貼圖創作者一個選項，讓傳送者和接收者看到不一樣的貼圖，就可以免去這樣的尷尬。就我舉的例子，接收者應該要收到傳送圖形的鏡像(但圖形中文字不能鏡像，所以本質上就是另一張雙生貼圖)。

記憶拼圖 (Memento)

如果將一部電影切成約十個片段，從最後一個片段開始往前播放，每一個片段的結尾，會是上一個播放片段的開始，這樣的電影不可謂不創新，但是接受的人多嗎？

廿年前克里斯多福諾蘭執導的電影「記憶拼圖」(Memento)，就是這樣的一部電影。當初在台上映時，怕觀眾看不懂，片商播放的是"改正"成順時序發展的版本。廿年後本片以數位修復版的名義重新在大螢幕上映，改成了原始倒敘的版本。我也進了電影院朝聖。

 

我相信每個看過的人，都會自行在心中還原成原始的時序，好弄懂劇情的來龍去脈，也會嘗試著找出是否有邏輯上不合理的地方。其實劇情也不太複雜，但是如果沒看過廿年前的版本，也事先不知道劇情，要在看完數位修復版後，將劇情依心中"拚好"的原來時序完整地向他人敘述出來，還是有點難度的。

不定冠詞a與an的用法

國中英文就有教過，可數名詞前不定冠詞要用a或an，取決於後面接著的字(word)是否為母音開頭。但很多人誤解這個規則，變成看到以a/e/i/o/u這幾個母音字母開頭的字，就在前頭加an，否則就加a。很多情況下這樣會出錯的。

例如a unique, a unicast, a UDG, a uplink, a upstream這些寫法都是對的，因為字母u在這些字中都不是母音。反而像an LSD (L發/el/為母音開頭)，an SDN (S音標/ɛs/是母音開頭)與 an MTV (M音標/ɛm/是母音開頭)都是對的寫法。但MODEM應該用 a MODEM，因為它的發音是 /ˈmoʊdəm/ 。

比較難判斷的是像L2這種縮寫字。如果將L2唸成L-two，前面就應該加an (L的音標是/el/為母音開頭)。如果將L2唸成原來的layer-two，前面就用a。這就看個人習慣了。

關於地方美食

常常可以在網路或報章雜誌上看到哪兒有特色地方美食，哪兒有開了三四十年的老店。這些報導可以吸引一些喜歡嘗鮮的觀光人潮，不過我還是以一貫的懷疑態度來看待，幾次親身經歷也驗證了我的懷疑並非沒有道理。現在我就來分享我的觀點。

我的第一個看法是，若食材並不特殊，料理方式也沒有太特別，口味受到大眾歡迎的食品，應該會很快流行到其他地方。例如珍珠奶茶、香雞排，並沒有太長的歷史，也非「古早味」或「三十年老店招牌菜」，卻早就遍布全島的大街小巷。世界級的例子有「披薩」、「義大利麵」、「生魚片」、「漢堡」等，這些食品已廣為不同民族所接受。因此如果名店的食材並不特殊，料理方式也沒有太特別，但卻沒有散佈到其他地方，那只能說當地人的口味較特殊，外地人吃不來。

我的第二個看法是，如是當地人「天天光顧」的老店，那價錢一定是便宜的，但基本上只是用來解決三餐的溫飽問題，口味可以接受，或者比較吃不膩而已，距離「美食」還有一段的距離。雖然說吃當地人常光顧的店不較不會被坑，是安全的選擇，但請不要誤導說這是「美食」。另外，如果大老遠到一個地方旅行，吃東西只求不要踩到雷，那麼大可選擇連鎖餐飲店(麥當勞、肯德基)即可。

我的第三個看法比較政治不正確。從前農業社會的人安土重遷，基本上會常去的地方就鄰村甚或縣城而已，無緣踏及遠方的大都市或國外。在所知所聞有限的情況下，認定的美食真的僅限該區域有效力而已。現代人閱歷豐富見聞廣，吃的東西五湖四海，標準也不一樣了。在這樣的前提下，該地的傳統美食也就是當地人才認同，外地客不見得會同意了。

\colon 和 \mid

使用LaTex時，如果要寫出函數的定義域與對應域時，會在函數名稱後面加一個冒號(colon)，像下圖這樣:

我們通常會直接鍵入冒號(":")到文件中。其實較建議的寫法是用\colon。不過當冒號是用於某個數值範圍(range)、當作關係運算子(relation operator)、或者表示比值(ratio)時，應該直接鍵入冒號。

另外一個例子，出現在描述集合成員特性時，會用垂直的bar ("|")來分隔成員與描述。如下圖的例子:

我們通常也會直接鍵入鍵盤中的"|"。其實這裡也應該用\mid取代。使用\colon和\mid與直接鍵入最大的差別是前者會讓符號與前後字元的空間(spacing)調整得比較美觀些。