# US 10,872,072 B2 · Storage-optimized data-atomic systems and techniques for handling erasures and errors in distributed storage systems > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,872,072 B2 - Document ID: US10872072B2 - Status: Granted - Kind: B2 - Application number: 15/838,966 - Filed: 2017-12-12 - Published: 2018-06-14 - Granted: 2020-12-22 - Earliest claimed: 2016-12-12 - Assignees: Massachusetts Institute of Technology; Northeastern University; University of Connecticut - Applicants: Massachusetts Institute of Technology; Northeastern University; University of Connecticut - Inventors: Muriel Medard; Kishori Mohan Konwar; Prakash Narayana Moorthy; Nancy Ann Lynch; Erez Kantor; Alexander Allister Schwarzmann - Web page: https://patentgrep.com/patent/US10872072B2 ## CPC - G06F 16/2329: {using versioning} - G06F 16/00: Information retrieval; Database structures therefor; File system structures therefor - G06F 16/27: Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor - H04L 67/1097: for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS] - H04L 69/26: {Special purpose or proprietary protocols or architectures (network applications for proprietary or special purpose networking environments H04L67/12)} - G06F 3/067: {Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## Abstract Described are devices, systems and techniques for implementing atomic memory objects in a multi-writer, multi-reader setting. In an embodiment, the devices, systems and techniques use maximum distance separable (MDS) codes, and may be specifically designed to optimize a total storage cost for a given fault-tolerance requirement. Also described is an embodiment to handle the case where some of the servers can return erroneous coded elements during a read operation. ## Claims ### Claim 1 A method of transmitting a message, that pertains to a data storage protocol, throughout a data storage network having a plurality of data storage servers logically numbered 1 through n, of which at most f are faulty, the method comprising: receiving the message in a first data storage server; and by each data storage server in the plurality, responsive to a first receiving of the message: (a) if the logical number of the responsive data storage server is no greater than f+1, forwarding the message to each data storage server having a logical number greater than that of the responsive data storage server; and (b) processing the message according to the data storage protocol; wherein the message is associated with a reader and includes a tag that is totally orderable with respect to other such tags, and wherein processing the message comprises: registering the tag in association with the reader; and when the tag is not higher ordered than a previously stored tag, sending to the reader the previously stored tag and a previously stored coded element computed from a version of a value uniquely identified by the previously stored tag. ### Claim 2 A method of transmitting a message, that pertains to a data storage protocol, throughout a data storage network having a plurality of data storage servers logically numbered 1 through n, of which at most f are faulty, the method comprising: receiving the message in a first data storage server; and by each data storage server in the plurality, responsive to a first receiving of the message: (a) if the logical number of the responsive data storage server is no greater than f+1, forwarding the message to each data storage server having a logical number greater than that of the responsive data storage server; and (b) processing the message according to the data storage protocol; wherein the message includes a version of a value to be written in the data storage network, and wherein: forwarding the message includes, for each data storage server having a logical number greater than f+1, replacing within the message the version of the value to be written by a coded element computed therefrom according to both an encoding scheme and the logical number of the respective data storage server; and processing the message comprises replacing within the message the version of the value to be written by a coded element computed therefrom according to both the encoding scheme and the logical number of the responsive data storage server. ### Claim 3 (depends on 2) A method according to claim 2, wherein the message includes a tag that is totally orderable with respect to other such tags, and wherein processing the message includes relaying the tag and the coded element to a reader when the tag is at least as highly ordered as a tag previously registered in association with the reader. ### Claim 4 (depends on 3) A method according to claim 3, wherein processing the message further includes storing the tag and the coded element when the tag is higher ordered than a previously stored tag. ### Claim 5 (depends on 2) A method according to claim 2, wherein the encoding scheme uses an [n, k] Maximum Distance Separable (MDS) code, where k≤n−f. ### Claim 6 A method of using a data storage network having a plurality of data storage servers logically numbered 1 through n, of which at most f are faulty, the method comprising: by each data storage server having a logical number no greater than f+1: receiving a first message that includes a version of a value to be stored in the data storage network; transmitting, to each data storage server having a logical number greater than f+1, a respective second message that includes a coded element computed from the version of the value according to both an encoding scheme and the logical number of the respective data storage server to which the second message is transmitted; and storing a coded element computed from the version of the value according to both the encoding scheme and the logical number of the data storage server; and by each data storage server having a logical number greater than f+1, responsive to a first receiving of the respective second message, storing the coded element included therein; whereby each data storage server in the plurality stores exactly one coded element in association with the version of the value. ### Claim 7 (depends on 6) A method according to claim 6, further comprising, by each data storage server in the plurality: receiving a third message associated with a reader that includes a tag that is totally orderable with respect to other such tags; registering the tag in association with the reader; and when the tag is not higher ordered than a previously stored tag, sending to the reader the previously stored tag and a previously stored coded element computed according to the encoding scheme from a version of the value uniquely identified by the previously stored tag. ### Claim 8 (depends on 7) A method according to claim 7, further comprising, by each data storage server in the plurality, informing each other data storage server in the plurality about such sending. ### Claim 9 (depends on 6) A method according to claim 6, wherein the first message includes a tag that is totally orderable with respect to other such tags, and storing the coded element includes relaying the tag and the coded element to a reader when the tag is at least as highly ordered as a tag previously registered in association with the reader. ### Claim 10 (depends on 9) A method according to claim 9, further comprising informing each other data storage server in the plurality about such relaying. ### Claim 11 (depends on 9) A method according to claim 9, wherein storing the coded element comprises storing only when the tag is higher ordered than a previously stored tag. ### Claim 12 (depends on 6) A method according to claim 6, wherein the encoding scheme uses an [n, k] Maximum Distance Separable (MDS) code, where k≤n−f. ### Claim 13 A method of transmitting a message, that pertains to a data storage protocol, throughout a data storage network having a plurality of n data storage servers, of which at most f are faulty, the method comprising: receiving the message in a first data storage server; and by each data storage server in the plurality of n data storage servers, responsive to a first receiving of the message: (a) if the responsive data storage server is in a first subset having f+1 of the plurality of n data storage servers, forwarding the message to each data storage server in a respective second subset of the first subset, and forwarding the message to each of the data storage servers not in the first subset; and (b) processing the message according to the data storage protocol; wherein the message is associated with a reader and includes a tag that is totally orderable with respect to other such tags, and wherein processing the message comprises: registering the tag in association with the reader; and when the tag is not higher ordered than a previously stored tag, sending to the reader the previously stored tag and a previously stored coded element computed from a version of a value uniquely identified by the previously stored tag. ### Claim 14 A method of transmitting a message, that pertains to a data storage protocol, throughout a data storage network having a plurality of n data storage servers, of which at most f are faulty, the method comprising: receiving the message in a first data storage server; and by each data storage server in the plurality of n data storage servers, responsive to a first receiving of the message: (a) if the responsive data storage server is in a first subset having f+1 of the plurality of n data storage servers, forwarding the message to each data storage server in a respective second subset of the first subset, and forwarding the message to each of the data storage servers not in the first subset; and (b) processing the message according to the data storage protocol; wherein the message includes a version of a value to be written in the data storage network, and wherein: forwarding the message to each of the data storage servers not in the first subset includes replacing within the message the version of the value to be written by a coded element computed therefrom according to an encoding scheme; and processing the message comprises replacing within the message the version of the value to be written by a coded element computed therefrom according to the encoding scheme. ### Claim 15 (depends on 14) A method according to claim 14, wherein the message includes a tag that is totally orderable with respect to other such tags, and wherein processing the message includes relaying the tag and the coded element to a reader when the tag is at least as highly ordered as a tag previously registered in association with the reader. ### Claim 16 A method of using a data storage network having a plurality of n data storage servers, of which at most f are faulty, the method comprising: by each data storage server in a given subset having f+1 of the plurality of n data storage servers: receiving a first message that includes a version of a value to be stored in the data storage network; transmitting, to each data storage server not in the given subset, a respective second message that includes a coded element computed from the version of the value according to an encoding scheme; and storing a coded element computed from the version of the value according to the encoding scheme; and by each data storage server not in the given subset, responsive to a first receiving of the respective second message, storing the coded element included therein. ### Claim 17 (depends on 16) A method according to claim 16, further comprising, by each data storage server in the plurality of n data storage servers: receiving a third message associated with a reader that includes a tag that is totally orderable with respect to other such tags; registering the tag in association with the reader; and when the tag is not higher ordered than a previously stored tag, sending to the reader the previously stored tag and a previously stored coded element computed according to the encoding scheme from a version of the value uniquely identified by the previously stored tag. ### Claim 18 (depends on 16) A method according to claim 16, wherein the first message includes a tag that is totally orderable with respect to other such tags, and storing the coded element includes relaying the tag and the coded element to a reader when the tag is at least as highly ordered as a tag previously registered in association with the reader. ### Claim 19 (depends on 15) A method according to claim 15, wherein processing the message further includes storing the tag and the coded element when the tag is higher ordered than a previously stored tag. ### Claim 20 (depends on 14) A method according to claim 14, wherein the encoding scheme uses an [n, k] Maximum Distance Separable (MDS) code, where k≤n−f.