FREE ELECTRONIC LIBRARY - Abstracts, online materials

Pages:     | 1 |   ...   | 16 | 17 ||

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

-- [ Page 18 ] --

SCHNEIDER, F. B. 1990. Implementing fault-tolerant services using the state machine approach: a tutorial. ACM Computing Surveys 22, 4, 299–319.

SHAMIR, A. 1979. How to share a secret. Communications of the ACM 22, 11, 612–613.

· 138 Efficient, scalable consistency for highly fault-tolerant storage

–  –  –

distributed system. IEEE Transactions on Software Engineering 9, 3, 261–270.

SOLTIS, S. R., RUWART, T. M., AND O’KEEFE, M. T. 1996. The global file system. In NASA Goddard Space Flight Center Conference on Mass Storage Systems and Technologies. IEEE Computer Society Press.

–  –  –

Metadata efficiency in versioning file systems. In Conference on File and Storage Technologies. USENIX Association, 43–58.

STEINER, J. G., SCHILLER, J. I., AND NEUMAN, C. 1988. Kerberos: an authentication service for open network systems. In Winter USENIX Technical Conference. 191–202.

–  –  –

GANGER, G. R. 2002. Intrusion detection, diagnosis, and recovery with self-securing storage. Tech. Rep. CMU–CS–02–140, Carnegie Mellon University.

–  –  –

GANGER, G. R. 2000. Self-securing storage: protecting data in compromised systems.

In Symposium on Operating Systems Design and Implementation. USENIX Association, 165–180.

THAMBIDURAI, P. AND PARK, Y.-K. 1988. Interactive consistency with multiple failure modes. In Symposium on Reliable Distributed Systems. IEEE, 93–100.

THEKKATH, C. A., MANN, T., AND LEE, E. K. 1997. Frangipani: a scalable distributed file system. In ACM Symposium on Operating System Principles. ACM, 224–237.

–  –  –

WEATHERSPOON, H. AND KUBIATOWICZ, J. D. 2002. Erasure coding vs. replication: a quantitative approach. In First International Workshop on Peer-to-Peer Systems (IPTPS 2002).

WYLIE, J. J., BIGRIGG, M. W., STRUNK, J. D., GANGER, G. R., KILICCOTE, H., AND KHOSLA, P. K. 2000. Survivable information storage systems. IEEE Computer 33, 8, 61–68.

· 140 Efficient, scalable consistency for highly fault-tolerant storage A Read/write safety and liveness

–  –  –

This section presents a proof that our protocol implements linearizability [Herlihy and Wing 1990] as adapted appropriately for a fault model admitting operations by Byzantine clients.

A.1.1 Safety guarantees Intuitively, linearizability requires that each read operation return a value consistent with some execution in which each read and write is performed at a distinct point in time between when the client invokes the operation and when the operation returns. The adaptations necessary to reasonably interpret linearizability in our context arise from the fact that Byzantine clients need not follow the read and write protocols and that read operations

may abort in non-repair member protocols. We consider four distinct safety guarantees:

Linearizability Repairable protocol members with crash-only clients achieve linearizability as originally defined by Herlihy and Wing [Herlihy and Wing 1990].

Byzantine-operation linearizability Read operations by Byzantine clients are excluded from the set of linearizable operations.

Write operations are only included if they are well-formed (i.e., if they are single-valued · 142 Efficient, scalable consistency for highly fault-tolerant storage as in Section 3.2).

Write operations by Byzantine clients do not have a well-defined start time. Such operations are concurrent to all operations that begin before they complete and to all operations that are also performed by Byzantine clients. A Byzantine client can write “back in time” by using a lower logical timestamp than a benign client would have used.

Since write operations by Byzantine clients are concurrent to all operations that started before it completed, they can be linearized just prior to some concurrent write operation (if there is one). Such a linearization ensures that the Byzantine “back in time” write operation has no effect since the value written is never returned by a read operation.

In summary, there are two types of Byzantine write operations that are of concern:

writes that are not well-formed and “back in time” writes. In the case that the Byzantine write operation is not well-formed, read operations by benign clients exclude it from the set of linearized operations. In the case that the Byzantine write operation is “back in time”, the protocol family achieves something similar, in that such Byzantine write operations are linearized so that they have no effect.

A.1.2 Proof

Because return values of reads by Byzantine clients obviously need not comply with any correctness criteria, we disregard read operations by Byzantine clients in reasoning about linearizability, and define the duration of reads only for those executed by benign clients only.

