Distributed Data Structures: a Case Study

In spite of the amount of work recently devoted to distributed systems, distributed applications are relatively rare. One hypothesis to explain this scarcity of different examples is a lack of experience with algorithm design techniques tailored to an environment in which out-of-date and incomplete information is the rule. Since the design of data structures is an important aspect of traditional algorithm design, we feel that it is important to consider the problem of distributing data structures. In this paper, we investigate these issues by developing a distributed version of an extendible hash file which is a dynamic indexing structure that could be useful in a distributed database