A verification algorithm for Declarative Concurrent Programming - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2006

A verification algorithm for Declarative Concurrent Programming

Résumé

A verification method for distributed systems based on decoupling forward and backward behaviour is proposed. This method uses an event structure based algorithm that, given a CCS process, constructs its causal compression relative to a choice of observable actions. Verifying the original process equipped with distributed backtracking on non-observable actions, is equivalent to verifying its relative compression which in general is much smaller. We call this method Declarative Concurrent Programming (DCP). DCP technique compares well with direct bisimulation based methods. Benchmarks for the classic dining philosophers problem show that causal compression is rather efficient both time- and space-wise. State of the art verification tools can successfully handle more than 15 agents, whereas they can handle no more than 5 following the traditional direct method; an altogether spectacular improvement, since in this example the specification size is exponential in the number of agents.
Fichier principal
Vignette du fichier
RR-dcp.pdf (288.99 Ko) Télécharger le fichier
Loading...

Dates et versions

inria-00081218 , version 1 (22-06-2006)

Identifiants

Citer

Jean Krivine. A verification algorithm for Declarative Concurrent Programming. [Research Report] 2006. ⟨inria-00081218⟩

Collections

INRIA INRIA2 LARA
48 Consultations
49 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More