Towards a paradigm for robust distributed algorithms and data structures
Christian Scheideler · 2006
There is a wealth of literature on distributed algorithms and data structures. Standard models used in the research community are synchronous or asynchronous shared memory or network models. The shared memory model is basically a generalization of the von Neumann model from one processing unit to multiple processing units or processes acting on a single, linear addressable memory. In the network model, there is no shared memory. Every processing unit has its own, private memory, and the processing units are connected by a network of (usually) bidirectional communication links that allow the processing units to exchange messages. The set of processing units is usually considered to be fixed though processing units may fail and recover according to some stochastic or adversarial model. With the rise of very large distributed systems such as peer-to-peer systems, these models are not appropriate any more. For example, the set of processing units can be highly dynamic and there may not be any mutual trust relationships between the units. This creates fundamental problems, such as keeping the (honest) units in a single connected component, that the previous models cannot address in their basic form. We show how to extend the network model so that we have a model that is powerful enough to design algorithms and data structures that are provably robust even against massive adversarial