Show simple item record

dc.contributor.authorGacs, Peteren_US
dc.date.accessioned2011-10-20T04:32:21Z
dc.date.available2011-10-20T04:32:21Z
dc.date.issued1995-11-18en_US
dc.identifier.citationGacs, Peter. "Deterministic Computations Whose History is Independent of the Order of Updating“, Technical Report BUCS-1995-018, Computer Science Department, Boston University, November 18, 1995. [Available from: http://hdl.handle.net/2144/1577]en_US
dc.identifier.urihttp://hdl.handle.net/2144/1577
dc.description.abstractConsider a network of processors (sites) in which each site x has a finite set N(x) of neighbors. There is a transition function f that for each site x computes the next state ξ(x) from the states in N(x). But these transitions (updates) are applied in arbitrary order, one or many at a time. If the state of site x at time t is η(x; t) then let us define the sequence ζ(x; 0); ζ(x; 1), ... by taking the sequence η(x; 0),η(x; 1), ... , and deleting each repetition, i.e. each element equal to the preceding one. The function f is said to have invariant histories if the sequence ζ(x; i), (while it lasts, in case it is finite) depends only on the initial configuration, not on the order of updates. This paper shows that though the invariant history property is typically undecidable, there is a useful simple sufficient condition, called commutativity: For any configuration, for any pair x; y of neighbors, if the updating would change both ξ(x) and ξ(y) then the result of updating first x and then y is the same as the result of doing this in the reverse order. This fact is derivable from known results on the confluence of term-rewriting systems but the self-contained proof given here may be justifiable.en_US
dc.description.sponsorshipNational Science Foundation (CCR-920484)en_US
dc.language.isoen_USen_US
dc.publisherBoston University Computer Science Departmenten_US
dc.relation.ispartofseriesBUCS Technical Reports;BUCS-TR-1995-018en_US
dc.titleDeterministic Computations Whose History Is Independent of the Order of Asynchronous Updatingen_US
dc.typeTechnical Reporten_US


Files in this item

This item appears in the following Collection(s)

Show simple item record