Protocol Synthesis from Context-Free Processes using Event Structures

Akio Nakata(*),  Teruo Higashino(**), Kenichi Taniguchi(**)

(*) Department of Computer Science, Hiroshima City University
    nakata@cs.hiroshima-cu.ac.jp
(**) Department of Information and Computer Sciences, Osaka University
    {higashino,taniguchi}@ics.es.osaka-u.ac.jp


Abstract

In this paper, we propose a protocol synthesis method based on 
a partial order model (called event structures)
for the class of context-free processes.
First, we assign a unique name called event ID 
to every event executable by a given service specification.
An event ID is a finite sequence of symbols derived from
the context-free process specification.
Then we show that some interesting sets of events are expressible
by regular expressions on symbols, and that
the event structure can be finitely represented by a set
of relations among the regular expressions.
Finally, we present a method to derive a protocol specification
which implements a given service specification on distributed nodes,
by using the obtained finite representation of event structures.
The derived protocol specification contains the minimum message exchanges 
necessary to ensure the partial order of 
events of the service specification.

keywords: 
formal description techniques, distributed systems, 
protocol synthesis, context-free processes, event structures