Complexity Results for Checking Distributed Implementability

Reference:

Keijo Heljanko and Alin Stefanescu. Complexity results for checking distributed implementability. In Jörg Desel and Yosinori Watanabe, editors, Proceedings of the 5th International Conference on Application of Concurrency to System Design (ACSD'2005), pages 78–87, St Malo, France, June 2005. IEEE Computer Society.

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].

Keywords:

synthesis, distributed systems

Suggested BibTeX entry:

@inproceedings{HelSte:ACSD05,
    address = {St Malo, France},
    author = {Keijo Heljanko and Alin Stefanescu},
    booktitle = {Proceedings of the 5th International Conference on Application of Concurrency to System Design (ACSD'2005)},
    editor = {J{\"o}rg Desel and Yosinori Watanabe},
    month = {June},
    pages = {78--87},
    publisher = {{IEEE} Computer Society},
    title = {Complexity Results for Checking Distributed Implementability},
    year = {2005},
}