FREE ELECTRONIC LIBRARY - Abstracts, online materials

Pages:     | 1 |   ...   | 8 | 9 || 11 | 12 |   ...   | 18 |

«Efficient, scalable consistency for highly fault-tolerant storage GARTH GOODSON August 2004 CMU-CS-04-111 Dept. of Electrical and Computer ...»

-- [ Page 10 ] --

fication over the new object history set, line 416. This is necessary, since barrier-writes may be executed at storage-nodes hosting the CW operation that they are trying to block (i.e., an incomplete operation may complete just prior to the execution of the barrier). If classification yields the same candidate (cf. line 417), the client can perform the valuewrite. And, if the value-write completes, then the Candidate is returned (in case the CW operation is called for repair). If either the barrier-write or value-write do not complete, then the CW operation aborts, and must be retried (including the read phase). Figure 4.6 shows an example of a barrier-write that necessitates re-classification.

4.3.3 CW requests at storage-nodes Receiving CW requests

–  –  –

RECEIVE WRITE REQUEST(LT, LT conditioned, ObjectHistorySet, Data) :

600: if (VALIDATE CW REQ(LT, LT conditioned, ObjectHistorySet, Data)) then 601: /∗ Execute the CW request ∗/ 602: Request := LT, LT conditioned, Data 603: ReplicaHistory := ReplicaHistory ∪ Request 604: /∗ Prune history ∗/ 605: if (Data = ⊥) then 606: PRUNE HISTORY SET(ReplicaHistory, LT conditioned ) 607: end if 608: SEND(WRITE RESPONSE, S, ReplicaHistory, SUCCESS) 609: return 610: end if 611: SEND(WRITE RESPONSE, S, ReplicaHistory, FAIL) 612: return

Figure 4.7: Reception of a CW at storage-node S.

into the storage-node’s local history, line 603. The request is comprised of the tuple:

LT, LT conditioned, Data.

If an object history set contains a complete candidate, the storage-node can prune its replica history up to the complete candidate’s timestamp (cf. line 606). A validated object history set always contains a candidate that is complete (although such a candidate may be earlier in the object history set than a repairable candidate returned from classification); note, the initial timestamp 0 can be considered the earliest complete candidate. All versions prior to the latest complete (non-barrier) CW (i.e., prior to the CW’s LT conditioned ) can be pruned; however, no pruning occurs on barrier-writes. The use of authenticators obviates the need for distributed garbage collection as was necessary in the RW protocol.

Finally, a response is sent back to the client. Note that the storage-node’s local history is always transmitted in the response. This allows the client to update the object history set and re-perform classification if necessary (e.g., if the CW operation failed).

Validating CW requests

Storage-nodes must validate CW requests. If validation succeeds, the storage-node executes the CW request: it executes the value-write and updates its replica history to include the CW request. Remember, the replica history is stored in stable storage that endures the crash-recovery cycle. If validation fails, the storage-node rejects the CW request.

With the object history set, the storage-node can perform the exact same logic as the · 72 Efficient, scalable consistency for highly fault-tolerant storage

VALIDATE CW REQ(LT, LT conditioned, ObjectHistorySet, Data) :

700: /∗ Validate LT.Time, ensures logical time is always increasing ∗/ 701: if (LT.Time = ((MAX TIMESTAMP[ObjectHistorySet]).Time + 1)) then 702: return (FAIL) 703: end if 704: /∗ Validate authenticators for each history set ∗/ 705: if (VALIDATE AUTHENTICATORS(ObjectHistorySet) = FAIL) then 706: return (FAIL) 707: end if 708: /∗ Validate verifiers ∗/ 709: if (HASH(Data) = LT.Verifier Data) then 710: return (FAIL) 711: else if (HASH(ObjectHistorySet) = LT.Verifier OHS) then 712: return (FAIL) 713: end if 714:

715: /∗ Perform classification to find latest logical timestamps ∗/ 716: LTlatest comp nb, LTlatest comp nb bd, LTlatest nb, LTlatest barrier, LTlatest ni nb, Classifylatest barrier := CLASSIFY(ObjectHistorySet) 717:

