Muutke küpsiste eelistusi

Consistent Distributed Storage [Pehme köide]

, ,
Teised raamatud teemal:
Consistent Distributed StorageSuurem pilt
Teised raamatud teemal:
Püsilink: https://www.kriso.ee/db/9781636390628.html

This is a presentation of several approaches for employing shared memory abstraction in distributed systems, a powerful tool for simplifying the design and implementation of software systems for networked platforms.

These approaches enable system designers to work with abstract readable and writable objects without the need to deal with the complexity and dynamism of the underlying platform. The key property of shared memory implementations is the consistency guarantee that it provides under concurrent access to the shared objects. The most intuitive memory consistency model is atomicity because of its equivalence with a memory system where accesses occur serially, one at a time. Emulations of shared atomic memory in distributed systems is an active area of research and development. The problem proves to be challenging, and especially so in distributed message passing settings with unreliable components, as is often the case in networked systems. Several examples are provided for implementing shared memory services with the help of replication on top of message-passing distributed platforms subject to a variety of perturbations in the computing medium.

Acknowledgments xi
Outline xiii
1 Introduction
1(6)
1.1 Shared Storage: A Landscape
1(2)
1.2 Distribution and Consistency
3(4)
2 Model of Computation
7(12)
2.1 Distributed System
7(6)
2.1.1 Input/Output Automata and Executions
7(2)
2.1.2 Failures
9(1)
2.1.3 Communication
10(1)
2.1.4 Quorum Systems
11(2)
2.2 Consistency: Atomic Object Semantics
13(3)
2.3 Notation Summary
16(1)
2.4 Bibliographic Notes
17(2)
3 The Static Environment
19(4)
3.1 Replication
19(1)
3.2 Communication and Rounds
19(1)
3.3 Efficiency Measures
20(1)
3.4 List of Symbols
21(2)
4 The Single-Writer Setting
23(24)
4.1 SWMR Algorithm ABD: Basic Techniques
23(7)
4.1.1 Algorithm ABD Specification
24(1)
4.1.2 Algorithm ABD Correctness
25(4)
4.1.3 Efficiency of Algorithm ABD
29(1)
4.2 Algorithm Fast: Expediting Read Operations
30(7)
4.2.1 Algorithm Fast Specification
30(4)
4.2.2 Algorithm Fast Correctness
34(3)
4.3 Lower Bound: Limitations of Fast Implementations
37(1)
4.4 Algorithm SLIQ: Introducing Quorum Views
38(7)
4.4.1 Algorithmic Technique: Quorum Views
39(1)
4.4.2 Algorithm SLIQ Specification
40(4)
4.4.3 Algorithm SLIQ Correctness
44(1)
4.5 Bibliographic Notes
45(2)
5 The Multiple-Writer Setting
47(32)
5.1 Algorithm MWABD: Multi-Writer ABD
47(4)
5.1.1 Algorithm MWABD Specification
47(2)
5.1.2 Algorithm MWABD Correctness
49(2)
5.2 Algorithm CWFR: Quorum View Generalization
51(9)
5.2.1 Algorithmic Technique: MW Quorum Views
51(1)
5.2.2 Algorithm CWFR Specification
52(5)
5.2.3 Algorithm CWFR Correctness
57(3)
5.3 Lower Bound: Inherent Limitations of MWMR on Fast Operations
60(6)
5.4 Algorithm SFW: Expediting Write Operations
66(11)
5.4.1 Algorithmic Technique: Server Side Ordering (SSO)
67(1)
5.4.2 Algorithmic Technique: Enhanced Tagging
68(1)
5.4.3 Algorithm SFW Specification
69(4)
5.4.4 Algorithm SFW Correctness
73(4)
5.5 Bibliographic Notes
77(2)
6 The Dynamic Environment
79(4)
6.1 Consensus
80(1)
6.2 Group Communication Services
81(1)
6.3 Using Reconfiguration for Direct Implementations
82(1)
7 RAMBO: Reconfigurable Dynamic Memory
83(32)
7.1 Models and Definitions
84(2)
7.2 Rambo Service Specifications
86(5)
7.2.1 Rambo Service Specification
86(2)
7.2.2 Recon Service Specification
88(3)
7.3 Implementation of Rambo
91(11)
7.3.1 Overall Architecture
92(1)
7.3.2 Implementation of Joiner
92(1)
7.3.3 Implementation of Reader-Writer
92(8)
7.3.4 Implementation of the Recon Service
100(2)
7.3.5 The Complete Rambo Algorithm
102(1)
7.4 Atomicity of Rambo
102(3)
7.5 Conditional Performance Analysis: Latency Bounds
105(3)
7.6 Extensions of Rambo
108(3)
7.7 GeoQuorums--Adaptation of Rambo for Mobile Settings
111(2)
7.8 Bibliographic Notes
113(2)
8 RDS: Integrated Reconfigurations
115(20)
8.1 Preliminaries
115(1)
8.2 The Paxos Consensus Algorithm
116(3)
8.2.1 Tie Part-Time Parliament
116(1)
8.2.2 Fast Paxos
117(1)
8.2.3 Deciding Upon a New Configuration
118(1)
8.3 Reconfigurable Distributed Storage
119(9)
8.3.1 Signature and State
119(2)
8.3.2 Read and Write Operations
121(1)
8.3.3 Communication and Independent Transitions
122(3)
8.3.4 Reconfiguration
125(3)
8.4 Consensus of RDS
128(1)
8.5 Conditional Performance Analysis
129(2)
8.6 Bibliographic Notes
131(4)
9 DynaStore: Incremental Reconfigurations
135(20)
9.1 Preliminaries
136(2)
9.1.1 Incremental Reconfiguration
137(1)
9.1.2 Activity of Processes
137(1)
9.1.3 Majority Assumption
138(1)
9.2 The Weak Snapshot Automaton
138(4)
9.3 Tie Reader-Writer-Recon Automaton
142(5)
9.3.1 Partially Ordered Configurations
144(1)
9.3.2 Adding New Configurations
145(1)
9.3.3 Contacting Quorums
146(1)
9.4 Correctness
147(5)
9.5 Implementation and Performance Considerations
152(2)
9.6 Bibliographic Notes
154(1)
10 Concluding Remarks and Looking Ahead
155(4)
Bibliography 159(12)
Authors' Biographies 171(2)
Index 173
Vincent Gramoli is a Future Fellow of the Australian Research Council at the University of Sydney, Australia and a Visiting Professor at EPFL, Switzerland. Vincent started his research on the topic of reconfigurable atomic memory while visiting the University of Connecticut and MIT (USA). He then worked in the area of large-scale distributed systems at INRIA (France) and on the slicing problem at Cornell University (USA). He moved to the University of Neuchâtel and EPFL (Switzerland), where he contributed to the development of the Transactional Memory stack. He obtained his Ph.D. from Université de Rennes and his Habilitation from Sorbonne University. His interest lies in the security and fault tolerance of distributed computing.

