Paper Info
Title
Entailment-based actions for coordination
Abstract
Coordination seems to require (at least in part) a persistent repository of information that concurrent agents can query and update. Indeed, most coordination languages are based on a shared data space model. They differ in the details of how actions and processes are defined, but most assume the data space to have a multiset structure, and actions to be rewritings. We find this view too particular and not expressive enough in many practical cases, and set out in this paper to develop a more general theory of actions, abandoning the syntactic rewriting paradigm in favour of a more abstract notion of update based on entailment. Actions may impose certain properties to be entailed or not entailed, and the corresponding update is the minimal change, possibly by removing information and adding new one, that satisfies the (dis)entailment requirements. We work with abstract situations (standing for information states) ordered under entailment. We show that if a situation space is a coherent, prime algebraic, consistently complete poset then a suitable class of its subsets, which we call definite, corresponds to update operations with suitable generality (any situation can be obtained by an update of any other) and good compositional properties (closure under sequential and synchronous composition). These updates can be seen as unconditional determinate actions, i.e. total functions from situations to situations; these functions are always a composition of a restriction (losing information) and an expansion (adding consistent information). We show that the space of updates is itself an ordered structure similar to a situation space. Then we consider general actions, which may be conditional and nondeterministic. They thus represent arbitrary relations between situations, but are actually more specific, coding the intensional rather than extensional behaviour, this being relevant for the synchronous composition. We formulate general actions as (suitably restricted) relations between situations and definite sets, define their synchronous, sequential and choice compositions, and show them to be fully abstract with respect to observing situation transitions under any compositional context. The synchronous and sequential compositions give rise to an intrinsic notion of independence of actions, that reflects their ability to be truly concurrent.
Year
DOI
Venue
1998
10.1016/S0304-3975(97)00152-7
Theor. Comput. Sci.
Keywords
DocType
Volume
Entailment-based action
Journal
192
Issue
ISSN
Citations 
2
Theoretical Computer Science
0
PageRank 
References 
Authors
0.34
8
2
Name
Order
Citations
PageRank
Luís Monteiro112619.98
António Porto223035.74