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