當分散式系統的節點數成長，任何節點都越來越難掌握其他節點的狀況。而這種知識對執行分散式演算法——繞送（routing）、多播、資料放置、搜尋等——可能很重要。我們已看過許多把大量節點組織成特定拓撲以利演算法執行的例子；本節看另一種與時間量測相關的組織方式。

在幾何覆蓋網路（geometric overlay network）中，每個節點被賦予 m 維幾何空間中的一個位置，使空間中兩節點的距離反映真實世界的效能指標。最簡單也最常用的例子是距離對應節點間延遲：給定節點 P 與 Q，距離 d(P, Q) 反映訊息從 P 到 Q（往返皆然）要走多久。

應用#

• 就近轉發請求：伺服器 O 上的網站複製到網際網路上多台伺服器 S1…Sk。客戶端 C 向 O 請求頁面時，O 可以把請求轉給離 C 最近（回應時間最佳）的伺服器——只要知道 C 與各副本伺服器的幾何位置，O 挑出使 d(C, Si) 最小的 Si 即可。這個選擇只需 O 的本地運算，不必實際取樣 C 與每台副本伺服器之間的延遲。
• 最佳副本放置（下一章詳談）：網站蒐集了客戶端的位置後，若要把內容複製到 K 台伺服器，可以算出使「客戶端到副本的平均回應時間」最小的 K 個最佳位置。只要客戶端與伺服器的幾何位置能反映延遲，這種計算幾乎是輕而易舉。
• 位置繞送（position-based routing）（Araujo and Rodrigues, 2005；Stojmenovic, 2002）：只用位置資訊轉發訊息。例如一個樸素的演算法：每個節點把訊息轉給離目的地最近的鄰居。雖然這個特定演算法不保證收斂，但它說明了決策只用本地資訊——不必像傳統繞送演算法那樣把連結資訊散播給全網節點。

以三邊量測計算位置#

理論上，在 m 維幾何空間中定位一個節點，需要對 m + 1 個已知位置的節點做距離量測。以 m = 2 為例：節點 P 要算自己的位置，就聯絡三個位置已知的節點並量測與各自的距離——只接觸一個節點，P 只知道自己在某個圓上；接觸兩個，知道自己在兩圓交點之一（通常有兩點）；第三個節點才能定出實際位置。

與 GPS 相同，P 解三條方程式（兩個未知數 xP、yP）即可算出自己的座標 (xP, yP)；其中 di 通常對應 P 與位於 (xi, yi) 之節點間的量測延遲，可估為往返延遲的一半。

但延遲的量測值會隨時間改變，效果是 P 每次重算位置都會得到不同結果。更麻煩的是，若其他節點用 P 的當前位置來計算自己的座標，P 的定位誤差會連帶影響其他節點的定位精度。

不同節點量到的距離通常彼此不一致。例如在一維空間中：R 量到與 Q 的距離是 2.0、d(P, Q) 已量得 1.0，但 R 量 d(P, R) 卻得到 3.2——與前兩個量測明顯矛盾。把計算移到二維空間可以化解這個小例子的矛盾，但面對大量量測值，這不是通解。事實上，網際網路的延遲量測可能違反三角不等式（triangle inequality：對任意三節點 P、Q、R，必須 d(P, R) ≤ d(P, Q) + d(Q, R)），因此完全消除不一致通常是不可能的。

兩種實務做法#

地標法#

Ng and Zhang (2002) 提出使用 L 個特殊節點 b1, …, bL，稱為地標（landmarks）：

• 地標們量測彼此的成對延遲 d(bi, bj)，交由一個中央節點計算每個地標的座標——中央節點的目標是讓「量測距離與定位後幾何距離」的總誤差函數最小化。
• 最小化中隱藏的參數是維度 m。顯然要 L > m，但沒有什麼阻止我們選一個遠小於 L 的 m。之後，任一節點 P 量測自己到 L 個地標的距離，同樣以最小化誤差的方式算出自己的座標。

結果顯示：只要地標選得好，m 可以小到 6 或 7，而任意兩節點 P、Q 的幾何距離估計值與實際延遲 d(P, Q) 的差距不超過 2 倍（Szyamniak et al., 2004）。

彈簧法（Vivaldi）#

另一種做法是把節點集合看成一個巨大的系統，節點之間以彈簧相連。此時「量測距離與幾何距離的差 |d(P, Q) − d̂(P, Q)|」表示 P、Q 相對於彈簧系統靜止狀態被移位的程度。讓每個節點（微幅）調整自己的位置，可以證明系統最終會收斂到總誤差最小的最佳組態。Vivaldi 採用這個做法，細節見 Dabek et al. (2004a)。