Browse Prior Art Database

A Decentralized Naming Facility

IP.com Disclosure Number: IPCOM000128292D
Original Publication Date: 1985-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 28 page(s) / 97K

Publishing Venue

Software Patent Institute

Related People

David R. Cheriton: AUTHOR [+4]

Abstract

A key component in distributed computer systems is the naming facility: the means by which high- level names are bound to objects and by which objects are located given only their names. We describe the design, implementation, and performance of a decentralized naming facility, in which the global name space and name mapping mechanism are implemented by a set of cooperating peers, with no central authority. Decentralization is shown to lend increased extensibility and reliability to the design. Efficiency in name mapping is achieved through specialized caching techniques. Categories and Subject Descriptors: C.2.4 [Computer Systems Organization]: Distributed Systems; D.4.3 [Operating Systems]: File Systems Management- directory structures, distributed file systerns; D.4.7 [Operating Systems]: Organization and Design. General Terms: Design, experimentation, measurement, performance, reliability Additional Key Words and Phrases: Naming, distributed system, fault tolerance, cache Authors' address: Computer Science Department, Stanford University, Stanford, CA 94305

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 3% of the total text.

Page 1 of 28

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

A Decentralized Naming Facility

David R. Cheriton, Timothy P. Mann Computer Science Department Stanford University

February 1, 1986

Abstract

A key component in distributed computer systems is the naming facility: the means by which high- level names are bound to objects and by which objects are located given only their names. We describe the design, implementation, and performance of a decentralized naming facility, in which the global name space and name mapping mechanism are implemented by a set of cooperating peers, with no central authority. Decentralization is shown to lend increased extensibility and reliability to the design. Efficiency in name mapping is achieved through specialized caching techniques.

Categories and Subject Descriptors: C.2.4 [Computer Systems Organization]: Distributed Systems; D.4.3 [Operating Systems]: File Systems Management- directory structures, distributed file systerns; D.4.7 [Operating Systems]: Organization and Design.

General Terms: Design, experimentation, measurement, performance, reliability

Additional Key Words and Phrases: Naming, distributed system, fault tolerance, cache

Authors' address: Computer Science Department, Stanford University, Stanford, CA 94305

This work was supported by the Defense Advanced Research Projects Agency under contracts MDA903-80-C-0102 and N00039-83-K-0431, and by the IBM Corporation under a Graduate Fellowship.

I Introduction

A key component in distributed computer systems is the naming facility: the means by which global, high-level names are bound to objects and by which objects are located given only their names. High-level names are user-assigned character-string names, such as file names, user account names, mailbox names, host names, and service names. These names are distinguished from system-assigned low-level identifiers such as process identifiers and open file. handles. A global naming facility provides names for objects in the system that can be passed between clients without change in interpretation, often referred to as absolute names. In this paper, we. present a decentralized approach to naming, using the paradigm of problem- oriented shared memory [4]. Conceptually, a global naming facility can be realized as a single global directory that records all bindings between global names and objects. This directory can be viewed as a shared memory that is accessed by all nodes in the distributed system. In our design, the global directory is partitioned across multiple servers and accessed by multiple clients connected to a network, analogous to multiple memory boards and multiple processors connected to a backplane. Each client maintains a cache of names to reduce network traffic, with a cache miss producing a broadcast or multicast to the participating servers. Various

Stanford University Page 1 Dec 31, 1985

Page 2 of 28

A Decentralized Naming Facility

aspects of the design, particularl...