Abstract
所謂群集，是指接收相同信息的一群行程(Process) 。在分散式系統中，群集經常會透過信息的傳送，來執行儲存於信息上的命令，以便完成一件任務。由於信息的延誤和非先進先出的管道傳輸，導致每個行程可能以不同的順序去執行所收到的信息。然而，在某些應用上，群集需要以某種順序去執行這些信息。因此，信息傳送的順序，在某些狀錶是很重要的。到目前為止，已經有三種信息傳送的性質被提出。它們分別是(1) 單一來源排序(2)多重來源排序(3) 多重群集排序。其中以(3) 的性質最嚴謹。本篇論文中，我們提出一個演算法可以達成性質(3)。所謂多重群集排序, 是指任意兩個行程，分別接收到相同的兩個信息時，此兩個行程以相同的次序執行所收到的信息。但是，這兩個信息可能由不同的行程送出。為了達到此性質，每個屬於同一群集的行程，必須依照相同的順序來排列執行佇列。這些行程每收到信息時，依照上面的資訊，將此信息放置於某個佇列的適當位置。然後，以循環式排班的方式去執行它。我們的方法，在執行信息之前，不需另外送出控制信息與其他行程溝通。也不需維護邏輯時鐘和樹狀結構。於本篇論文所提出的系統，我們做了以下的假設。多重群集是存在的，信息傳輸是可靠的，傳輸管道是非先進先出且信息延誤是限的。