Event Structure Semantics of Orc
S. Rosario, D. Kitchin, A. Benveniste, W. Cook, S. Haar, and C.
Jard
One challenge in developing wide-area distributed applications is
analyzing the system's non-functional properties, including timing
constraints and internal dependencies that can affect quality of
service. Analysis of non-functional properties requires a precise
formal semantics for the language in which the system is written; but
labelled transition systems and trace semantics, which are commonly
used for this purpose, do not facilitate this kind of analysis. Event
structures provide an explicit representation of the the causal
dependencies between events in the execution of a system. But event
structures are difficult to construct compositionally, because they
cannot easily represent fragments of a computation. In this paper we
present a partial-order semantics based on heaps (an explicitly encoded form
of occurrence nets with read arcs), which naturally represent fragments
of behavior. Heaps are then easily translated into asymmetric event
structures. The semantics is developed for Orc, an orchestration
language in which concurrent services are invoked to achieve a goal
while managing time-outs, exceptions, and priority. Orc, and this new
semantics, are being used to study quality of service (QoS) for wide
area orchestrations.
This work is partially supported by RNRT (National Research Network
in Telecommunication) through the SWAN
project (Self aWare mANagement).
Research
Report, extended version (pdf)
WSFM
2007 paper (pdf)