Method and system for achieving consensus using alternate voting strategies (AVS) with incomplete information

• US 10,007,438 B2
• Filed: 06/25/2016
• Issued: 06/26/2018
• Est. Priority Date: 06/25/2016
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Dhuse, Greg R., Khadiwala, Ravi V., Wozniak, Ethan S.
• Primary Examiner(s): Queler, Adam M
• Assistant Examiner(s): Olson, Alex G
• Application Number:
  US15/193,024
• Publication Number:
  US 20170371541A1
• Time in Patent Office: 731 Days
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 3/0611 in relation to response time
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

A computing device having interface, memory, and processing module, transmits write requests for a set of encoded data slices to storage units (SUs) of a dispersed storage network (DSN) based on a write request process and to receive proposal records for a subset of the set of encoded data slices from at least some of the SUs. The computing device interprets the proposal records to determine whether it or any another computing device has a threshold number of its respective write requests in a first priority position in the ordered list of pending write requests. When no computing device has the threshold number, the computing device determines whether any computing device can be blacklisted and/or eliminated and whether a winner of the ballot can be determined after such determination. When a winner is determined, the computing device transmits finalize commands to the storage units.

Claims

1. A computing device comprising:

an interface configured to interface with a dispersed storage network (DSN);

a memory; and

a processing module operably coupled to the interface and to the memory, wherein the processing module is configured to;

transmit, via the interface, write requests for a set of encoded data slices to storage units (SUs) of a dispersed storage network (DSN) based on a write request process, wherein a data segment is dispersed error encoded to produce the set of encoded data slices, wherein a threshold number of encoded data slices provides for reconstruction of the data segment, wherein each write request of the write requests corresponds to a respective one data slice of the set of encoded data slices and is transmitted to a respective one SU of the SUs;

receive, via the interface of the computing device, proposal records for a subset of the set of encoded data slices from at least some of the SUs, wherein a proposal record of the proposal records includes an ordered list of pending write requests including one of the write requests and another write request from another computing device;

interpret the proposal records to determine whether the computing device or the other computing device has a threshold number of its respective write requests in a first priority position in the ordered list of pending write requests;

when neither of the computing device nor the other computing device has the threshold number of its respective write requests in the first priority position;

determine a number of missing proposal records;

determine whether either the computing device or the other computing device has an actual number of the first priority positions of the respective write requests that is more than the number of missing proposal records less than the threshold number;

when the other computing device has the actual number of the first priority positions of the respective write requests that is more than the number of missing proposal records less than the threshold number;

remove the other write request from the other computing device from the proposal requests to produce updated proposal records;

interpret the updated proposal records to determine whether the computing device has the threshold number of write requests in the first priority position; and

when the computing device has the threshold number of write requests in the first priority position of the updated proposal records, transmit, via the interface, finalize commands to the storage units.

2. The computing device of claim 1, wherein the processing module is further configured to:

transmit, via the interface, finalize commands to the storage units when the computing device has the threshold number of its respective write requests in the first priority position in the proposal records.

3. The computing device of claim 1, wherein the processing module is further configured to:

request a new set of proposal records from the SUs based on the write requests when both the computing device and the other computing device have the actual number of the first priority positions of the respective write requests that is equal to or less than the number of missing proposal records less than the threshold number.

4. The computing device of claim 1, wherein the processing module is further configured to:

abort the write request process when both the computing device and the other computing device have the actual number of the first priority positions of the respective write requests that is equal to or less than the number of missing proposal records less than the threshold number.

5. The computing device of claim 4, wherein the processing module is further configured to:

transmit, via the interface, new write requests for the set of encoded data slices to SUs of the DSN based on another write request process.

6. The computing device of claim 1, wherein the processing module is further configured to:

when neither the computing device nor the other computing device has the actual number of the first priority positions of the respective write requests that is equal to or less than the number of missing proposal records less than the threshold number and when the other computing device'"'"'s actual number plus the number of missing proposal records is less than the computing device'"'"'s actual number plus the number missing proposal records;

remove the other write request from the other computing device from the proposal requests to produce other updated proposal records; and

interpret the other updated proposal records.

7. The computing device of claim 1, wherein the processing module is further configured to:

receive, via the interface, the proposal records for the subset of the set of encoded data slices from at least some of the SUs, wherein a first proposal record of the proposal records includes a first ordered list of pending write requests including one of the write requests and a first other write request from a first other computing device, and wherein a second proposal record of the proposal records includes a second ordered list of pending write requests including another one of the write requests and a second other write request from a second other computing device;

interpret the proposal records to determine whether the computing device, the first other computing device, or the second other computing device has the threshold number of its respective write requests in a first priority position in the ordered list of pending write requests;

when none of the computing device, the first other computing device, or the second other computing device has the threshold number of its respective write requests in the first priority position;

determine the number of missing proposal records;

determine whether any of the computing device, the first other computing device, or the second other computing device has the actual number of the first priority positions of the respective write requests that is more than the number of missing proposal records less than the threshold number;

when each of the first other computing device and the second other computing device have the actual number of the first priority positions of the respective write requests that is more than the number of missing proposal records less than the threshold number;

remove the first other write request from the first other computing device from the proposal requests to produce first updated proposal records;

