Service Manuals, User Guides, Schematic Diagrams or docs for : xerox parc techReports CSL-81-8_Information_Storage_in_a_Decentralized_Computer_System
<< Back | HomeMost service manuals and schematics are PDF files, so You will need Adobre Acrobat Reader to view : Acrobat Download Some of the files are DjVu format. Readers and resources available here : DjVu Resources
For the compressed files, most common are zip and rar. Please, extract files with Your favorite compression software ( WinZip, WinRAR ... ) before viewing. If a document has multiple parts, You should download all, before extracting.
Good luck. Repair on Your own risk. Make sure You know what You are doing.
Image preview - the first page of the document
>> Download CSL-81-8_Information_Storage_in_a_Decentralized_Computer_System documenatation <<
Text preview - extract from the document
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. Replication 49
5.1 Suites 49
5.2 Basic Algorithm 52
5.3 Correctness Argument 61
5.4 Refinements 62
5.4.1 Weak Representatives 62
5.4.2 Lower Degrees of Consistency 62
5.4.3 Representative Performance 62
5.4.4 Expressive Power of Suites 62
5.4.5 Size of Replicated Objects 62
5.4.6 Total Replacement 63
5.4.7 Simultaneous Suite Update 63
5.4.8 Releasing Read Locks 63
5.4.9 Updating Representatives in Background 63
5.4.10 Guessing a Representative is Current 63
5.4.11 Postponed Creation of File Representatives 63
5.4.12 An Alternative for Replicated Volumes 64
5.5 Related Work 64
5.6 Summary 64
6. Reconfiguration 65
6.1 Reconfigurable Objects 65
6.2 Basic Algorithm 66
6.3 Refinements 74
6.3.1 Reducing Data Movement 74
6.3.2 Eliminating the Volume Index 74
6.4 Summary 75
iv
7. Protection 76
7.1 Preliminaries 77
7.1.1 Framework 77
7.1.2 Environment 77
7.1.2.1 Cryptography 77
7.1.2.2 Threshold Scheme 81
7.1.2.3 Checksums 82
7.2 Cryptographic Sealing 82
7.2.1 Model 82
7.2.2 Basic Algorithm 85
7.2.3 Strength 93
7.2.3.1 Correctness Argument 93
7.2.3.2 Susceptibility to Cryptanalysis 95
7.3 Applications 97
7.3.1 Privilege Establishment 97
7.3.1.1 Key Rings 97
7.3.1.2 Encrypted Objects 97
7.3.1.3 Guarded Objects 98
7.3.1.4 Protected Volumes 99
7.3.2 Common Protection Mechanisms 100
7.3.2.1 Capabilities 100
7.3.2.2 Access Control Lists 102
7.3.2.3 Information Flow Control 102
7.3.3 Secure Processors 104
7.3.3.1 Limiting Remote Evaluation 104
7.3.3.2 Secure Channels 105
7.3.4 Revocation 107
7.3.4.1 Protected Indirection 109
7.3.4.2 Revocation Algorithm 109
7.4 Practical Considerations III
7.4.1 Changing Protection Controls III
7.4.2 Authentication in the Large 112
7.4.3 Performance 112
7.4.4 Comments 113
7.4.5 Elimination of Authentication 113
7.5 Comparative Analysis 113
7.6 Summary 114
8. Practical Considerations 115
8.1 Implementation 115
8.1.1 Prototypes 115
8.1.2 Full-Scale Implementations 116
8.2 Configuration 116
8.2.1 Static Configuration 116
8.2.2 Dynamic Configuration 120
8.3 Summary 120
v
9. Summary of Ideas 121
Appendix A: Exposition Language: EL 123
A.l Language Extensions 123
A.2 Classes 123
A.3 Records 125
AA External Representation 127
A.5 Exception Handling 127
A.6 Processes 128
A.7 Synchronization 128
A.8 Sets 128
A.9 Byte Arrays 129
A.I0 Miscellaneous 129
Appendix B: Storage System Summary 130
Appendix C: The Open Function 133
Bibliography 134
Index 138
vi
Figures
Figure 2.1 - Structure of a Processor Class 18
Figure 3.1- Structure ofa Located Class 34
Figure 4.1 - An Indirect Record 42
Figure 4.2 - Structure of an Indirect Class 45
Figure 5.1 - Structure of a Suite Class 54
Figure 6.1 - Structure of a Reconfigurable File or Index 67
Figure 6.2 - Structure ofa Reconfigurable Volume 68
Figure 6.3 - File and Index Reconfiguration Algorithm 70
Figure 6.4 - Step 1 of Volume Reconfiguration: Move Files 71
Figure 6.5 - Step 2 of Volume Reconfiguration: Move File Index 72
Figure 6.6 - Step 3 of Volume Reconfiguration: Change Volume Pointer 73
Figure 7.1- A Passive Protection Mechanism 78
Figure 7.2 - An Active Protection Mechanism 79
Figure 7.3 - Example Sealed Objects 87
Figure 7.4 - Protection System Internal Structure 88
Figure 7.5 - Capability Reference 101
Figure 7.6 - Object Reference: Access Control List 103
Figure 7.7 - Structure of a Secure Located Class 108
Figure 7.8 - A Revocable Capability 110
Figure 8.1 - A Basic Storage Service 117
Figure 8.2 - Client Defined Protected Volumes 118
vii
Tables
Table 3.1 - Typical Lock Compatibility Matrix 35
Table 3.2 - Lock Compatibility Matrix with Intention Locks 36
Table 5.1 - Sample Suite Configurations 51
viii
Preface
This paper is organized so that it can be used in several ways. It can of course be read in its
entirety for a treatment of the general problem of decentralized information storage. It is also
possible to read an isolated chapter for a treatment of a single topic, such as protection. Each
chapter begins with an outline of its organization and ends with a summary of its contents. If the
reader wishes to look at a chapter in isolation I would also suggest that they read Sections 1.3 and
3.1.
There is a comprehensive index at the end of the paper. The index is useful to locate
references to a specific concept It also indexes the program text, and thus should help a reader
find the definition of a function or a type.
I have tried to present enough detail so a reader can easily implement the ideas I discuss.
However, it is possible to understand the essence of the ideas without reading program text On a
first reading, a casual reader should probably skip sections titled implementation or refinement
I would like to thank my patient advisers, Dr. Butler Lampson and Prof. Susan Owicki, for
their help and good advice over the past four years. In addition to my advisers, Peter Deutsch,
Jim Gray, Martin Haeberli, Prof. Larry Manning, Gene McDaniel, Alfred Spector, Larry Stewart,
and Howard Sturgis took the time to carefully read chapters of this paper and suggest
improvements. I would also like to thank Bob Taylor for making it possible for me to do this work
at the Xerox Palo Alto Research Center. The work benefited greatly from daily interactions with
colleagues at Xerox.
The Fannie and John Hertz Fellowship that I held while a graduate student gave me the
freedom to pursue this research. The research was supported in part by the Fannie and John Hertz
Foundation, and by the Xerox Corporation.
This work is dedicated to my parents.
ix
Abstract
This paper describes an architecture for shared information storage in a decentralized computer
system. The issues that are addressed include: naming of files and other objects (naming), reliable
storage of data (stable storage), coordinated access to shared storage (transa~tional storage), location
of objects (location), use of multiple copies to increase performance, reliability and availability
(replication), dynamic modification of object representations (reconfiguration), and storage security
and authentication (protection).
A complete model of the architecture is presented, which describes the interface to the facilities
provided, and describes in detail the proposed mechanisms for implementing them. The model
presents new approaches to naming, location, replication, reconfiguration, and protection. To verify
the model, three prototypes were constructed, and experience with these prototypes is discussed.
The model names objects with variable length byte arrays called references. References may
contain location information, protection guards, cryptographic keys, and other references. In
addition, references can be made indirect to delay their binding to a specific object or location.
The replication mechanism is based on assigning votes to each copy of a replicated object. The
characteristics of a replicated object can be chosen from a range of possibilities by appropriately
choosing its voting configuration. Temporary copies can be easily implemented by introducing
copies with no votes.
The reconfiguration mechanism allows the storage that is used to implement an object to
change while the system is operating. A client need not be aware that an object has been
reconfigured.
The protection mechanism is based on the idea of sealing an object with a key. Sealed objects
can only be unsealed with an appropriate set of keys. Complex◦ Jabse Service Manual Search 2024 ◦ Jabse Pravopis ◦ onTap.bg ◦ Other service manual resources online : Fixya ◦ eServiceinfo