Struktura obiektu

Autor:

Hurfin, Michel ; Raynal, Michel

Współtwórca:

Korbicz, Józef - red. ; Uciński, Dariusz - red.

Tytuł:

On-the-fly detection of a class of word-based patterns in labelled DAGs

Tytuł publikacji grupowej:

AMCS, volume 7 (1997)

Temat i słowa kluczowe:

sterowanie ; sterowanie-teoria ; sztuczna inteligencja ; matematyka stosowana ; informatyka

Abstract:

The problem tackled in this paper originates from the debugging of distributed applications. Execution of such an application can be modelled as a partially ordered set of process states. The debugging of control flows (sequences of process states) of these executions is based on satisfying the predicates by process states. A process state that satisfies a predicate inherits its label. ; In this context, it follows that a distributed execution is a labelled directed acyclic graph (DAG for brevity). To debug or to determine if control flows of a distributed execution satisfy some property amounts to testing if the labelled DAG includes some pattern defined on predicate labels. ; This paper first introduces a general pattern (called the diamond necklace) which includes classical patterns encountered in distributed debugging. Then an efficient polynomial-time algorithm detecting such patterns in a labelled DAG is presented. To be easily adapted to an on-the-fly detection of the pattern in distributed executions, the algorithm visits the nodes of the graph according to a topological sort strategy.

Wydawca:

Zielona Góra: Uniwersytet Zielonogórski

Data wydania:

1997

Typ zasobu:

artykuł

Strony:

205-216

Źródło:

AMCS, volume 7, number 1 (1997) ; kliknij tutaj, żeby przejść

Jezyk:

eng

Prawa do dysponowania publikacją:

Biblioteka Uniwersytetu Zielonogórskiego