Decentralized object finding using forwarding addresses (object, network, distribution)

A problem that must be solved in designing a large distributed computing system is ensuring that processors can "find" all of the "objects" that they have the right to access. To avoid the potential reliability problems and bottlenecks that can be introduced by centralized services it is desirable that object finding be decentralized and allow any group of processors to proceed independently and autonomously. Given a model of a decentralized system in which objects are analogous to moveable physical objects and in which access rights are carried only by proper names, we examine in detail the implications of using forwarding addresses for finding objects. Special emphasis is placed on the issues of performance, active resource management, and high availability through distribution. We analyze the cost of using each of several object finding protocols based on forwarding addresses, deriving ammortized worst case upper and lower bounds as well as estimates for the average case. The average case costs of two simple protocols are analyzed using Markov chains, revealing that the mean cost per access is order of the square root of N, where N is the number of distinct processors that an object visits. The worst case costs of a path compressing protocol are determined to be order of log N. If the object is accessed a times and moves m times, then all cost estimates are decreasing functions of a/m. We provide a detailed specification of a possible implementation of the PCacc protocol. One extension of the basic implementation involves the addition of a mechanism called an inexact reference set. This extension enables a processor to actively manage its resources, both enabling it to reclaim the storage occupied by forwarding addresses and to control the use of storage occupied by objects. Another extension that we describe is that of allowing forwarding addresses to point to the multiple processors that host distributed objects. We show that this extension ensures enhanced accessibility in the presence of processor faults.