Reference:
Keijo Heljanko and Alin Stefanescu. Complexity results for checking distributed implementability. Technical Report 05/2004, Institute of Formal Methods in Computer Science, University of Stuttgart, Stuttgart, Germany, October 2004.
Abstract:
We consider the distributed implementability problem as: Given a labeled transition system TS together with a distribution of its actions over a set of processes, does there exist a distributed system over such that its global transitions system is `equivalent' to TS? We consider the distributed systems modeled as synchronous products of transitions systems [Arn94], respectively as asynchronous automata [Zie87]. In this paper we provide complexity bounds for the above problem with three interpretations for `equivalent' as transition system isomorphism, language equivalence, and bisimilarity. In particular, we solve problems left open in [Mor99,CMT99]. We also describe a logic programming implementation which complements the implementation for the synthesis of asynchronous automata initiated in [SEM03].
Keywords:
synthesis, distributed systems
Suggested BibTeX entry:
@techreport{USFMIHS04,
address = {Stuttgart, Germany},
author = {Keijo Heljanko and Alin Stefanescu},
institution = {Institute of Formal Methods in Computer Science, University of Stuttgart},
month = {October},
number = {05/2004},
pages = {37},
title = {Complexity Results for Checking Distributed Implementability},
year = {2004},
}
