Další formáty:
BibTeX
LaTeX
RIS
@inproceedings{1376942,
author = {Dalsgaard, Andreas E. and Enevoldsen, Soeren and Larsen, Kim G. and Srba, Jiří},
address = {Netherlands},
booktitle = {Proceedings of Symposium on Dependable Software Engineering: Theories, Tools and Applications (SETTA'16)},
doi = {http://dx.doi.org/10.1007/978-3-319-47677-3_13},
keywords = {dependency graphs; verification; CTL; Petri nets},
howpublished = {tištěná verze "print"},
language = {eng},
location = {Netherlands},
isbn = {978-3-319-47676-6},
pages = {197-212},
publisher = {Springer},
title = {Distributed Computation of Fixed Points on Dependency Graphs},
url = {http://link.springer.com/chapter/10.1007/978-3-319-47677-3_13},
year = {2016}
}
TY - JOUR
ID - 1376942
AU - Dalsgaard, Andreas E. - Enevoldsen, Soeren - Larsen, Kim G. - Srba, Jiří
PY - 2016
TI - Distributed Computation of Fixed Points on Dependency Graphs
PB - Springer
CY - Netherlands
SN - 9783319476766
KW - dependency graphs
KW - verification
KW - CTL
KW - Petri nets
UR - http://link.springer.com/chapter/10.1007/978-3-319-47677-3_13
L2 - http://link.springer.com/chapter/10.1007/978-3-319-47677-3_13
N2 - Dependency graph is an abstract mathematical structure for representing complex causal dependencies among its vertices. Several equivalence and model checking questions, boolean equation systems and other problems can be reduced to fixed-point computations on dependency graphs. We develop a novel distributed algorithm for computing such fixed points, prove its correctness and provide an efficient, open-source implementation of the algorithm. The algorithm works in an on-the-fly manner, eliminating the need to generate a priori the entire dependency graph. We evaluate the applicability of our approach by a number of experiments that verify weak simulation/bisimulation equivalences between CCS processes and we compare the performance with the well-known CWB tool. Even though the fixed-point computation, being a P-complete problem, is difficult to parallelize in theory, we achieve significant speed-ups in the performance as demonstrated on a Linux cluster with several hundreds of cores.
ER -
DALSGAARD, Andreas E., Soeren ENEVOLDSEN, Kim G. LARSEN a Jiří SRBA. Distributed Computation of Fixed Points on Dependency Graphs. In \textit{Proceedings of Symposium on Dependable Software Engineering: Theories, Tools and Applications (SETTA'16)}. Netherlands: Springer, 2016, s.~197-212. ISBN~978-3-319-47676-6. Dostupné z: https://dx.doi.org/10.1007/978-3-319-47677-3\_{}13.
|
