We consider the problem of a rendezvous of distributed units. The environment is modeled as a graph, the node labeling of which may not be "common knowledge" to the units, due to protocol and naming convention mismatch, machine faults, status change, or even hostility fo the environment. meeting of such units is likely to be a basic procedure in the area of distributed"intelligent agent" computing and in the domain of coordinated tasks of autonoumous robots. The crux of the problem which we present here and initiate research on, is the breaking of potential symmetry while the units dynamically move. The units are more intelligent than simple pebbles or tokens, nad our algorithms iwll make use of this capability for speeding up the convergence to a common place. We consider both randomized protocols and deterministic protocols; the problem is unsolvable by a uniform deeterministic algorithm. The deterministic procedure employs ideas from design theory and achieves O(n) time, while the randomized methods are based on random walks and may achieve O(n/k) time where k is the number of agents.
展开▼