interpret the first updated proposal records;

remove the second other write request from the second other computing device from the proposal requests to produce second updated proposal records;

interpret the second updated proposal records; and

when interpretation of the first updated proposal records and the second updated proposal records both identify the computing device as having the threshold number of write requests in the first priority position of the updated proposal records, transmit, via the interface, finalize commands to the storage units.

8. The computing device of claim 1, wherein the processing module is further configured to:

receive, via the interface, a first proposal record of the proposal records from a first SU that is remotely located from the computing device within the DSN and a second proposal record of the proposal records from a second SU that is remotely located from the computing device and the first SU within the DSN.

9. A method for execution by a computing device, the method comprising:

transmitting, via an interface of the computing device that is configured to interface with a dispersed storage network (DSN), write requests for a set of encoded data slices to storage units (SUs) of a dispersed storage network (DSN) based on a write request process, wherein a data segment is dispersed error encoded to produce the set of encoded data slices, wherein a threshold number of encoded data slices provides for reconstruction of the data segment, wherein each write request of the write requests corresponds to a respective one data slice of the set of encoded data slices and is transmitted to a respective one SU of the SUs;

receiving, via the interface of the computing device, proposal records for a subset of the set of encoded data slices from at least some of the SUs, wherein a proposal record of the proposal records includes an ordered list of pending write requests including one of the write requests and other write request from other computing device;

interpreting the proposal records to determine whether the computing device or the other computing device has a threshold number of its respective write requests in a first priority position in the ordered list of pending write requests;

when neither of the computing device nor the other computing device has the threshold number of its respective write requests in the first priority position;

determining a number of missing proposal records;

determining whether either the computing device or the other computing device has an actual number of the first priority positions of the respective write requests that is more than the number of missing proposal records less than the threshold number;

when the other computing device has the actual number of the first priority positions of the respective write requests that is more than the number of missing proposal records less than the threshold number;

removing the other write request from the other computing device from the proposal requests to produce updated proposal records;

interpreting the updated proposal records to determine whether the computing device has the threshold number of write requests in the first priority position; and

when the computing device has the threshold number of write requests in the first priority position of the updated proposal records, transmitting, via the interface of the computing device, finalize commands to the storage units.

10. The method of claim 9 further comprising:

transmitting, via the interface of the computing device, finalize commands to the storage units when the computing device has the threshold number of its respective write requests in the first priority position in the proposal records.

11. The method of claim 9 further comprising:

requesting a new set of proposal records from the SUs based on the write requests when both the computing device and the other computing device have the actual number of the first priority positions of the respective write requests that is equal to or less than the number of missing proposal records less than the threshold number.

12. The method of claim 9 further comprising:

aborting the write request process when both the computing device and the other computing device have the actual number of the first priority positions of the respective write requests that is equal to or less than the number of missing proposal records less than the threshold number.

13. The method of claim 9 further comprising:

transmitting, via the interface of the computing device, new write requests for the set of encoded data slices to SUs of the DSN based on another write request process.

14. The method of claim 9 further comprising:

when neither the computing device nor the other computing device has the actual number of the first priority positions of the respective write requests that is equal to or less than the number of missing proposal records less than the threshold number and when the other computing device'"'"'s actual number plus the number of missing proposal records is less than the computing device'"'"'s actual number plus the number missing proposal records;

removing the other write request from the other computing device from the proposal requests to produce other updated proposal records; and

interpreting the other updated proposal records.

15. The method of claim 9 further comprising:

receiving, via the interface of the computing device, the proposal records for the subset of the set of encoded data slices from at least some of the SUs, wherein a first proposal record of the proposal records includes a first ordered list of pending write requests including one of the write requests and a first other write request from a first other computing device, and wherein a second proposal record of the proposal records includes a second ordered list of pending write requests including another one of the write requests and a second other write request from a second other computing device;

interpreting the proposal records to determine whether the computing device, the first other computing device, or the second other computing device has the threshold number of its respective write requests in a first priority position in the ordered list of pending write requests;

when none of the computing device, the first other computing device, or the second other computing device has the threshold number of its respective write requests in the first priority position;

determining the number of missing proposal records;

determining whether any of the computing device, the first other computing device, or the second other computing device has the actual number of the first priority positions of the respective write requests that is more than the number of missing proposal records less than the threshold number;

when each of the first other computing device and the second other computing device have the actual number of the first priority positions of the respective write requests that is more than the number of missing proposal records less than the threshold number;

removing the first other write request from the first other computing device from the proposal requests to produce first updated proposal records;

interpreting the first updated proposal records;

removing the second other write request from the second other computing device from the proposal requests to produce second updated proposal records;

interpreting the second updated proposal records; and

when interpretation of the first updated proposal records and the second updated proposal records both identify the computing device as having the threshold number of write requests in the first priority position of the updated proposal records, transmitting, via the interface of the computing device, finalize commands to the storage units.

16. The method of claim 9 further comprising:

receiving, via the interface of the computing device, a first proposal record of the proposal records from a first SU that is remotely located from the computing device within the DSN and a second proposal record of the proposal records from a second SU that is remotely located from the computing device and the first SU within the DSN.