分散與行動計算系統中因果次序協定之研究

Abstract

在許多分散式系統的應用中，要求送至同一目的地的所有訊息須以不違反 其因果次序(causal ordering) 的方式完成傳遞。所謂訊息的因果次序， 乃是取決於其送出事件間的邏輯時間順序。傳統確保訊息因果次序的方法 ，有的是將所有的處理負荷放在單一程序上；有的是利用向量時鐘 (vector clocks) 或類似的機制來獲得訊息送出事件間的邏輯時間順序。 後者的做法將使得每一個送出的訊息皆須附帶一個O(n2)的訊息表頭 (message header)，其中n代表系統中程序的數目。雖然已有學者證明O( n2)的訊息額外空間負擔 (message space overhead) 已經是理論上的最 佳值，不過傳統的方法顯然並不適用於擁有較多程序的系統 。我們針對 這個缺點，提出一些改進的做法，具體的內容有：(1) 提出一個可重置 (reset) 分散式系統中向量時鐘的演算法。此方法不但解決了傳統訊息因 果次序協定中，時鐘度量可能會因滿溢 (overflow) 而造成錯誤的問題， 同時也使得我們能夠以有限的位元數來實作可無限期運作的向量時鐘，有 效減少訊息額外空間負擔。(2) 藉由將程序叢集化 (clustering) 的方 法，將系統中的訊息交由少數的程序來處理。如果每一叢集遞迴地進行叢 集化，整個系統將形成一階層化叢集。此種方法有效地減少了訊息表頭的 大小。由於我們只明確界定了訊息在不同叢集間的傳遞介面與路徑，而沒 有限制各叢集內確保訊息因果次序所需使用的方法，所以每個叢集可自由 決定其區域的協定。此種特性使得我們的做法特別適用於無單一網路管理 機構的網路，如 Internet。分析結果顯示，適當的叢集化策略可使訊息 表頭的大小降為O(n) 。(3) 設計在行動計算環境下的訊息因果次序協定 。由於行動電腦具有可移動的特性，如果直接而未加修改地將 (2) 的方 法移植過來，固然可減少訊息表頭額外的空間負擔，卻也會使得行動電腦 的交遞 (handoff) 程序變得非常複雜，抵銷了原先設計上的優點。我們 特別針對此點，設計一個交遞程序簡單而訊息表頭額外的空間負擔低的協 定。同時我們也與其他學者的方法做一比較。 Many distributed applications demand that causally related messages directed to the same destinations are certain to be delivered in an order consistent with their causality. Ensuring this property is a problem called causal message ordering (CMO). Previously proposed CMO approaches either place the entire processing load on a single process or impose quadratic message header size in the number of participating processes. These solutions are thus only suitable for small-scale systems. This dissertation proposes tow techniques to cope with scalability problem. The first technique aims to reduce message header size by limiting the number of bits used to implement an entry of vector clocks, which are used in many CMO approaches for capturing message causality. When any clock is about to overflow, our proposed algorithm resets all clocks on the fly, with the guarantee that CMO is still respected.The second technique we proposed is to organize processes into a number of clusters such that, within each cluster, any CMO methods can be usefully employed. Our performance analysis indicates that our approach can decrease processing loads on hot-spot sites that is introduced by the centralized approach, or, alternatively, can decompose costly message space overhead, brought in by the fully distributed approach, to small components.We then propose a CMO protocol for mobile computing systems. A mobile computing system is an extension of conventional distributed computing systems such that a computing entity is able to retain its network connection while in transit. Previously proposed method suffers from costly handoff cost and unnecessary delays in delivering messages. When compared with previous proposals, our method provides an alternative with a low handoff cost, medium message overhead, and low probability of unnecessary inhibition in delivering messages.