[L1] ================================================ AMAST Links 01 02

                  Layered Design of Parallel Systems 
                  Wil Janssen - University of Twente
                          PhD Thesis Abstract

  In this thesis I discuss a method for the correct development of
programs for parallel or distributed computer systems. The idea is to
develop the system stepwise, starting from a sequential or layered
initial design that reflects the logical structure of the system.  In
a number of steps the initial design is refined to meet the actual
architecture of the system under consideration. The top-level
structure however is still sequential or layered. Then this layered
system is transformed to a parallel or distributed system tailored to
the physical structure of the system by means of the communication
closed layers principle, originally introduced by Elrad and Francez,
which states that under some side conditions layered and parallel
systems are equivalent.  
  We use a new program composition operator, called layer composition. 
It's functional behavior is as if it were sequential composition, but
it allows parallelism between independent components. This allows to
formulate the communication closed layers principle as an algebraic
law. The foundation of the method are hierarchical graphs, which are
a hierarchically structured extension of partial order models. 
Hierarchical graphs are used both as a semantic model and to define
our process language in. Hierarchical graphs allow to model shared
memory algorithms, asynchronous and synchronous communication,
atomicity, and real-time.
  We apply the method of layered design to several examples, such as
the Two-Phase Commit protocol for distributed databases, a distributed
minimum-weight spanning tree algorithm, parts of caching algorithms, 
and algorithms computing distances in graphs. Also some small examples
concerning real-time are discussed.

  Copies of the thesis are available from the author on request:
E-mail: janssenw@cs.utwente.nl