Title: Deterministic Computations Whose Hisrtory is Independent of
the Order of Updating
Author: Peter Gacs
Date: November 18, 1995
Abstract:
Consider a network of processors (sites) in which each site has
finitely many neighbors. Each site has some transition function
computing its next state from the states of the neighbors. These
transitions (updates) are applied in arbitrary order, one or many at a
time.
If the state of site x at time t is r(x,t) then let us define the
sequence r'(x,0),r'(x,1),... by taking the sequence
r(x,0),r(x,1),... and deleting each repetition, i.e. each element
equal to the preceding one.
The system of transition functions is said to support asynchrony if
the sequence r'(x,i), (while it lasts, in case it is finite) depends
only on the initial configuration, not on the order of updates.
This paper gives a simple characterization of transition functions
supporting asynchrony. The characterization says that it is
equivalent to the following seemingly weaker commutativity condition:
For any configuration, for any pair x,y of neighbors, if the updating
would change both s(x) and s(y) then the result of updating first x
and then y is be the same as the result of doing this in the reverse
order.