718: /∗ Check if a barrier is needed, and not writing a barrier ∗/ 719: if ((LTlatest comp nb bd = LTlatest nb ) AND ((LTlatest barrier LTlatest nb ) OR (Classifylatest barrier = COMPLETE)) then 720: /∗ Barrier is needed, make sure this is a barrier ∗/ 721: if (LT.Barrier = FALSE) then 722: return (FAIL) 723: end if 724: else if (LT.Barrier = TRUE) then 725: return (FAIL) 726: end if 727:

728: /∗ Validate replica acceptance policy ∗/ 729: if (MAX[ReplicaHistory] MAX[LTlatest nb, LTlatest barrier ]) then 730: return (FAIL) 731: end if 732:

733: if (LT.Barrier = FALSE) then 734: /∗ Validate condition on relationship, conditioning on a complete∗/ 735: if ((LTlatest nb = LTlatest comp nb ) AND (LT conditioned = LTlatest comp nb )) then 736: /∗ Classified complete as latest timestamp, but LT conditioned not conditioned on latest complete ∗/ 737: return (FAIL) 738: end if 739:

740: /∗ Validate condition on relationship, performing repair ∗/ 741: if (((LTlatest nb = LTlatest comp nb ) AND (LTlatest nb = LTlatest ni nb )) AND (LT.Verifier Data = LTlatest ni nb.Verifier Data) OR (LT conditioned = LTlatest comp nb bd )) then 742: return (FAIL) 743: end if 744: end if 745: return (SUCCESS)

–  –  –

Logical timestamps returned from classifying the object history set on the storage-node:

• LTlatest barrier : Latest barrier logical timestamp;

• LTlatest nb : Latest non-barrier logical timestamp;

• LTlatest ni nb : Latest non-incomplete, non-barrier logical timestamp;

• LTlatest comp nb : Latest complete, non-barrier logical timestamp;

• LTlatest comp nb bd : Latest complete, non-barrier, by deduction logical timestamp.

Note: LTlatest comp nb bd = MAX[LTlatest comp nb, LTlatest ni nbconditioned ]

Figure 4.9: Logical timestamps returned from classification.

line 701. Next, the authenticators for the object history set is validated (cf.

line 705). Recall, the object history set is comprised of history sets from each of the storage-nodes queried during the read operation phase. Each of these history sets has a corresponding authenticator that must be validated. The impact of failed authenticator validation is discussed in Section 4.6.2.

Next, the verifiers, stored within the timestamp, are validated (cf. lines 708 - 713).

Again, the storage-node is replicating client logic to ensure that the validating timestamp is well-formed. The object history set verifier determines the conditioned-on relationship for a the CW operation and the value verifier determines the value of the CW operation, thus limiting the actions a Byzantine client can perform.

By performing classification on the object history set, line 716, the storage-node can validate that the candidate is the correct candidate, and that the timestamp is the correct timestamp (since both are deterministic given an object history set). As well, the storagenode can check to see if a barrier is required (cf. line 719). To make these checks, storagenode classification returns multiple logical timestamps, each set to a logical timestamp within the object history set. These timestamps are described within Figure 4.9.

The descriptions of most of the timestamps returned from classification are clear.

However, the LTlatest comp nb bd timestamp deserves further discussion. As described, this timestamp represents a version that is complete by deduction. A candidate that is complete by deduction is a candidate that is necessarily complete, but has not been observed as such. This occurs when a repairable (non-barrier) candidate A is observed (in the object history set) to have conditioned upon another, earlier, repairable (non-barrier) candidate B.

Recall, a complete candidate may be viewed as repairable. Since A is repairable, it has · 74 Efficient, scalable consistency for highly fault-tolerant storage passed validation at ≥ QC − t storage-nodes, of which at least QC − t − b are benign (see the constraint derivations for more details, Section 4.4). The only possible way that A can pass validation at a benign storage-node is by conditioning on a complete (non-barrier) candidate. Thus, B must be complete (by deduction).

Barriers are required to squash pending CW requests (e.g., incomplete CW operations from failed clients). A barrier is required if there exists any non-barrier, non-complete CW request that exists within the object history set at a later logical timestamp than any other complete CW write or barrier operation (i.e., there exists a pending incomplete CW operation). If the Barrier portion of the logical timestamp is set to TRUE, the storagenode knows that the CW request is part of a barrier-write. The only further validation that occurs for barrier-writes is that of the acceptance-check against the replica’s history.

The acceptance-check, line 728 ensures that a CW request has not been executed locally that is later than the latest logical timestamp present within the object history set.

If the CW is not a barrier-write, the conditioned-on relationship is then validated (cf. lines 734 - 743). There are two cases for validation. First, a complete candidate is classified as the latest non-barrier. In this case, the conditioned-on timestamp is verified against the latest complete, non-barrier CW (cf. line 735).

Second, a repairable candidate is classified as the latest non-barrier. That is, the latest non-barrier is the same as the latest non-incomplete, non-barrier operation and the latest non-barrier is not the latest complete, line 741. If the candidate is repairable, two validations are performed. First, the storage-node validates that the object value for the CW request is the same as the repairable candidates (this ensures that the repair occurs correctly). Second, the CW’s conditioning on timestamp is checked against the repairable’s conditioning on timestamp (note, in this case LTlatest comp nb bd = LTlatest ni nbconditioned );

this ensures the continuity of the conditioning chain.

A summary of the conditions that hold if storage-node validation succeeds is presented in Figure 4.10. These are derived from the pseudo-code shown in Figure 4.8.


4.4 Constraints 75

–  –  –

4.4 Constraints This section presents bounds on N and QC, the definition of a complete CW operation (in terms of t and b), and constraints on COMPLETE and INCOMPLETE. The derivation of constraints is similar to that for the protocol for R/W objects in Section 3.4. The differences in bounds arise mainly from the added constraint that repairable candidates must intersect with complete candidates for the R/CW protocol to be safe. A formal proof of the safety and liveness of the R/CW protocol and its extension to the Q/U protocol is given in [Abd-El-Malek et al. 2004].

4.4.1 Read classification rules

Recall that the candidate is the data-item version, returned by a read request, with the greatest logical timestamp. The set of read responses that share the candidate’s timestamp are the candidate set. Constraints on COMPLETE and INCOMPLETE are required to ensure two properties. The first property is that if a candidate is ever classified as complete, then any subsequent read operation observes the complete candidate as repairable. The second property is that if candidate A is complete and conditioned-on candidate B, any repairable candidate with a timestamp greater than A either conditioned-on A or can traverse the conditioned-on chain back to A.

To classify a candidate as complete, a candidate set of at least QC benign storagenodes must be observed. In the worst case, at most b members of the candidate set may be Byzantine, thus, |CandidateSet| − b ≥ QC ⇒ COMPLETE = QC + b. (4.1) · 76 Efficient, scalable consistency for highly fault-tolerant storage To classify a candidate as incomplete, the candidate must be incomplete (i.e., fewer than QC benign storage-nodes have executed the CW). We consider a rule for classifying incomplete candidates that takes advantage of N − t responses from storage-nodes. In the crash-recovery model, eventually, a client is guaranteed to receive this many responses— even though, there may be periods during which more than t storage-nodes are crashed.

Moreover, a client cannot expect more than this many responses, since up to t storagenodes may never recover (and in an asynchronous environment crash failures are undetectable). Thus, the rule for classifying a candidate incomplete is, |CandidateSet| + t QC ⇒ INCOMPLETE = QC − t. (4.2) Candidates that cannot be classified as complete or incomplete are classified as repairable.

Given these constraints on COMPLETE and INCOMPLETE, consider the examples illustrated in Figure 4.2. In this example, t = 1 and b = 0, so COMPLETE = 3, INCOMPLETE = 2, and N = 4. Since client A observes a candidate with timestamp 5 in two replica histories, and this is not less than the incomplete threshold, it classifies 5 as repairable. Whereas candidate 6 is observed by client B in one replica history and classified incomplete.

4.4.2 Real repairable candidates

This property ensures that colluding Byzantine storage-nodes are unable to fabricate a candidate that a correct client deems repairable. To achieve this property, a candidate set of size b must be classifiable as incomplete. Substituting |CandidateSet| = b into (4.2),

–  –  –

didate may be observable as repairable, a client may observe two repairable candidate’s (even though one is complete) and not know which candidate to repair. If the “wrong candidate” (i.e., the one that is not complete) is repaired, the condition on chain is violated.

To achieve this property, it is necessary that a complete candidate and repairable candidate intersect at at least one benign storage-node. Thus, from the lower bounds of repairable and complete candidates,

–  –  –

4.4.4 Read set intersection The intersection between a complete and a candidate set of QC benign storage-nodes must result in at least a repairable being observed. Thus,

–  –  –

4.4.5 CW termination A CW operation is defined to be complete once a total of QC benign storage-nodes have executed the CW.

Pages:     | 1 |   ...   | 8 | 9 || 11 | 12 |   ...   | 18 |

Similar works:

«OPPORTUNISTIC PRIVATE INVESTMENT PROGRAM STRATEGIC PLAN BOARD APPROVED: 02/18/2011 ARIZONA STATE RETIREMENT SYSTEM 3300 N CENTRAL AVENUE PHOENIX, AZ 85012 ARIZONA STATE RETIREMENT SYSTEM TABLE OF CONTENTS OPPORTUNISTIC PRIVATE INVESTMENT PROGRAM STRATEGIC PLAN P age |i TABLE OF CONTENTS Introduction Investment Philosophy Mission Statement Investment Themes and Considerations Objectives Return Objectives Risk Mitigation Governance Structure Defined Roles for Decision-Making Bodies Appendix A...»

«Brno University of Technology Faculty of Information Technology Department of Computer Graphics and Multimedia Omni-directional image processing for human detection and tracking A THESIS SUBMITTED IN FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY. Ing. Igor Potúček Supervised by: Doc.Dr.Ing.Pavel Zemčík Submitted: June 2006 State doctoral exam: 14.June 2004 Availability: Library of the Faculty of Information Technology, Brno University of Technology, Czech Republic...»

«Communication as Symbiogenesis On the Relationality of Mobile Phoning in Korea Namsook Park Thesis submitted for the Degree of Doctor of Philosophy Centre for Cultural Studies Goldsmiths College University of London Declaration I declare that the work presented in this thesis is entirely my own. Namsook Park London, August 2011 Abstract This study understands communication as parasitic and symbiogenetic. It recognizes an object or technology no less and no more important than a subject, and...»

«Imagem Tânia Maria Pereira Lopes Non-Invasive Hemodynamic Parameters Assessment using Optoelectronic Devices Thesis submitted to the University of Coimbra in fulfillment of the requirements for the degree of Doctor of Philosophy (PhD) in Biomedical Engineering under the scientific supervision of PhD João Manuel Rendeiro Cardoso and Full Professor Carlos Manuel Alexandre Correia University of Coimbra Faculty of Sciences and Technology Department of Physics Non-Invasive Hemodynamic Paramenters...»

«Centre for Philosophy of Natural and Social Science ABSTRACTS OF PAPERS Note that in many instances the following abstracts summarise works that are in various stages of completion. Please do not quote without consulting the author(s). Claus Beisbart How to Make a Difference – Measures of Voting Power Revamped Claus Beisbart and Luc Bovens Voting power (i-power) measures the extent to which a vote can make a difference to the outcome of a collective decision. And a voter has the opportunity...»

«In Vivo Measurement and Visualization of Pelvic Position and Orientation and Changes in Soft Tissue Shape and Thickness with Respect to Changes in Seating Surface Shape Thomas G. Ault CMU-RI-TR-05-56 November 9th, 2005 Carnegie Mellon University Pittsburgh, Pennsylvania 15213 Submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy in the field of Robotics Thesis Committee: Mel Siegel, Robotics Institute (Chair) David Brienza, University of Pittsburgh Stephen...»

«LUTHERAN IN TWO WORLDS: REMAKING MISSION FROM MADAGASCAR TO THE MIDWEST UNITED STATES by Britt E. Halvorson A dissertation submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy (Anthropology) in The University of Michigan Doctoral Committee: Professor Gillian Feeley-Harnik, Co-Chair Professor Thomas E. Fricke, Co-Chair Associate Professor Paul C. Johnson Associate Professor Erik A. Mueggler © Britt E. Halvorson All rights reserved DEDICATION In memory of...»

«Cost Benefit Analysis for Software Process Improvements Sapan K Shah Submitted for the Degree of Master of Philosophy from the University of Surrey UniS Department of Computing School of Electronics and Physical Sciences University of Surrey Guildford, Surrey GU2 7XH, UK Oct 2008 Supervised by: Professor Paul Krause, Dr Bill Mitchell ©Sapan K Shah 2008 Abstract Software Process Improvement (SPI) techniques have repeatedly proven to be effective in removing defects from software artefacts and...»

«Modeling of Hall thruster lifetime and erosion mechanisms Shannon Yun-Ming Cheng, Manuel Martinez-Sanchez May 2007 SSL # 23-07 Modeling of Hall thruster lifetime and erosion mechanisms by Shannon Yun-Ming Cheng S.B., Aeronautics and Astronautics, Massachusetts Institute of Technology (2000) S.M., Aeronautics and Astronautics, Massachusetts Institute of Technology (2002) Submitted to the Department of Aeronautics and Astronautics in partial fulfillment of the requirements for the degree of...»

«Hand, David John (1988) Regulation of curd initiation in the summer cauliflower. PhD thesis, University of Nottingham.Access from the University of Nottingham repository: http://eprints.nottingham.ac.uk/27674/1/384336.pdf Copyright and reuse: The Nottingham ePrints service makes this work by researchers of the University of Nottingham available open access under the following conditions. This article is made available under the University of Nottingham End User licence and may be reused...»

«THE KENYON REVIEW Vol. XVII W I N T E R, 1955 No. 1 Walter Kaufman NIETZSCHE AND RILKE T HIS STUDY of Nietzsche and Rilke, and particularly of what they have in common, is meant to throw light on both and also on the relation of philosophy and poetry. To those who are used to comparisons of Nietzsche with Nero and of Rilke with St. Francis any insistence on common elements will come as a surprise; but it may also disabuse them of some misapprehensions. There are, of course, obvious differences...»

«EUROPEAN JOURNAL OF PRAGMATISM AND AMERICAN PHILOSOPHY COPYRIGHT © 2009ASSOCIAZIONE PRAGMA Patrick Baert Neo-Pragmatism and Phenomenology: A Proposal Abstract. This article introduces a new pragmatist-inspired perspective on the social sciences. It explores the relevance of neo-pragmatism for the philosophy of the social sciences, showing how it can lead to innovative and groundbreaking social research. The paper attempts to drive home these insights by elaborating on the affinities of...»

<<  HOME   |    CONTACTS
2017 www.abstract.dislib.info - Abstracts, online materials

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.