Patent Publication Number: US-8533478-B2

Title: System for and method of writing and reading redundant data

Description:
FIELD OF THE INVENTION 
     The present invention relates to the field of distributed data storage and, more particularly, to fault tolerant data replication and distributed protocols. 
     BACKGROUND OF THE INVENTION 
     Enterprise-class data storage systems differ from consumer-class storage systems primarily in their requirements for reliability. For example, a feature commonly desired for enterprise-class storage systems is that the storage system should not lose data or stop serving data in circumstances that fall short of a complete disaster. To fulfill these requirements, such storage systems are generally constructed from customized, high reliability, hardware components. Their firmware, including the operating system, is typically built from the ground up. Designing and building the hardware components is time-consuming and expensive, and this, coupled with relatively low manufacturing volumes is a major factor in the typically high prices of such storage systems. Another disadvantage to such systems is lack of scalability of a single system. Customers typically pay a high up-front cost for even a minimum disk array configuration, yet a single system can support only a finite capacity and performance. Customers may exceed these limits, resulting in poorly performing systems or having to purchase multiple systems, both of which increase management costs. 
     It has been proposed to increase the fault tolerance of off-the-shelf or commodity storage system components through and the use of data replication. However, this solution requires coordinated operation of the redundant components and synchronization of the replicated data. 
     Therefore, what is needed are improved techniques for storage environments in which redundant devices are provided or in which data is replicated. It is toward this end that the present invention is directed. 
     SUMMARY OF THE INVENTION 
     The present invention provides a system for and a method of writing and reading redundant data. In accordance with an embodiment of the invention, data is written by storing a copy of the data along with a timestamp and a signature at each of a set of storage devices. The data is read by retrieving the copy of the data, the timestamp and the signature from each of a plurality of the set of data storage devices. One of the copies of the data is selected to be provided to a requester of the data. Each of the storage devices of the set is requested to certify the selected copy of the data. Provided that a proof of certification of the selected copy of the data is valid, the storage devices of the set are instructed to store the selected copy of the data along with a new timestamp. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The present invention is described with respect to particular exemplary embodiments thereof and reference is accordingly made to the drawings in which: 
         FIG. 1  illustrates an exemplary storage system including multiple redundant storage device nodes in accordance with an embodiment of the present invention; 
         FIG. 2  illustrates an exemplary storage device for use in the storage system of  FIG. 1  in accordance with an embodiment of the present invention; 
         FIG. 3  illustrates a flow diagram of a method of writing and reading data in accordance with an embodiment of the present invention; 
         FIGS. 4A and 4B  illustrate exemplary timing diagrams for writing and reading data, respectively, in accordance with an embodiment of the present invention; 
         FIGS. 5A-C  illustrate pseudocode for writing and reading data in accordance with an embodiment of the present invention; 
         FIGS. 6A and 6B  illustrate exemplary timing diagrams for writing and reading data, respectively, in accordance with an embodiment of the present invention; and 
         FIGS. 7A-C  illustrate pseudocode for writing and reading data in accordance with an embodiment of the present invention. 
     
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     The present invention provides improved techniques for storage environments in which redundant storage devices are provided or in which data is replicated. Each storage device may be, but need not be, constructed of commodity components while their operation is coordinated in a decentralized manner. From the perspective of applications requiring storage services, the plurality of storage devices present a single, highly available copy of the data, though the data is replicated. Techniques are provided for accommodating failures and other irregular behaviors, such as malicious security attacks, in a manner that is transparent to applications requiring storage services. A storage device which is the subject of a malicious attack or other circumstance that causes irregular behavior is referred to herein as being “byzantine.” A process performed by such a byzantine device is also referred to herein as “byzantine.” 
       FIG. 1  illustrates an exemplary storage system  100  including multiple redundant storage devices  102  in accordance with an embodiment of the present invention. The storage devices  102  communicate with each other via a communication medium  104 , such as a network (e.g., using Remote Direct Memory Access or RDMA over Ethernet). One or more clients  106  (e.g., servers) access the storage system  100  via a communication medium  108  for accessing data stored therein by performing read and write operations. The communication medium  108  may be implemented by direct or network connections using, for example, iSCSI over Ethernet, Fibre Channel, SCSI or Serial Attached SCSI protocols. While the communication media  104  and  108  are illustrated as being separate, they may be combined or connected to each other. The clients  106  may execute application software (e.g., an email or database application) that generates data and/or requires access to the data. 
       FIG. 2  illustrates an exemplary storage device  102  for use in the storage system  100  of  FIG. 1  in accordance with an embodiment of the present invention. As shown in  FIG. 2 , the storage device  102  may include an interface  110 , a central processing unit (CPU)  112 , mass storage  114 , such as one or more hard disks, and memory  116 , which is preferably non-volatile (e.g., NV-RAM). The interface  110  enables the storage device  102  to communicate with other devices  102  of the storage system  100  and with devices external to the storage system  100 , such as the clients  106 . The CPU  112  generally controls operation of the storage device  102 . The memory  116  generally acts as a cache memory for temporarily storing data to be written to the mass storage  114  and data read from the mass storage  114 . The memory  116  may also store additional information associated with the data, as explained in more detail herein. 
     Preferably, each storage device  102  is composed of off-the-shelf or commodity parts so as to minimize cost. I-However, it is not necessary that each storage device  102  is identical to the others. For example, they may be composed of disparate parts and may differ in performance and/or storage capacity. 
     To provide fault tolerance, data is replicated within the storage system  100 . In a preferred embodiment, for each data element, such as a block, an object or a file, at least two different storage devices  102  in the system  100  are designated for storing replicas of the data, where the number of designated storage devices and, thus, the number of replicas, is given as “n.” To ensure that the data copies remain consistent, successful read and write operations preferably require participation of at least a majority of the designated devices. 
       FIGS. 1 and 2  represent physical computer hardware by which the methods described herein can be implemented. For example, software may be tangibly stored in one or more computer-readable media which form a part of the computer hardware of  FIGS. 1 and 2 . For example, a computer-readable medium may comprise a floppy disk, an optical disk, a magnetic disk or solid state memory, such as RAM, DRAM, or flash memory. Such software, when executed by the computer hardware, causes the hardware to perform the method steps described herein, including the sending and receiving of communications among the storage devices  102  and the clients  106  and the writing and the reading of data to and from the memory  114  and mass storage  116 . 
       FIG. 3  illustrates a flow diagram  300  of a method of writing and reading data in accordance with an embodiment of the present invention. In a step  302 , data is written by storing a copy of the data along with a timestamp and a signature at each of a set of storage devices (e.g., the storage devices  102  of  FIGS. 1 and 2 ). The number of devices  102  included in the set is preferably, n, the number of devices designated for storing the data. The timestamp is preferably representative of a current time when the request for writing the data is initiated. For purposes of explanation, the value of the copy of the data may be given as v, while the timestamp may be given as T and the signature may be given as S. As used herein, f is a number of the n storage devices that can be byzantine while the system still writes and reads correctly. Thus, n−f is the number of storage devices needed to conduct read and write operations. 
     Each storage device  102 , given as p, preferably has a pair (e p , d p ) of public and private keys. In addition, each of the clients  106  has a pair (e client , d client ) of public and private keys. Further, all processes executing within the system may have access to all of the public keys used within the system. For purposes of explanation, the signature S of message m with key d p  may be given as S p (m). Further, a verification of a signature S against message m using key e p  may be given as V p (s,m). In step  302 , the message that includes the data value v and the timestamp T is signed by the client  106  that initiated the request. Thus, in step  302 , the data v and timestamp T to be stored at each of the storage devices p may be included within a message m, with each message m being signed by a corresponding signature S client (m), with the signature being sent along with the message. It is assumed that byzantine processes cannot break these cryptographic primitives. 
     In a step  304 , at a time after the data v was written, the data is read by retrieving the copy of the data, the timestamp and the signature from each of a plurality of the set of n data storage devices and selecting one of the copies of the data to be provided to a requestor of the data. The copy to be provided to the requestor is selected according to the timestamps and signatures of the retrieved copies. In an embodiment, the copy to be provided to the requestor has the highest timestamp T among those copies that have a valid signature, which indicates that the copy is the most-recently stored valid copy. For purposes of explanation, the selected copy may be given as v*. 
     In accordance with an embodiment of the present invention, a write or a read request may be received by any one of the storage devices  102  of the storage system  100 , and may be initiated by any of the clients  106 . The storage device  102  that receives the request acts as the coordinator for the request. While the device that receives the request may also be a designated device for storing the data, this is not necessary. Thus, any of the devices  102  may receive the request. So that each device  102  has information regarding the locations of data within the system  100 , each may store, or otherwise have access to, a table of data locations which associates an identification of the data (e.g., a block or file) to identifications of the storage devices  102  designated for storing copies of the data. The coordinator device communicates with the designated devices (and also accesses its own storage if it is also a designated device) for performing the write and read operations described herein. 
     In a step  306 , each or the storage devices of the set is requested to certify the selected copy of the data. To accomplish this, the coordinator may send the signed message that includes the selected copy of the data v* to each of the set of storage devices. The results of this verification (referred to as a proof of certification) may then be communicated from each of the storage devices to the coordinator for the read operation. 
     In a step  308 , provided that the proof of certification of the selected copy of the data is valid, the storage devices of the set are instructed to store the selected copy of the data along with a new timestamp. This may be accomplished by coordinator issuing this instruction along with the selected copy of the data v* and a new timestamp T to each of the n storage devices of the set. This new timestamp T is preferably representative of a current time when the read request is issued by the client  106  in step  304 . 
       FIG. 4A  illustrates an exemplary timing diagram for writing data in accordance with an embodiment of the present invention. As explained above in connection with  FIG. 3 , a client  106  signs requests issued by the client. This allows the storage devices  102  to execute the requests with confidence that the request was validly originated. In addition, the storage devices  102  preferably sign responses so that the client can verify that its request was fulfilled. For example, to write a data value v to a storage device  102 , a client signs a request with the data value v and a timestamp T, and sends it to the coordinator (e.g., in step  302  in  FIG. 3 ). The coordinator then instructs the storage devices  102  to store v and T, attaching the client&#39;s signature to a message sent to the storage devices  102 . The storage devices  102  store this signature, along with v and T to be used later in reads. It is preferable that the signature is generated from both v and T, not just v, for otherwise a malicious coordinator could overwrite new values with old values. Each storage device  102  may then respond with a signed acknowledgement that it stored v and T, which the coordinator returns to the client  106  as proof of execution of the write operation. 
     To summarize the write procedure of step  302 , the client signs a write request with a data value v and a new timestamp T. The coordinator forwards this request to all storage devices  102  designated for storing the data, who then store (v, T) and the client signature. 
       FIG. 4B  illustrates an exemplary timing diagram for reading the data in accordance with an embodiment of the present invention. The method of reading the data from the storage devices  102  preferably prevents a byzantine process from being able to store an invalid data value with a more-recent timestamp than is associated with the valid copies of the data. To accomplish this, the read operation includes a write-back mechanism (i.e. the store operation of step  308 ). The write-back mechanism protects against a circumstance referred to herein as a ‘pending write.’ A pending write occurs when a value is stored only at a minority of the designated storage devices (e.g., because the client and coordinator crashed while the value was being written). In this case, subsequent reads by a different coordinator may return different data, depending on whether the read majority intersects the minority of storage devices with the pending write. The store operation addresses pending writes in two ways. First, if a data value v* with a most-recent timestamp was stored only at a minority of storage devices  102 , then that data value is propagated to a majority of the storage devices  102  during the store operation. Second, there could be a pending write of some value (given as  v ) with a higher timestamp than the most-recent successful write (this is possible since the coordinator can miss replies from failed storage devices). Such a pending write can cause the write to take effect at a time in the future when some coordinator finally sees the value  v . Writing back v* with a new timestamp (which is larger than  v &#39;s timestamp) during the store operation ensures that  v  will not be picked in a future read. This is referred to herein as ‘timestamp promotion’ of v*. 
     The read operation includes three phases, shown by the three triangular ‘humps’ in  FIG. 4B . These three phases correspond to the steps  304 ,  306  and  308 , of  FIG. 3 , respectively. The read operation may be initiated by a client  106  sending a read request to one of the storage devices  102  which acts as the coordinator. The client  106  preferably obtains and signs a new timestamp and includes it with the request. Then, in a first phase (step  304 ), the coordinator issues a query to each of the plurality of the set of n data storage devices  102  requesting that each data storage device return its copy of the data v along with its corresponding timestamp T and signature S stored by each storage device. The coordinator then selects the data value v* having a most-recent timestamp T* from among the returned values v that are determined to be valid (we explain this validity determination herein below). So that the correct value is chosen for v* the coordinator preferably ensures that at least n−f replies are returned in response to its query in step  304 . 
     After querying storage devices and picking the value v* with the largest timestamp from among the valid returned values v, the coordinator needs to write back the data value v* with the new timestamp T to the storage devices of the set; however, there is no client signature authorizing such a write-back. More particularly, the client signed the new timestamp T authorizing some to-be-specified write-back with timestamp T, but the client did not have v* so that write-back of v* with timestamp T has not been authorized. To guard against a byzantine coordinator, it is desired to prevent the coordinator from writing back an incorrect value for the data. The certification step  306  helps to guard against this possibility. In an embodiment of the certification step  306 , the coordinator sends a message to the client requesting that the client sign a request to write-back v* and the new timestamp T. However, this embodiment requires additional communication between the clients  106  and storage devices  102 . To avoid this additional communication, in another embodiment of the certification step  306 , the coordinator sends to the set of storage devices the entire set of replies from which v* was picked. The set of replies may be given as R. Each storage device then validates this write-back by examining the set of replies R and verifying that the coordinator chose v* correctly. To prevent the coordinator from forging the set of replies R, the examining performed by each storage device includes verifying that each of the replies in the set R was signed by a different storage device. 
     However, if a byzantine coordinator happens to receive more than n−f replies, it could generate two different sets of n−f replies each, such that the data value v* having the most-recent timestamp is different for each set. By doing so, the coordinator can cause different storage devices to write back different values. This situation may be avoided by having the coordinator certify a value-timestamp pair before it is stored at a storage device. At most, one value-timestamp pair can be certified for a given timestamp. This may performed in the certification step  306  as follows:
         (1) The coordinator sends R, v* and the new timestamp T to each of the storage devices.   (2) The storage devices check that v* is computed correctly from R and reply with a signed statement including R, v* and T. A non-byzantine storage device signs at most one statement for a given T; to keep track of that, a storage device remembers the largest T used in a statement it previously signed, and it rejects signing statements with smaller or equal timestamps. Timestamps T are preferably signed by clients so that a byzantine storage device cannot cause storage devices to reject signing statements for the largest timestamp.   (3) The coordinator collects signed statements from n−f storage devices into a vector of signatures. This vector is referred to herein as a ‘certificate’ represented by a variable valproof.       

     The valproof certificate confirms that v* can be safely promoted to timestamp T. Thus, in step  308 , the coordinator attaches the certificate to the write-back request of v*, and each storage device then verifies that the certificate is correct (by determining that all statements refer to v* and T, and they are signed by n−f storage devices). If so, the storage device stores v*, T, and the certificate. The storage device needs to store the certificate so that later, when it replies to a read request, it can prove that its value-timestamp pair (v*, T) is legitimate. In other words, a storage device can either store a data-timestamp pair (v, T) that comes from a write operation, or a data-timestamp pair (v, T) that comes from a write-back operation. In the first case, there is a client signature for (v, T), and in the second case, there is a certificate for (v, T) and there is a client signature on T. 
     Because each valproof certificate includes n−f signatures, each storage device needs space to store θ(n) signatures. When a read coordinator queries storage devices, it may receive n−f different certificates, which together have θ(n 2 ) signatures. 
       FIGS. 5A-C  illustrate pseudocode for writing and reading data in accordance with an embodiment of the present invention.  FIGS. 5A-C  show details such as checking the formatting of messages, timestamps, and signatures. The code has three parts. The top part illustrated in  FIG. 5A  shows code executed by the clients  106 . The middle part illustrated in  FIG. 5B  shows code executed by storage devices  102 , including coordinator code (left column), and code for responding to the coordinator (right column). In accordance with the code shown in  FIG. 5B : (1) the storage devices use and check signatures throughout, to prevent a byzantine storage device from deviating significantly from the method; and (2) the read coordinator runs a phase to certify a value before it is written back. This certification phase uses a timestamp T to keep track of the largest timestamp certified by a storage device. A storage device refuses to certify smaller timestamps. When a storage device stores a value v with some promoted timestamp T (that is, a timestamp that is not the original one used to write v), it also stores a proof or certificate that the promotion is valid. This certificate is stored in variable valproof. The certificate consists of signed statements from n−f storage devices, each statement containing v and timestamp T. Storing the valproof certificate takes θ(n) space. 
     A storage device that stores a value v with its original timestamp T (without promotion) does not store a valproof certificate. This is because there is a client signature on v and T to prove that T is a valid timestamp for v. When a coordinator queries values from each storage device, it needs to check the valproof certificate or the client signature that comes with each value. In the worst case, all storage devices reply with a valproof certificate (instead of a client signature), in which case the coordinator needs to check θ(n 2 ) signatures. In an alternative embodiment, explained below, such valproof certificates do not need to be stored. 
     The bottom part illustrated in  FIG. 5C  has auxiliary boolean functions used by both clients and storage devices to check messages and signatures. Each function returns whether the check passes. For example, chkValProof (v, T, valproof) checks that a valproof is a correct certificate for v and T, that is, valproof is a set of statements containing v and T signed by n−f storage devices. Π S  refers to the set of n storage devices. 
     In accordance with the embodiments of  FIGS. 4A-B  and  5 A-C, in a system with n storage devices and k clients, up to f&lt;n/3 storage devices can be byzantine and any number of clients can crash while the system can still effectively execute read and write operations. For each operation, a client sends and receives only one message and storage devices check θ(n 2 ) signatures. 
     To summarize the read procedure of  FIGS. 4A-B  and  5 A-C, the client signs a new timestamp T and sends it to the coordinator. The coordinator queries the n storage devices and receives a set of replies with at least n−f of the storage devices replying with a valid client signature or valproof certificate (this step corresponds to step  304  of  FIG. 3 ). The coordinator picks the value v* with highest timestamp (among the values with a valid client signature or valproof certificate), and sends the set of replies, v*, and T to all of the storage devices, who then verify the set of replies, v*, and T, and reply with a signed statement (step  306  of  FIG. 3 ). The coordinator collects n−f properly signed statements to form a valproof certificate and uses the valproof certificate to write back v* with timestamp T. The storage devices store v*, T and valproof (step  308  of  FIG. 3 ). 
     In accordance with the method described above in connection with  FIGS. 4A-B  and  5 A-C, space required at each storage device is θ(n) (since a storage device may have to store a certificate with a signature from n−f storage devices) and reading a value may involve checking all the signatures of n−f certificates, for a total of θ(n 2 ) signatures. In accordance with an alternative embodiment of a method of writing and reading data (described below in connection with  FIGS. 6A-B  and  7 A-C), the signature usage is reduced. This may be accomplished by the storage devices not storing the certificates and by the read operation not requiring checking certificates. As a result, space at each storage device is θ(1) and operations check θ(n) signatures. There is a trade-off: the alternative method of  FIGS. 6A-B  and  7 A-C tolerates up to f&lt;n/4 byzantine storage devices instead of f&lt;n/3, as in the method of  FIGS. 4A-B  and  5 A-C. 
       FIGS. 6A and 6B  illustrate exemplary timing diagrams for writing and reading data, respectively, in accordance with an alternative embodiment of the present invention. To understand how the alternative method works, consider what might happen to the method described above if storage devices did not keep certificates and read coordinators did not check them. In this case, a byzantine storage device could falsely claim that an old value has been promoted to a new timestamp. If this were to happen, the next read request would return an old value (which was promoted to the highest timestamp), and this would violate linearizability. It appears that this problem might be solved by requiring timestamps to be signed by clients; in this case, however, a client may sign a new timestamp for reading, send this timestamp to a byzantine coordinator, and then crash. Now a byzantine storage device has a signed timestamp, and so the attack described above would still be possible. 
     The method described above in connection with  FIGS. 4A-B  and  5 A-C solved this problem by using certificates to prevent byzantine storage devices from promoting old values to new timestamps. The alternative method of  FIGS. 6A-B  and  7 A-C employs a new mechanism to select a ‘winning value’ in a read operation rather than selecting the value with highest timestamp. This alternative mechanism helps to ensure that even if byzantine storage devices promote old values to new timestamps, these values are not picked by a read coordinator, even if the read coordinator cannot tell that these values were maliciously promoted. 
     Note that there are at most f byzantine storage devices. Therefore, the read coordinator can use the following rule to choose the data value that will be returned from among the values stored at the set of storage devices: Order the data values by timestamp, breaking ties arbitrarily, and discard the top f values, picking the top value that is left as the one to be returned to the requestor. This winning rule is based on the idea that after a value is written or written-back, it is stored with the highest timestamp at n−f storage devices. Later, if f byzantine storage devices try to promote old values to larger timestamps, the (f+1)-th top value is still an uncorrupted value. This mechanism, however, could potentially be defeated under a more sophisticated attack. 
     Such an attack may be accomplished as follows: (1) Initially, all storage devices hold a value v with timestamp T. (2) Then, a byzantine storage device changes its stored value to some old value {circumflex over (v)} but with a new, higher timestamp {circumflex over (T)}&gt;T. (3) Next, a client requests a write for v 1  with timestamp T 1 &gt;T 0 , the request goes to a byzantine coordinator, the coordinator only sends (v 1 , T 1 ) to one non-byzantine storage device, and the client crashes. (4) Similarly for each of values v 2 , . . . , v f , some client requests a write for v j  with timestamp T j &gt;T j-1 , the request goes to a byzantine coordinator, the coordinator only sends (v j , T j ) to a non-byzantine storage device (and the storage device is different for each j), and the client crashes. After all this, f non-byzantine storage devices hold values v 1 , . . . , v f  with timestamps T 1 , . . . , T f , respectively, and one byzantine storage device holds value {circumflex over (v)} with timestamp T 0 . If a read occurs next, the above-described winning-rule incorrectly picks {circumflex over (v)} as the value to be returned to the client. But the only acceptable values that could be picked (according to linearizability) is v or one of the v j &#39;s. 
     An alternative embodiment of the winning rule is the following: Discard data values stored at less than f+1 storage devices; among the data values left, select the one with highest timestamp. 
     This winning rule is based on the idea that, since there are a maximum of f byzantine storage devices, the above rule discards any maliciously-promoted values that those f storage devices might hold. It appears possible that this rule could end up discarding all values in certain circumstances. This could occur, for example, if a client starts a write, sends its request to byzantine coordinator, which stores the value at a single storage device, and then the client crashes. In this case, each storage device (including non-byzantine ones) could end up with a different value. 
     Yet another embodiment of the ‘winning rule’ keeps track of an additional timestamp. Preferably, this is the timestamp used originally to write the value (in step  302 ). For example, suppose the data value v is first written with timestamp T 1  and, later, a write-back promotes v&#39;s timestamp to T 2 . Then, each storage device stores v, T 1  and T 2 . For purposes of explanation, T 1  is referred to herein as the ‘left’ timestamp of v, and T 2  is the ‘right’ timestamp of v. If T 1  has not been promoted, then T 2 =T 1 . Note that storage devices need not keep the entire history of timestamps of a value: they preferably only keep the original timestamp (the ‘left’ timestamp) and the latest promoted timestamp (the ‘right’ timestamp). For example, if a subsequent write-back promotes v&#39;s timestamp to T 3 , then T 1  and T 3  are stored, not T 2 . A ‘left’ timestamp comes from a previous write operation, and there is a client signature that binds the timestamp to the value v written during the write operation. A ‘right’ timestamp, if different from the left timestamp, comes from the timestamp promotion in a read operation; there is client signature on the timestamp, but it does not bind it to any data value. Thus, the ‘right’ timestamp is changed each time the data is read. The left and right timestamps can be combined into a pair [T 1 , T 2 ] or into a triple [T 1 , T 2 , v], where v is the value bound to T 1 . 
     This method may use the following ‘winning rule’: (1) Among the n−f triples obtained from storage devices, find a set, referred herein as candSet, of 2f+1 triples with the largest right timestamps. Ties may be broken arbitrarily. (2) If some timestamp T 0  is the left timestamp of f+1 or more triples in candSet, pick any such triple as the winner. (3) Otherwise, pick the triple in candSet with largest left timestamp. Again, ties may be broken ties arbitrarily. 
     This winning rule ensures that in any run, if some read or write operation succeeds, resulting in n−2f non-byzantine storage devices storing the same triple [T 1 , T 2 , v], then afterwards, this winning rule will not select an old, stale value (i.e. one whose left timestamp is less than T 1 ). 
     Thus, a read returns a relatively recent value, which implies linearizability. Suppose some set S 1  of n−2f of non-byzantine storage devices store the same triple [T 1 , T 2 , v]. If a non-byzantine storage device stores a triple [T′ 1 , T′ 2 , v′] with T′ 2 &gt;T 2  then either T′ 1 =T 1  or T′ 1 &gt;T 2 . More particularly, after the set S 1  of storage devices store the same triple [T 1 , T 2 , v], suppose the winning rule is applied for a set S 2  of n−f triples (each triple from a different storage device), and consider the candSet computed in accordance with the rule as described above. Then: (1) candSet has at least one triple from a storage device in S 1  since candSet has 2f+1 elements; and (2) S 2  has at least n−3f elements from S 1 . Since f&lt;n/4, we have n−3f≧f+1. From this, it follows that S 2  has at least f+1 elements from S 1 , which are all non-byzantine storage devices. There are two cases: 
     Case 1: Assume that some timestamp T 0  is the left timestamp of f+1 or more triples in candSet—as in part (2) of the winning rule. Let goodCandSet be the triples in candSet from non-byzantine storage devices. Since candSet has 2f+1 triples, goodCandSet has at least f+1 triples. Storage devices in S 1  cannot replace their right timestamps with a timestamp smaller than T 2 , since a non-byzantine storage device preferably rejects requests to store right timestamps lower than its own. Thus, goodCandSet has at least f+1 triples with right timestamps equal to T 2  or greater. If such a triple has right timestamp greater than T 2  then, its left timestamps is either T 1  or greater than T 2 . If such a triple has right timestamp equal to T 2  then its left timestamp is equal to T 1  (since when a read coordinator is promoting timestamps to T 2 , it preferably commits to a single value and such a value is v, and the left timestamp of a triple is bound to its value through a client signature). Note that there are at most f triples in candSet that are not in goodCandSet. Therefore, timestamp T 0  (the timestamp which is the left timestamp of f+1 or more triples in candSet) is either equal to T 1  or it is greater than T 2 . Thus, the winning rule does not choose a triple whose left timestamp is less than T 1 . 
     Case 2: Now assume that no such timestamp T 0  exists, i.e., part (3) of the winning rule applies. Thus, candSet has at least one triple from a storage device in S 1  (since candSet has 2f+1 elements). Let p be such a storage device. If p changes its triple from [T 1 , T 2 , v] to something else, then its right timestamp increases, so its left timestamp either remains as T 1  or increases beyond T 2 . Therefore, the largest left timestamp in triples in candSet is at least T 1 . Thus, the winning rule does not choose a triple whose left timestamp is less than T 1 . 
     This shows that if some read or write operation succeeds, resulting in n−2f non-byzantine storage devices storing the same triple [T 1 , T 2 , v], then afterwards, this winning rule will not select an old, stale value (i.e. one whose left timestamp is less than T 1 ). It is worth noting that this does not hold if the winning rule is changed such that candSet had 2f+2 instead of 2f+1 triples with largest timestamp. This because part (2) of the winning rule could be triggered for a timestamp To smaller than T 1 . 
     In accordance with the embodiments of  FIGS. 6A-B  and  7 A-C, in a system with n storage devices and k clients, up to f&lt;n/4 storage devices can be byzantine and any number of clients can crash while the system can still effectively execute read and write operations. For each operation, a client sends and receives only one message and storage devices check θ(n) signatures. 
       FIGS. 7A-C  illustrate pseudocode for writing and reading data in accordance with an embodiment of the present invention.  FIGS. 7A-C  show details such as checking the formatting of messages, timestamps, and signatures. The code has three parts. The top part illustrated in  FIG. 7A  shows code executed by client, and it is similar to the method in  FIGS. 5A-C . In accordance with  FIGS. 7A-C , clients sign timestamps and requests, and they check that the replies are properly signed by storage devices. 
     The middle part illustrated in  FIG. 7B  shows code executed by storage devices, including coordinator code (left column), code for responding to the coordinator (right column), and the function with the winning rule (right column). The general structure of the method is similar to that of the method in  FIGS. 5A-C . A primary difference, explained in detail above, is the usage of signatures. As in the method of  FIG. 5A-C , the read protocol includes a certify phase. Further, the read coordinator uses function winreply to select the winning value. This function is shown on the right column. Each storage device stores its triple [T 1 , T 2 , v] in variables T l(eft) , T r(ight) , and Val, respectively. Variable T cert  is used for the certify phase: it stores the largest T used in a statement signed by the storage device. Variable T read  is stores the largest timestamp seen in a read operation. Variable CliWSig holds a client signature on Val and its timestamp, to prevent forgery of values. 
     The bottom part illustrated in  FIG. 7C  has auxiliary boolean functions used by both clients and storage devices to check messages and signatures. Each function returns whether the check passes. For example, chkValProof(v, T, valproof) checks that a valproof is a correct certificate for v and T (i.e., a set of statements containing v and T signed by n−f storage devices). 
     To summarize the read procedure of  FIGS. 6A-B  and  7 A-C, the client signs a new timestamp T and sends it to the coordinator. The coordinator queries the n storage devices and receives a set of n−f replies, where each reply includes a triple [T 1 , T 2 , v] from a storage device (this step corresponds to step  304  of  FIG. 3 ). From these replies, the coordinator identifies a set, referred herein as candSet and picks one of the triples [T 1 , T 2 , v] as the winner according to a ‘winning rule,’ as described above. The coordinator sends the set of replies, the winning data value v*, and T to all of the storage devices, who then verify the set of replies, v*, and T, and reply with a signed statement (step  306  of  FIG. 3 ). The coordinator collects n−f properly signed statements to form a valproof certificate and uses the valproof certificate to write back v* with timestamp T. The storage devices store v*, T 1  and T (step  308  of  FIG. 3 ). 
     The foregoing detailed description of the present invention is provided for the purposes of illustration and is not intended to be exhaustive or to limit the invention to the embodiments disclosed. Accordingly, the scope of the present invention is defined by the appended claims.