Detecting arbitrary stable properties using efficient snapshots

Ajay D. Kshemkalyani

doi:10.1109/TSE.2007.1000

Detecting arbitrary stable properties using efficient snapshots

2007-05-01

10

OA

AI

A

Ajay D. Kshemkalyani *

B

Bin Wu

DOI：10.1109/TSE.2007.1000

原文链接

原文求助

摘要

En 中文

A stable property continues to hold in an execution once it becomes true. Detecting arbitrary stable properties efficiently in distributed executions is still an open problem. The known algorithms for detecting arbitrary stable properties and snapshot algorithms used to detect such stable properties suffer from drawbacks such as the following: They incur the overhead of a large number of messages per global snapshot, or alter application message headers, or use inhibition, or use the execution history, or assume a strong property such as causal delivery of messages in the system. We solve the problem of detecting an arbitrary stable property efficiently under the following assumptions: P1) The application messages should not be modified, not even by timestamps or message coloring. P2) No inhibition is allowed. P3) The algorithm should not use the message history. P4) Any process can initiate the algorithm. This paper proposes a family of nonintrusive algorithms requiring 6(n-1) control messages, where n is the number of processes. A three-phase strategy of uncoordinated observation of local states is used to give a consistent snapshot from which any stable property can be detected. A key feature of our algorithms is that they do not rely on the processes continually and pessimistically reporting their activity. Only the relevant activity that occurs in the thin slice during the algorithm execution needs to be examined.

Keyword:

distributed system

global state

stable predicate

stable property

distributed snapshot

Detecting arbitrary stable properties using efficient snapshots

摘要

期刊

机构

引用论文