Nicolas Nicolaou is a co-founder and a senior scientist and algorithms engineer at Algolysis Ltd. He held various academic positions as a visiting faculty until 2014, as an IEF Marie Curie Fellow at IMDEA Networks Institute (2014-2016), a shortterm scholar at MIT (2017), and a PostDoc Researcher at the KIOS Research Center of Excellence (2017-2019) before departing for an industrial position in 2019. He holds a Ph.D. (2011) and a M.Sc. (2006) from the University of Connecticut and a B.Sc. (2003) from the University of Cyprus. His main research interests lie in the areas of distributed systems, design and analysis of fault-tolerant distributed algorithms, distributed ledgers (blockchains), security for embedded devices and critical infrastructures, and sensor networks.

Alexander A. Schwarzmann is the Dean of the School of Computer and Cyber Sciences at Augusta University in Georgia, USA. He holds a Ph.D. from Brown University (1992), M.S. from Cornell University (1981), and a B.S. from Stevens Institute of Technology (1979), all in Computer Science, and he did his post-doctoral work at MIT (USA). Previously, he worked at Bell Labs, Digital Equipment Corp., and the University of Connecticut, where he was the Head of Computer Science & Engineering, and the Founding Director of the Center for Voting Technology Research. His professional interests are in Distributed Computing, Fault-tolerance, and Security and Integrity of Electronic Voting Systems. He authored over 150 technical articles, 3 books, and 1 patent. He is also a Vigneron d'Honneur of Jurade de Saint-Emilion.