Causing Communication Closure: Safe Program Composition with Reliable Non-FIFO Channels

Details Causing Communication Closure: Safe Program Composition with Reliable Non-FIFO Channels Causing Communication Closure: Safe Program Composition with Reliable Non-FIFO Channels

2007-01-09

arxiv.org/abs/cs/0701064v1

Computer Science

Distributed, Parallel, and Cluster Computing

Scientific paper

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 reliable 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 \emph{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 investigation 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 programs. It is shown that every sealable program that is open to interference on $O(n^2)$ channels can be sealed using O(n) messages.

Affiliated with

Also associated with

No associations

Rating

Causing Communication Closure: Safe Program Composition with Reliable Non-FIFO Channels does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Causing Communication Closure: Safe Program Composition with Reliable Non-FIFO Channels, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Causing Communication Closure: Safe Program Composition with Reliable Non-FIFO Channels will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-722880