ISSN:
1432-0541
Keywords:
Communication protocols
;
Synthesis algorithm
;
Knowledge logic
;
Polynomial algorithm
;
PSPACE-complete
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract We define a notation (specification language) for describing desired patterns of communication among components of a distributed system through multiport, unreliable channels. Our language specifies the network topology, and the kinds of information transmission desired. We give a polynomial-time algorithm for determining whether a specification is satisfiable; our algorithm can actually construct a protocol that achieves the specified exchange of information, optimized with respect to two possible criteria. Examples suggest that our method can automatically synthesize reasonably complex protocols.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01762126
Permalink