Scalable accessibility of a recoverable database using wandering tokens

In a large distributed system there is usually the need to keep a
record of the state of the components: one example is the database of
the resources available in a Grid. The design of such database should
take into account that the size of the system is not constant, and may
vary of orders of magnitude: manual intervention to reconfigure the
system in order to meet accessibility requirements may be problematic,
and a source of unreliability.

We present a scheme that provides scalable accessibility to such a
database, focussing on the performance of update operations. The
scalable implementation of update operations enables ubiquitous
replication of the database, thus bringing at reach the scalability of
read operations. Each component of the system regulates automatically
the relevant operational parameters with a kind of feedback, which is
based on probabilistic considerations. Many aspect of the scheme are
in fact probabilistic, and we introduce a simple model that describes
the performance of the system.

The overall approach as well as certain performance figures that
cannot be forecast analitically, are explored with simulation.