可容錯之行動物件定位演算法

Abstract

找出特定物件位置以便遞送欲傳給該 物件之訊息，是所有分散式系統都應有能力 完成的工作。多數支援行動物件的系統利用 所謂的home-based 策略來解決定位問題。在 這類方法中，所有的物件都有一個固定的 家，欲傳給某一物件的訊息必須先取道該物 件的家。這類方法有容錯上的弱點，當一個 物件的家損壞了或是到這個家的所有通訊路 線都損壞了，那系統中的使用者便無法再操 作該物件。 我們的主要研究目的便在探討容錯能 力好的追蹤物件位置的分散式目錄結構及定 位演算法。這項研究是我們稍早的一個名為 「分散式互斥與物件追蹤」的國科會研究計 畫的延續。在該計畫裡，我們探討如何將分 散式互斥演算法應用到行動物件的定位工 作。我們從既有互斥演算法推導出兩個定位 演算法；我們的主要貢獻在於處理容錯性的 問題。

Locating an object so as to deliver messages intended for the object is a basic task of every distributed system. Most systems that support mobile objects use home-based tracking strategies wherein every object has a designated home and all messages for an object (or at least the first one in the same session) are routed through its home. One problem of this type of protocols is that an object becomes inaccessible when its home fails or communications to its home are blocked. We investigate distributed directory structures and algorithms for tracking mobile objects that exhibit a high degree of tolerance to node and communication failures. This research is a continuation of a previous NSC-sponsored project titled ``Distributed Mutual Exclusion and Object Tracking' (NSC 89-2213-E-002-021) where we explored the idea of adapting token-based mutual exclusion algorithms for object tracking. We derive from existing token-based algorithms two schemes for tracking mobile objects. Our main contribution lies in addressing fault tolerance issues.