2005 | OriginalPaper | Buchkapitel
Safe Composition of Distributed Programs Communicating over Order-Preserving Imperfect Channels
verfasst von : Kai Engelhardt, Yoram Moses
Erschienen in: Distributed Computing – IWDC 2005
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The fundamental question considered in this paper is when program
Q
, if executed immediately after program
P
, is guaranteed not to interfere with
P
and be safe from interference by
P
. If a message sent by one of these programs is received by the other, it may affect and modify the other’s execution. The notion of
communication closed layers (CCLs)
introduced by Elrad and Francez in 1982 is a useful tool for studying such interference. CCLs have been considered mainly in the context of reliable FIFO channels (without duplication), where one can design programs layers that do not interfere with any other layer. When channels are less than perfect such programs are no longer feasible. The absence of interference between layers becomes context-dependent. In this paper we study the impact of message duplication and loss on the safety on the safety of layer composition. Using a communication phase operator, the
fits after
relation among programs is defined. If program
Q
fits after
P
then
P
and
Q
will not interfere with each other in executions of
P
∗
Q
. For programs
P
and
Q
in a natural class of programs we outline efficient algorithms for the following: (1) deciding whether
Q
fits after
P
; (2) deciding whether
Q
seals
P
, meaning that
Q
fits after
P
and no following program can communicate with
P
; and (3) constructing a
separatorS
that both fits after
P
and satisfies that
Q
fits after
P
∗
S
.