Distributed breadth-first search LTL model checking

BARNAT, Jiří a Ivana ČERNÁ. Distributed breadth-first search LTL model checking. Formal Methods in System Design. Springer Netherlands, 2006, roč. 29, č. 2, s. 117-134. ISSN 0925-9856.

Základní údaje

Originální název

Distributed breadth-first search LTL model checking

Název česky

Distribuované ověřování modelu LTL s využitím prohledávání grafu do šířky

Autoři

BARNAT, Jiří (203 Česká republika, garant) a Ivana ČERNÁ (203 Česká republika)

Vydání

Formal Methods in System Design, Springer Netherlands, 2006, 0925-9856

---

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Nizozemské království

Utajení

není předmětem státního či obchodního tajemství

Odkazy

URL

Impakt faktor

Impact factor: 0.900

Kód RIV

RIV/00216224:14330/06:00015452

Organizační jednotka

Fakulta informatiky

UT WoS

000241173800002

Klíčová slova anglicky

LTL model checking; Distributed memory; Breadth-first Search

Štítky

Breadth-first Search, distributed memory, LTL model checking

Příznaky

Mezinárodní význam, Recenzováno

---

Anotace

V originále

We propose a parallel distributed memory on-the-fly algorithm for enumerative LTL model checking. The algorithm is designed for networks of workstations communicating via MPI. The detection of cycles (faulty runs) effectively employs the so-called back-level edges. In particular, a parallel level synchronized breadth-first search of the graph is performed to discover all back-level edges, and for each level the back-level edges are checked in parallel by a nested search procedure to confirm or refute the presence of a cycle. Several improvements of the basic algorithm are presented and advantages and drawbacks of their application to distributed LTL model checking are discussed.

Česky

Je zde navrhnut a experimentalně vyhodnocen algoritmus pro detekci akceptujicích cyklů v grafu, založený na tzv. back-level hranách. Algoritmus je dále rozšířen o několik nezbytných módů, které jsou nezbytné pro vytvoření skutečného verifikačního nástroje pro LTL ověřování modelů. Tento nástroj byl implementován a experimentálně vyhodnocen na několika směrodatných vstupech.

---

Návaznosti

GA201/06/1338, projekt VaV	Název: Automatizovaná verifikace softwaru Investor: Grantová agentura ČR, Automatizovaná verifikace softwaru
GD102/05/H050, projekt VaV	Název: Integrovaný přístup k výchově studentů DSP v oblasti paralelních a distribuovaných systémů Investor: Grantová agentura ČR, Integrovaný přístup k výchově studentů DSP v oblasti paralelních a distribuovaných systémů
MSM0021622419, záměr	Název: Vysoce paralelní a distribuované výpočetní systémy Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Vysoce paralelní a distribuované výpočetní systémy
1ET408050503, projekt VaV	Název: Techniky automatické verifikace a validace softwarových a hardwarových systémů Investor: Akademie věd ČR, Techniky automatické verifikace a validace softwarových a hardwarových systémů
1M0545, projekt VaV	Název: Institut Teoretické Informatiky Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Institut Teoretické Informatiky