Token allocation in distributed systems

Abstract

Allocation and reallocation techniques for resources in a distributed database (DDB) system are discussed. An abstract model of the DDB, which partitions data among a set of nodes in a network, is presented. Initial resource allocation and demand driven borrowing policies are investigated using the model. It is shown that a single token borrowing policy which attempts to correct the greatest waste of resources in the system, achieves a cost within several percent of the unachievable lower bound, and multiple token borrowing polices, which anticipate future need and keep the system balanced with respect to the remaining number of tokens, perform much better than those that only borrow the needed amount.