PROPAGATOR - A Family of Patterns

Peter H. Feiler
Software Engineering Institute
Carnegie-Mellon University
Pittsburgh, PA 15232

Walter  F. Tichy
University of Karlsruhe
D-76128 Karlsruhe, Germany

Contact:
Walter  F. Tichy
University of Karlsruhe
D-76128 Karlsruhe
Germany

Net: tichy@ira.uka.de
Tel: +49 721 608-3934
Fax: +49 721 69 40 92


Abstract 

Propagator is a family of patterns for consistently updating objects in
a dependency network. The propagator patterns are found in such diverse
applications as Make, WWW, spreadsheets, GUIs, distributed file systems,
distributed databases, workflow systems, and multilevel caches.

There are four main patterns: Strict Propagator, Strict Propagator With
Failure, Lazy Propagator, and Adaptive Propagator. In the strict
propagation patterns, updates flow from the point of original change
forward through the network. Dependent objects are immediately updated,
unless failure occurs. In the lazy propagation pattern, an updated
object merely sets its timestamp, without notifying any other object.
Upon request, a dependent object makes itself current after requesting
predecessor objects to bring themselves up-to-date. The adaptive
propagator separates propagation of out-of-date markers from the actual
update. It supports a combination of strict, lazy, and periodic update
schemes.
 
All patterns support smart propagation for avoiding redundant work as
well as concurrent updates. Examples of these patterns are formulated 
in the Internet language Java.