Quotient graphs for the analysis of asymmetric distributed systems : surveying two alternative approaches
Contributo in Atti di convegno
Data di Pubblicazione:
2005
Citazione:
Quotient graphs for the analysis of asymmetric distributed systems : surveying two alternative approaches / C. Bellettini, L. Capra - In: Proceedings of the 19th IEEE International parallel and distributed processing symposium, IPDPS’05 : Denver, Colorado, USA, 2005 / [a cura di] G. Min, M. Ould-Khaoua. - Los Alamitos : IEEE Computer Society, 2005. - ISBN 0769523129. (( Intervento presentato al 19. convegno International Parallel and Distributed Processing Symposium (IPDPS) tenutosi a Denver, USA nel 2005 [10.1109/IPDPS.2005.371].
Abstract:
State-space based techniques represent a powerful analysis tool of discrete-event systems. One way to face the state-space explosion is the exploitation of behavioral symmetries of distributed systems. Well-Formed Coloured Petri Nets (WN) allow the direct construction of a symbolic reachability graph (SRG) that captures symmetries suitably encoded in WN syntax. Most real systems however mix symmetric and asymmetric behaviors.
The SRG, and more generally, all those approaches based on a static description of symmetries, have shown not to be effective in such cases. In this paper two quotient graphs are proposed as effective analysis frameworks for asymmetric systems. Both rely on WN syntax extended with relational operators. The first one is an extension of the SRG that exploits local symmetries.
The second technique uses linear constraints and substate inclusion in order to aggregate states. An asymmetric distributed leader-election algorithm is used as running example.
Tipologia IRIS:
03 - Contributo in volume
Elenco autori:
C. Bellettini, L. Capra
Link alla scheda completa:
Titolo del libro:
Proceedings of the 19th IEEE International parallel and distributed processing symposium, IPDPS’05 : Denver, Colorado, USA, 2005