Paper Info
Title
Causing Communication Closure: Safe Program Composition with Reliable Non-FIFO Channels
Abstract
A semantic framework for analyzing safe composition of distributed programs is presented. Its applicability is illustrated by a study of program composition when communication is reli- able but not necessarily FIFO. In this model, special care must be taken to ensure that messages do not accidentally overtake one another in the composed program. We show that barriers do not exist in this model. Indeed, no program that sends or receives messages can automatically be composed with arbitrary programs without jeopardizing their intended behavior. Safety of composition becomes context-sensitive and new tools are needed for ensuring it. A notion of sealing is defined, where if a program P is immediately followed by a program Q that seals P then P will be communication-closed—it will execute as if it runs in isolation. The investi- gation of sealing in this model reveals a novel connection between Lamport causality and safe composition. A characterization of sealable programs is given, as well as efficient algorithms for testing if Q seals P and for constructing a seal for a significant class of program s. It is shown that every sealable program that is open to interference on O(n2) channels can be sealed using
Year
DOI
Venue
2009
10.1007/s00446-009-0081-9
Clinical Orthopaedics and Related Research
Keywords
DocType
Volume
Span Tree,Causal Chain,Virtual Channel,Program Graph,Dummy Node
Journal
abs/cs/070
Issue
ISSN
Citations 
2
0178-2770
0
PageRank 
References 
Authors
0.34
20
2
Name
Order
Citations
PageRank
Kai Engelhardt176235.62
Yoram Moses22120417.71