Abstract
分散式系統在計算的過程中，常需要做整體狀態的偵測，諸如“死結偵測”與“計算終止偵測”。由於系統的非同步性使得一個整體的狀態的偵測或快照(Snapshot)不可能在某一瞬間獲得；因此，每個計算站的區域快照將在不同的時刻被記錄下來，組合起來的整體快照其於因果律(Causality) 必需符合一致性(Consistency) 。也就是說任何包含於快照內的果(Effect)，其相對應之因(Cause) 也必包含於快照之內。如何來控制各計算站的區域快照時間，使其整體快照符合以上之要求，此謂快照問題。一個整體狀態的快照可作為復原或重播(Replay)之依據。當某一個計算站發現其目前的計算不正常時，它可能想要改變目前的整體狀態至一個它所期望的系統快照上，如何來控制目前整體狀正確地被轉移，謂之重播問題。其主要應用有容錯計算應用與交談式分散除錯系統。本篇論文探討這兩個問題其復雜度的下限(Lower bound) ，并依協定(Protocol)之行為與通道(Channel) 之型態各別給予分析結果。協定之行為分成禁制與非禁制(Nom-inhibitory)，通道之型態則分成FIFO 與Non-FIFO 兩種。本篇論文同時也提出了解決這兩個問題的協定(Protocol)。一個是非禁制的快照協定可用於Non-FIFO通道, 此協定不必像以往的方法記錄所有的訊息(Message) ；另一個是非禁制的重播協字可用於FIFO通道，此協定用了最少的訊息，符合該問題復雜度之下限，故為訊息最佳化協定(Message-optimal Pro-tocol) 。