DEFINITION 1 A read operation executed by a benign client begins when the client invokes READ locally. A read operation executed by a benign client completes when this invocation returns timestamp, value. A read operation by a benign client that crashes before the read completes, does not complete.

–  –  –

DEFINITION 2 Storage-node S, accepts a write request with data-fragment D, cross checksum CC, and timestamp ts upon successful return of the function VALIDATE WRITE(ts, D, CC) at the storage-node.

DEFINITION 3 Storage-node S, executes a write request once the write request is accepted. An executed write request is stored in stable storage.

It is not well defined when a write operation by a Byzantine client begins. Therefore, we settle for merely a definition of when writes by Byzantine clients complete.

DEFINITION 4 A write operation with timestamp ts completes once QC benign storagenodes have executed write requests with timestamp ts.

In fact, Definition 4 applies to write operations by benign clients as well as “write operations” by Byzantine clients. In this section, we use the label wts as a shorthand for the write operation with timestamp ts. In contrast to Definition 4, Definition 5 applies only to write operations by benign clients.

DEFINITION 5 wts begins when a benign client invokes the WRITE operation locally that issues a write request bearing timestamp ts.

LEMMA 1 Let c1 and c2 be benign clients. If c1 performs a read operation that returns ts1, v1, c2 performs a read operation that returns ts2, v2, and ts1 = ts2, then v1 = v2.

Proof: Since ts1 = ts2, each read operation considers the same verifier. Since each read operation considers the same verifier, each read operation considers the same cross checksum (remember, a collision resistant hash function is employed). A read operation does not return a value unless the cross checksum is valid and there are more than b read responses with the timestamp (since only candidates classified as repairable or complete are considered). Thus, only a set of data-fragments resulting from the erasure-coding of the same data-item that are issued as write requests with the same timestamp can validate a cross checksum. As such, v1 and v2 must be the same. 2 · 144 Efficient, scalable consistency for highly fault-tolerant storage Let vts denote the value written by wts which, by Lemma 1, is well-defined. We use rts to denote a read operation by a benign client that returns ts, vts.

DEFINITION 6 Let o1 denote an operation that completes (a read operation by a benign client, or a write operation), and let o2 denote an operation that begins (a read or write by a benign client). o1 precedes o2 if o1 completes before o2 begins. The precedence relation is written as o1 → o2. Operation o2 is said to follow, or to be subsequent to, operation o1.

LEMMA 2 If wts → wts, then ts ts.

Proof: A complete write operation executes at at least QC benign storage-nodes (cf. Definition 4). Since wts → wts, the READ TIMESTAMP function for wts collects N −t TIME RESPONSE messages, and so wts observes at least b + 1 TIME RESPONSE messages from benign storage-nodes that executed wts (remember, t + b QC for all asynchronous protocol family members). As such, wts observes some timestamp greater than or equal to ts and constructs ts to be greater than ts. A Byzantine storage-node can return a logical timestamp greater than that of the preceding write operation; however, this still advances logical time and Lemma 2 holds. 2 OBSERVATION 1 Timestamp order is a total order on write operations. The timestamps of write operations by benign clients respect the precedence order among writes.

LEMMA 3 If some read operation by a benign client returns ts, vts, with vts = ⊥, then wts is complete.

Proof: For a read operation to return value vts, the value must have been observed at at least QC + b storage-nodes (given the complete classification rule for candidate sets).

Since, at most b storage-nodes are Byzantine, the write operation wts has been executed by at least QC benign storage-nodes. By definition, wts is complete. 2

–  –  –

DEFINITION 7 wts is well-formed if ts.Verifier equals the hash of cross checksum CC, and for all i ∈ {1,..., N}, hash CC[i] of the cross checksum equals the hash of data-fragment i that results from the erasure-encoding of vts.

LEMMA 4 If wts is well-formed, and if wts → rts, then ts ≤ ts.

–  –  –

OBSERVATION 3 It follows from Lemma 4 that for any read rts, either wts → rts and wts is the latest complete write that precedes rts, or wts → rts and rts → wts (i.e., wts and rts are concurrent).

OBSERVATION 4 It also follows from Lemmas 3 and 4 that if rts → rts, then ts ≤ ts.

As such, there is a partial order on read operations by benign clients defined by the timestamps associated with the values returned (i.e., of the write operations read). More rts ⇐⇒ ts ts.

formally, rts Since Lemma 2 ensures a total order on write operations, ordering reads according to the timestamps of the write operations whose values they return yields a partial order on read operations. Lemma 4 ensures that this partial order is consistent with precedence among reads. Therefore, any way of extending this partial order to a total order yields an ordering of reads that is consistent with precedence among reads. Thus, Lemmas 2 and 4 guarantee that this totally ordered set of operations is consistent with precedence.

