The synthesis of communication protocols
type: Item
instance of: scholarly article
title: The synthesis of communication protocols
zbMATH Open document ID: 0636.68052
DOI: 10.1007/BF01762126
published in: Algorithmica
publication date: 1988-01-01T00:00:00Z
review text: 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 satifiable; 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.
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68N25
Mathematics Subject Classification ID: 94C15
Mathematics Subject Classification ID: 68N99
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q05
zbMATH DE Number: 4037205
zbMATH Keywords: communicating
zbMATH Keywords: finite automata
zbMATH Keywords: communication protocols
zbMATH Keywords: synthesis algorithm
zbMATH Keywords: knowledge logic
zbMATH Keywords: PSPACE-complete
zbMATH Keywords: distributed system
zbMATH Keywords: polynomial-time algorithm
author: Foto N. Afrati
author: Christos Papadimitriou
author: George Papageorgiou
MaRDI profile type: Publication
cites work: How processes learn
cites work: A model-theoretic analysis of knowledge
cites work: Q4198056
cites work: Q4184295
cites work: Knowledge and common knowledge in a distributed environment
cites work: Q4065570
cites work: Recoverability of Communication Protocols--Implications of a Theoretical Study
cites work: Q3948585
full work available at URL: https://doi.org/10.1007/bf01762126
OpenAlex ID: W2002371579
description: scientific article; zbMATH DE number 4037205