[網摘] High Scalable Architecture

底下只是一些資料收集，都是關於"High Scalable Architecture"的一些研究和實作。

• Jeffery Dean: MapReduce論文的作者, Protocol Buffer的創始人。
  http://research.google.com/people/jeff/
• Dan Kegel: 經典"The C10K problem"的作者。
  http://www.kegel.com/c10k.html
• Felix von Leitner: 在2003年以一篇"Scalable Network Programming"對於Web Server做深入分析。
  http://www.fefe.de/
  http://bulk.fefe.de/scalable-networking.pdf
• Node.js: 以V8 JavaScript engine為基礎的JavaScript Runtime，並且以"High Scalable"為最主要的Design Goal。
  http://nodejs.org
• Gustavo Duarte: 在2008年以"What Your Computer Does While You Wait"一文，用圖像將電腦組件之間的Bandwidth清楚表達。
  http://duartes.org/gustavo/blog/post/what-your-computer-does-while-you-wait
• Velocity 2010: Web Performance and Operations Conference.
  http://en.oreilly.com/velocity2010/public/schedule/topic/Web+Performance
• 分布式系统工程实践: 淘寶的Chuanhui在部落格上的作品，華文圈內對於分散式系統的經驗分享好文。
  http://www.nosqlnotes.net/wp-content/uploads/Distributed_System_Engineering_Practice.pdf
• 
  

悖論與Halting Problem

悖論是指某些奇特的推論。這些推論的假設和邏輯看似合理，但卻帶出明顯地不可接受的結論。(思方網) 

用邏輯的語言來說，悖論就是若假設命題A為真，經過一系列合理的推導，最終卻得到命題A為假的結論。

Halting Problem就是悖論的一個例子。Halting Problem是說是否可以寫一支程式，用來檢查任何一個程式是否會在有限的時間內結束。最後的結論是不可能存在這樣的一支程式，證明的方式正是利用悖論中的矛盾。

推導過程很簡單，首先假設這支程式已經存在，我們命名為H(M, w)，M為任一支被檢查的程式，w為M的輸入參數。為了方便說明，我把H(M, w)表示成為虛擬碼。

Function H(M, w)
{
  if M(w) halts
    return true
  else
    return false
}

現在有趣的來了。如果H(M, w)真的存在，我們當然可以"Reuse"他去寫其他的程式。例如說，我可以寫一個P(K)，虛擬碼如下：

Function P(K)
{
  if H(K, K) == true
    loop
  else
    return
}

這個P(K)是一個有可能會陷入無窮迴圈的程式。
然後，讓我們來考慮把P當做P(K)的參數，也就是P(P)事情會怎麼發展。

Case I: 如果P(P)會進入無窮迴圈，那H(P, P)就會傳回false，然後P(P)就會立刻結束(return)。

Case II: 如果P(P)會立刻結束，那H(P, P)就會回傳true，然後P(P)就會進入無窮迴圈。

嘿嘿，無論是哪一種Case，得出來的結論都自相矛盾。
因此，H(M, w)存在的命題必為假。也就是說，H(M, w)是不可能存在。

* * * * * * * *

這個證明的歷史可以追朔到Alan Turning在1937年發表的論文："On Computable Numbers With an Application to the Entscheidungsproblem"。原始論文是用Universal Turing Machine來證明。