Efficient decentralized monitoring of safety in distributed systems

Koushik Sen, Abhay Vardhan, Gul Agha, Grigore Roşu

Research output: Contribution to journalConference article

Abstract

We describe an efficient decentralized monitoring algorithm that monitors a distributed program's execution to check for violations of safety properties. The monitoring is based on formulae written in PT-DTL, a variant of past time linear temporal logic that we define. PT-DTL is suitable for expressing temporal properties of distributed systems. Specifically, the formulae of PT-DTL are relative to a particular process and are interpreted over a projection of the trace of global states that represents what that process is aware of. A formula relative to one process may refer to other processes' local states through remote expressions and remote formulae. In order to correctly evaluate remote expressions, we introduce the notion of KNOWLEDGEVECTOR and provide an algorithm which keeps a process aware of other processes' local states that can affect the validity of a monitored PT-DTL formula. Both the logic and the monitoring algorithm are illustrated through a number of examples. Finally, we describe our implementation of the algorithm in a tool called DIANA.

Original languageEnglish (US)
Pages (from-to)418-427
Number of pages10
JournalProceedings - International Conference on Software Engineering
Volume26
StatePublished - Oct 4 2004
EventProceedings - 26th International Conference on Software Engineering, ICSE 2004 - Edinburgh, United Kingdom
Duration: May 23 2004May 28 2004

Fingerprint

Monitoring
Temporal logic

ASJC Scopus subject areas

  • Software

Cite this

Efficient decentralized monitoring of safety in distributed systems. / Sen, Koushik; Vardhan, Abhay; Agha, Gul; Roşu, Grigore.

In: Proceedings - International Conference on Software Engineering, Vol. 26, 04.10.2004, p. 418-427.

Research output: Contribution to journalConference article

@article{80b5a391a65b4564a3c52ecee3b7ad98,
title = "Efficient decentralized monitoring of safety in distributed systems",
abstract = "We describe an efficient decentralized monitoring algorithm that monitors a distributed program's execution to check for violations of safety properties. The monitoring is based on formulae written in PT-DTL, a variant of past time linear temporal logic that we define. PT-DTL is suitable for expressing temporal properties of distributed systems. Specifically, the formulae of PT-DTL are relative to a particular process and are interpreted over a projection of the trace of global states that represents what that process is aware of. A formula relative to one process may refer to other processes' local states through remote expressions and remote formulae. In order to correctly evaluate remote expressions, we introduce the notion of KNOWLEDGEVECTOR and provide an algorithm which keeps a process aware of other processes' local states that can affect the validity of a monitored PT-DTL formula. Both the logic and the monitoring algorithm are illustrated through a number of examples. Finally, we describe our implementation of the algorithm in a tool called DIANA.",
author = "Koushik Sen and Abhay Vardhan and Gul Agha and Grigore Roşu",
year = "2004",
month = "10",
day = "4",
language = "English (US)",
volume = "26",
pages = "418--427",
journal = "Proceedings - International Conference on Software Engineering",
issn = "0270-5257",
publisher = "IEEE Computer Society",

}

TY - JOUR

T1 - Efficient decentralized monitoring of safety in distributed systems

AU - Sen, Koushik

AU - Vardhan, Abhay

AU - Agha, Gul

AU - Roşu, Grigore

PY - 2004/10/4

Y1 - 2004/10/4

N2 - We describe an efficient decentralized monitoring algorithm that monitors a distributed program's execution to check for violations of safety properties. The monitoring is based on formulae written in PT-DTL, a variant of past time linear temporal logic that we define. PT-DTL is suitable for expressing temporal properties of distributed systems. Specifically, the formulae of PT-DTL are relative to a particular process and are interpreted over a projection of the trace of global states that represents what that process is aware of. A formula relative to one process may refer to other processes' local states through remote expressions and remote formulae. In order to correctly evaluate remote expressions, we introduce the notion of KNOWLEDGEVECTOR and provide an algorithm which keeps a process aware of other processes' local states that can affect the validity of a monitored PT-DTL formula. Both the logic and the monitoring algorithm are illustrated through a number of examples. Finally, we describe our implementation of the algorithm in a tool called DIANA.

AB - We describe an efficient decentralized monitoring algorithm that monitors a distributed program's execution to check for violations of safety properties. The monitoring is based on formulae written in PT-DTL, a variant of past time linear temporal logic that we define. PT-DTL is suitable for expressing temporal properties of distributed systems. Specifically, the formulae of PT-DTL are relative to a particular process and are interpreted over a projection of the trace of global states that represents what that process is aware of. A formula relative to one process may refer to other processes' local states through remote expressions and remote formulae. In order to correctly evaluate remote expressions, we introduce the notion of KNOWLEDGEVECTOR and provide an algorithm which keeps a process aware of other processes' local states that can affect the validity of a monitored PT-DTL formula. Both the logic and the monitoring algorithm are illustrated through a number of examples. Finally, we describe our implementation of the algorithm in a tool called DIANA.

UR - http://www.scopus.com/inward/record.url?scp=4644288597&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=4644288597&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:4644288597

VL - 26

SP - 418

EP - 427

JO - Proceedings - International Conference on Software Engineering

JF - Proceedings - International Conference on Software Engineering

SN - 0270-5257

ER -