死結偵測在分散式系統上是一個重要的問題，並且目前這個問題已經有了很多研究成
果。一般而言，所謂的死結狀態是指很多處理單元彼此要求資源，然而卻無限期的等
待這些要求被滿足。
此篇論文提出在 Q中取 P要求模式下的一個死結偵測分散式的方法。在前述的模式中
，一個處理單元可能在 Q個相同的資源中要求 P個，而每一個處理單元不是活動的，
就是空閒的。一個活動的處理單元在它發出一個要求後就會成為空間的，並且一個空
閒的處理單元只有在它所要求的 Q個資源中被允許 P個後，才會再活動起來。
我們假設訊息的延遲是任意的，但卻是有限，而且訊息在通道中是先進先出的。在這
些假設之下，此篇所提出方法有下列的性質：(1) 它絕不會偵測出錯誤的死結；(2 )
它在有限的時間內偵測出所有的死結。
很多死結偵測的分散式方法已被提出，在這些方法之中，Bracha和Toueg 所提出的方
法亦是 Q中取 P要求模式。但是我們有兩個主要的改進：(1) 我們所提出的方法是完
全的分散式；而且 (2)我們利用分散式的快照技巧於證明中。在我們的方法法，偵測
死結所需的資訊是分散在所有有關偵側計算的處理單元中，而不是像上述兩位作者的
方法將資訊集中於某一個處理單元。
在分散式的證明中，利用操作論證(operational arguments) 來證明是麻煩而又容易
錯誤的，很多用此種證明的論文已被證實是不正確的或是證得太複雜。我們不用操作
論證，而用分散式快照技巧來證明。分散式快照技巧是由Chandy和 Lamport所提出，
然而我們的技巧比其更一般化，因為原先的技巧需要所有的處理單元皆照下快照，而
我們的技巧卻只需部份的處理單元照下快照即可。
|