125 citations · 284 across the 20 of their papers we have counts for
Showing 2001Show all
3 papers · 1 filter
math.PR2001★ 4 cited
Clairvoyant scheduling of random walks
Peter Gacs
Two infinite walks on the same finite graph are called compatible if it is possible to introduce delays into them in such a way that they never collide. Years ago, Peter Winkler as…
math-ph2001★ 4 cited
A Toom rule that increases the thickness of sets
Peter Gacs
Toom's north-east-self voting cellular automaton rule R is known to suppress small minorities. A variant which we call R^+ is also known to turn an arbitrary initial configuration…
cs.DC2001★ 21 cited
Deterministic computations whose history is independent of the order of asynchronous updating
Peter Gacs
Consider 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)…