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