A model for distributed systems based on graph rewriting

A model for distributed systems based on graph rewriting
P. Degano and U. Montanari
J ACM 34(2):411-449

I was pointed to this paper by Eric Griffis, a student who will be visiting this summer as part of a NSF PIRE program.  Eric is interested in graph rewriting and distributed systems.

The paper presents a generic computational model for concurrent/distributed computation based on graphs (really, hypergraphs).  The "nodes" of the hypergraphs correspond to channels, and the "hyperedges" correspond to either events (interactions in the past) or processes (placeholders for possible interactions in the future).  Thus, the graph as a whole describes both the past (previous events), present (frontier of active processes that can make progress now) and future (processes whose progress is blocked by other processes).

The execution behavior of the system can be specified using graph rewriting.  Production rules are specified as mappings from nonterminal labels to graph fragments.  Rewrite rules are obtained from these by merging concurrent events.  The meaning of a system (that possibly runs forever) is defined by setting up a ultrametric space on graph states and taking limits.  (This is a large oversimplification.)
Read more »