This implies the natural extension of linearizability to our fault model (i.e., ignoring reads by Byzantine clients and the begin time of writes by Byzantine clients); in particular, it implies linearizability as originally defined by Herlihy [Herlihy and Wing 1990] for the read/write protocol if all clients are benign.

· 146 Efficient, scalable consistency for highly fault-tolerant storage A.2 Proof of liveness This section presents the proof of the liveness properties of protocol members.

A.2.1 Liveness guarantees There are two distinct liveness guarantees: wait-freedom and single-client wait-freedom.

These guarantees hold so long as the storage capacity on storage-nodes is not exhausted.

Wait-freedom Wait-freedom is a desirable liveness property [Herlihy 1991]. Informally, achieving waitfreedom means that each client can complete its operations in finitely many steps regardless of the actions performed or failures experienced by other clients. For a formal definitions see [Herlihy 1991].

Unbounded storage capacity

In the proof of liveness for read operations, we assume that storage-nodes have unbounded storage capacity (i.e., that the entire version history back to the initial value ⊥ at time 0 is available at each storage-node). To prevent capacity exhaustion, some garbage collection mechanism is required. Garbage collection reduces the liveness of read operations. A read operation that is concurrent to write operations and to garbage collection may not observe a complete candidate. The read operation can observe a series of incomplete candidates that complete and are garbage collected within the duration of the read operation. In such a situation, the read operation would observe ⊥ at some timestamp other than 0 from storage-nodes, indicating that the client has “skipped” over a complete write operation.

The read operation then must be retried. The implementation details of garbage collection and its impact on liveness properties is given in Section 3.7.3.

A.2.2 Proof

–  –  –

LEMMA 5 All operations eventually receive at least N − t responses.

Proof: In the crash-recovery model, there are at least N − t good storage-nodes (i.e., storage-nodes that are always-up or eventually-up). By definition, eventually, all good storage-nodes will be up. Since all requests to storage-nodes, from clients, are retried until N −t responses are received, eventually, N −t responses will be received (see READ TIMESTAMP, DO WRITE, and DO READ). 2 OBSERVATION 5 It is possible for progress to be made throughout the duration of a run, not just once all good storage-nodes are up. Lemma 5 guarantees that eventually N − t responses will be received. During any period in which N − t storage-nodes are up, operations may receive N −t responses and thus complete. In fact, responses can be collected, over time, from N − t storage-nodes, during a period in which fewer than N − t storagenodes are ever up (but during which some storage-nodes crash and some recover).

Asynchronous repairable

The asynchronous repairable protocol member provides a strong liveness property, namely wait-freedom [Herlihy 1991; Jayanti et al. 1998]. Informally, each operation by a correct client completes with certainty, even if all other clients fail, provided that at most b servers suffer Byzantine failures and no more than t servers are not good.

LEMMA 6 A write operation by a correct client completes.

Proof: A write operation by a correct client waits for N − t responses from storagenodes before returning. By Lemma 5, N − t responses can always be collected. Since, QC ≤ N − t − b (cf. (3.5) in Section 3.4) for repairable protocol members, then N − t ≥ QC + b. Since at most b storage-nodes are Byzantine, then at least QC benign storagenodes execute write requests, which completes the write operation. 2 LEMMA 7 A read operation by a correct client completes.

· 148 Efficient, scalable consistency for highly fault-tolerant storage Proof: Given N − t READ RESPONSE messages, a read operation classifies a candidate as complete, repairable, or incomplete. The read completes if a candidate is classified as complete. As well, the read completes if a candidate is repairable. Repair is initiated for repairable candidates—repair performs a write operation, which by Lemma 6 completes—which lets the read operation complete. In the case of an incomplete, the read operation traverses the version history backwards, until a complete or repairable candidate is discovered. Traversal of the version history terminates if ⊥ at logical time 0

Pages:     | 1 |   ...   | 16 | 17 ||

Similar works:

«International Strategic Partnerships page 1 INTERNATIONAL STRATEGIC PARTNERSHIPS by Tony Baker, Managing Partner, Market Access Worldwide Trade is not a zero sum game. Trade breeds more trade. If you win, then your winning helps me win too. This is true for individuals, for companies, and for countries. Partnering with other companies, in other countries, fits well with this philosophy. Especially for small and medium-sized companies, it is very desirable to develop overseas by using...»

