xerox CSL-81-8 Information Storage in a Decentralized Computer System free download

File name CSL-81-8_Information_Storage_in_a_Decentralized_Computer_System.pdf

Information Storage in a Decentralized Computer System David K. Gifford Information Storage in a Decentralized Computer System by David K. Gifford CSL-81-8 June 1981; Revised March 1982 Abstract: See page x. This report is a slightly revised version of a dissertation submitted to the Department of Electrical Engineering and the Committee on Graduate Studies of Stanford University in partial fulfillment of the requirements for the degree of Doctor of Philosophy. CR categories: 4.33. 4.35. 3.73 Key words and phrases: file system, information storage, reference, transaction, location, replication, suite, representative, quorum, reconfiguration, protection, cryptographic sealing, key, seal, unseal. XEROX Xerox Corporation Palo Alto Research Centers 3333 Coyote Hill Road Palo Alto, California 94304 @ Copyright 1981, 1982 by David K. Gifford All Rights Reserved. Contents List of Figures vii List of Tables viii Preface ix Abstract x 1. Method and Principles 1 1.1 Introduction 1 1.2 Method 1 1.3 System Description 3 1.4 Background 4 1.5 Architectural Principles 6 1.6 Summary 7 2. Environment 8 2.1 Hardware Components 8 2.1.1 Processors 8 2.1.2 Communication 9 2.1.3 Storage Devices 9 2.2 Stable Storage 10 2.3 Unique Identifiers 11 2.4 Reliable Remote Evaluation 11 2.4.1 Model 11 2.4.2 Algorithm 13 2.5 Summary 20 3. Transactional Storage 21 3.1 Model 21 3.1.1 References 21 3.1.2 Transactions 23 3.1.3 Volumes 26 3.1.4 Files 27 3.1.5 Mutable and Immutable Objects 28 3.2 Basic Algorithms 29 3.2.1 Single Processor Case 29 3.2.2 Decentralized Case 30 3.2.3 Reed's Algorithm 31 3.2.4 Located References 32 3.3 Refinements 35 3.3.1 Lock Compatibility 35 3.3.2 Lock Granularity 36 3.3.3 Lower ,Degrees of Consistency 36 3.3.4 Broken Read Locks 37 3.3.5 Releasing Read Locks 37 3.3.6 Deadlock 37 iii 3.3.7 Checkpoints and Save Points 38 3.3.8 Nested Transactions 38 3.3.9 Stable Storage Failure 38 3.4 Summary 38 4. Location 40 4.1 Indexes 40 4.2 Indirection 41 4.2.1 Model 41 4.2.2 Basic Algorithm 41 4.3 Indirect References 43 4.4 Object Location 46 4.5 Choice References 46 4.6 Summary 48 5. Replica