Storage-optimized data-atomic systems and techniques for handling erasures and errors in distributed storage systems

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.

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.

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.

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.

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.