TCS / Research / Publications / Complexity Results for Checking Distributed Implementability
Helsinki University of Technology, 
     Laboratory for Theoretical Computer Science

Complexity Results for Checking Distributed Implementability

Reference:

Keijo Heljanko and Alin Ştefănescu. 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 {\c{S}}tef\u{a}nescu},
    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},
}

See www.tcs.hut.fi ...

[TCS main] [Contact Info] [Personnel] [Research] [Publications] [Software] [Studies] [News Archive] [Links]
Latest update: 19 January 2010.