This paper proposes a methodology for designing a class of
algorithms for computing functions in dynamic distributed systems
in which communication channels and processes may cease
functioning temporarily or permanently. Communication and
computing may be interrupted by an adversary or by environmental
factors such as noise and power loss. The set of processes may be
partitioned into subsets that cannot communicate with each other;
algorithms in which all such subsets behave in a similar fashion,
regardless of size and identities of processes, are called
self-similar algorithms. Algorithms adapt to changing conditions,
speeding up or slowing down depending on the resources available.
The paper presents necessary and sufficient conditions for the
application of a self-similar strategy. Self-similar algorithms
are developed for several problems by applying the methodology.
Michel Charpentier <>
Last modified: Tue Sep 27 11:58:14 EDT 2005