Frameworks Research

Systems research
1 / 39
0
0
794 days ago, 333 views
PowerPoint PPT Presentation
Frameworks Research. Barbara Liskov October 2007. Replication . Objective: give unwavering quality and accessibility by putting away data at a few hubs. Single Server. Server. Customers. Single Server. X. Server. Customers. Repeated Servers. X. Servers. Customers. Replication Issues .

Presentation Transcript

Slide 1

Frameworks Research Barbara Liskov October 2007

Slide 2

Replication Goal: give unwavering quality and accessibility by putting away data at a few hubs

Slide 3

Single Server Clients

Slide 4

Single Server X Server Clients

Slide 5

Replicated Servers X Servers Clients

Slide 6

Replication Issues Semantics What is being repeated Failure suppositions

Slide 7

Issue 1: Semantics One-duplicate consistency Or weaker Servers Clients

Slide 8

Issue 2: Type of Operations Only peruses and composes General operations acct.deposit($$); acct.withdraw($$$);

Slide 9

Replication conventions Data replication Quorums and voting Operations State machine replication System plays out an arrangement of operations

Slide 10

Issue 3: Failure Assumptions Network is offbeat Eventual conveyance Network is vindictive Corruption Replay Spoofing Handled through cryptography Nodes are failstop or Byzantine

Slide 11

Failstop Failures Nodes flop by smashing A machine is either working accurately or it is doing nothing! The suspicion made in the 1980s

Slide 12

Failstop disappointments Requires 2f+1 imitations Operations must cross no less than one copy as a rule need accessibility for both peruses and composes: f+1 hubs is adequate Read and compose majorities

Slide 13

Quorums State: State: State: … Servers X compose A compose A compose A Clients

Slide 14

Quorums State: State: State: … An A X Servers Clients

Slide 15

Quorums State: State: State: … An A X Servers X compose B compose B compose B Clients

Slide 16

Data Replication R.H. Thomas, A lion's share accord way to deal with simultaneousness control for different duplicate databases, ACM TODS, 1979 D.K. Gifford, Weighted voting in favor of repeated information, SOSP 1979 H. Attiya, A. Bar-Noy, and D. Dolev, Sharing memory vigorously in message-passing frameworks, JACM , Jan. 1995

Slide 17

Quorum Consensus Each information thing has a form number A grouping of qualities write(d, val, v#) Waits for f+1 oks read(d) returns (val, v#) Waits for f+1 coordinating v#'s Else does a compose back

Slide 18

State Machine Replication Replicas must execute operations in a similar request Implies copies will have a similar state, expecting reproductions begin in a similar state operations are deterministic

Slide 19

Failstop Replication Viewstamped replication: another essential duplicate technique to bolster profoundly accessible conveyed frameworks, B. Oki and B. Liskov, PODC 1988 Thesis, May 1988 Replication in the Harp record framework, S. Ghemawat et. al, SOSP 1991 The low maintenance parliament, L. Lamport, TOCS 1998 Paxos made straightforward, L. Lamport, Nov. 2001

Slide 20

Approach Use an essential It arranges the operations Other imitations comply with this request

Slide 21

Views System travels through a succession of perspectives Primary runs the convention Replicas watch the essential and do a view change on the off chance that it fizzles

Slide 22

Normal Case Client sends demand to essential Primary sends plan message

Slide 23

Normal Case Client sends demand to essential Primary sends get ready message Replicas get ready Send get ready alright message to the essential

Slide 24

Normal Case Client sends demand to essential Primary sends get ready message to all Replicas get ready Send get ready alright message to the essential Primary sits tight for f get ready oks Sends reaction to customer

Slide 25

Normal Case A 2-stage convention: Prepare; submit Only 3 message delays

Slide 26

Byzantine Failures Nodes bomb discretionarily They lie, they plot Causes Malicious assaults Non-deterministic programming blunders

Slide 27

Quorums 3f+1 copies are expected to survive f disappointments 2f+1 reproductions is a majority Insures convergence The base in an offbeat system

Slide 28

Quorums … State: State: State: State: An A Servers X compose A compose A compose A compose A Clients

Slide 29

Quorums … State: State: State: State: An A B Servers X compose B compose B compose B compose B Clients

Slide 30

BFT M. Castro and B. Liskov, Practical Byzantine broken resilience and proactive recuperation, ACM TOCS, 2002

Slide 31

Strategy Primary runs the convention in the ordinary case Replicas watch the essential and do a view change on the off chance that it falls flat Key distinction: imitations may lie Solution: include a pre-get ready stage

Slide 32

Normal Case Client sends demand to essential

Slide 33

Normal Case Client sends demand to essential Primary sends pre-get ready message to all

Slide 34

Normal Case Client sends demand to essential Primary sends pre-plan message to all Why not a get ready message? Since essential may be malignant

Slide 35

Normal Case Client sends demand to essential Primary sends pre-get ready message to all Replicas check the pre-get ready and on the off chance that it is alright: Send plan messages to all

Slide 36

Normal Case Replicas sit tight for 2f+1 coordinating gets ready Send submit message to all

Slide 37

Normal Case Replicas sit tight for 2f+1 coordinating gets ready Send confer message to all Replicas sit tight for 2f+1 coordinating confers Execute operation and send result to customer

Slide 38

Follow-on Work BASE: utilizing reflection to enhance adaptation to non-critical failure, R. Rodrigo et al, SOSP 2001 R.Kotla and M. Dahlin, High Throughput Byzantine Fault resilience. DSN 2004 J. Li and D. Mazieres, Beyond 33% defective reproductions in Byzantine blame tolerant frameworks, NSDI 07 Abd-El-Malek et al, Fault-versatile Byzantine blame tolerant administrations, SOSP 05 HQ replications: a cross breed majority convention for Byzantine Fault resistance, OSDI 06

Slide 39

Papers in SOSP 07 Monday 1:30-3:30 Zyzzyva: Speculative Byzantine adaptation to internal failure Tolerating Byzantine blames in database frameworks utilizing submit boundary planning Low-overhead Byzantine blame tolerant stockpiling Attested annex just memory: making enemies adhere to their statement Tuesday: 11:00-12:00 PeerReview: down to earth responsibility for dispersed frameworks

SPONSORS