«Opera in a New Age: Mass Media, the “Popular,” and Opera, 1900-1960 by Rebecca M. Mitchell A dissertation submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy (History) in the University of Michigan Doctoral Committee: Professor James W. Cook, Jr., Chair Associate Professor John S. Carson Associate Professor Mark A. Clague Professor Philip J. Deloria © Rebecca M. Mitchell 2014 ii DEDICATION This dissertation is dedicated with gratefulness to my...»

«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...»

«Penultimate draft. For published version see Philosophical Perspectives 18, 2004 Puppies, Pigs, and People: Eating Meat and Marginal Cases 1. Fred’s Basement. Consider the story of Fred, who receives a visit from the police one day. They have been summoned by Fred's neighbors, who have been disturbed by strange sounds emanating from Fred's basement. When they enter the basement they are confronted by the following scene: Twenty-six small wire cages, each containing a puppy, some whining, some...»

«Multivalent Documents: Anytime, Anywhere, Any Type, Every Way User-Improvable Digital Documents and Systems by Thomas Arthur Phelps B.S. (University of Illinois at Urbana-Champaign) 1990 A.B. (University of Illinois at Urbana-Champaign) 1990 M.S. (University of California, Berkeley) 1993 A dissertation submitted in partial satisfaction of the requirements for the degree of Doctor of Philosophy in Computer Science in the GRADUATE DIVISION of the UNIVERSITY of CALIFORNIA, BERKELEY Committee in...»

«Philosophical Perspectives, 23, Ethics, 2009 INTENTION, PERMISSIBILITY, TERRORISM, AND WAR Jeff McMahan Rutgers University 1 Introduction There are many important moral beliefs that have been comparatively stable over time and across cultures that seem to presuppose that the intention with which one acts can affect the permissibility of one’s action. Until about forty years ago, the consensus among moral philosophers was that these beliefs are indeed best explained and justified by the idea...»

«THE SCIENTIFIC PROOF OF SURVIVAL AFTER DEATH Censored in Great Britain Michael Roll The Campaign for Philosophical Freedom www.cfpf.org.uk The Campaign for Philosophical Freedom www.cfpf.org.uk Contents THE SCIENTIFIC PROOF OF SURVIVAL AFTER DEATH 3 1. Paranormal Phenomena Do Not Exist 3 2. Paranormal Phenomena Do Exist 3 WHAT IS MEANT BY SCIENTIFIC PROOF? 5 THE EXPERIMENTAL PROOF OF SURVIVAL AFTER DEATH 6 References 6 THE ETHERIC WORLD MUST HAVE AN ASTRONOMICAL LOCALITY 7 References 7 RONALD...»

«Knowledge and Science in Paradise Lost Rosa Flotats ESTUDIS UNIVERSITARIS DE VIC Ours is an age in which science is of various trends and each is isolated from the others. The study of human knowledge, once in the general scope of all fields and sciences, now seems to be the exclusive property of philosophy. The 20th century will be studied in the future as a century of technology and of linguistics. Improvements and new technologies are the real cause for this well established separation into...»

«Epistemology ‘Audi’s introduction is at once philosophically insightful and masterfully written – even more so in its new edition. Guaranteed to fascinate the beginner while retaining its exalted status with the experts.’ Claudio de Almeida, PUCRS, Brazil ‘My students like this book and have learned much from it, as I have. Epistemology – especially in its second edition – is simply the best textbook in epistemology that I know of.’ Thomas Vinci, Dalhousie University, Canada...»

«Rome: Ancient by Eugene Rice Encyclopedia Copyright © 2015, glbtq, Inc. Entry Copyright © 2004, glbtq, inc. Reprinted from http://www.glbtq.com When Romans write about love, they normally are even-handed: For Ovid (43 B.C.E.-17 C.E.) love can be inspired by a boy or a girl (aut puer aut. puella) and Lucretius (94-55 B.C.E.) sees no difference whether boy or women (sive puer. seu mulier). Musonius Rufus (ca 30-102 C.E.) taught Stoic moral philosophy at Rome during the reigns of Nero and...»

«KNOW THYSELF : THE IMPACT OF PORTFOLIO DEVELOPMENT ON ADULT LEARNING JUDITH O. BROWN Barry University Thousands of years ago the Greeks carved above their temples the phrase know thyself, two simple words that imply a lifetime of investigation. Throughout the ages philosophers and scholars have emphasized the importance of self-knowledge as an outcome of learning. One teaching strategy that facilitates self-knowledge among adult students is the creation of an experiential learning portfolio...»

«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.