  An Abstract Graph Machine(AGM) is an abstract model for distributed memory
parallel stabilizing graph algorithms. A stabilizing algorithm starts from a
particular initial state and goes through series of different state changes
until it converges. The AGM adds work dependency to the stabilizing algorithm.
The work is processed within the processing function. All processes in the
system execute the same processing function. Before feeding work into the
processing function, work is ordered using a strict weak ordering relation. The
strict weak ordering relation divides work into equivalence classes, hence work
within a single equivalence class can be processed in parallel, but work in
different equivalence classes must be executed in the order they appear in
equivalence classes. The paper presents the AGM model, semantics and AGM models
for several existing distributed memory parallel graph algorithms.
