Complexity Results for Checking Distributed Implementability

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{US-FMI-HS04,
    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},
}