IP Library Granted Patent US 9,128,870
Granted Patent B2
US 9,128,870 · App. 14/480,139 · Granted Sep 8, 2015

Sending a zero information gain formatted encoded data slice

View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 9,128,870
App. No.
14/480,139
Granted
Sep 8, 2015
Kind
B2
Abstract

A method begins by a dispersed storage (DS) processing module determining whether to send an encoded data slice of set of encoded data slices in accordance with a zero information gain (ZIG) format. When the encoded data slice is to be sent in accordance with the ZIG format, the method continues with the DS processing module selecting a partial encoding threshold number of encoded data slices of the set of encoded data slices, wherein the partial encoding threshold number of encoded data slices does not include the encoded data slice and generating a set of ZIG encoded data slices based on a ZIG function and the partial encoding threshold number of encoded data slices, wherein the set of ZIG encoded data slices represents recovery information of the encoded data slice. The method continues with the DS processing module outputting the set of ZIG encoded data slices.

Claims (76)

1. A method for execution by a computing device, the method comprises:

determining, by the computing device, whether to send an encoded data slice of a set of encoded data slices or to send the encoded data slice in accordance with a zero information gain (ZIG) format, wherein data is encoded using a dispersed storage error coding function to produce the set of encoded data slices, and wherein the data can be recreated from a decode threshold number of encoded data slices of the set of encoded data slices, the decode threshold number of encoded data slices being less than a number of slices in the set of encoded data slices;

when the encoded data slice is to be sent in accordance with the ZIG format:

selecting a subset of the set of encoded data slices, in which the subset of the set of encoded data slices having less than the decode threshold number of encoded data slices and the subset not including the encoded data slice;

selecting one or more partial encoding of the encoded data slice, in which the one or more partial encoding associates the encoded data slice with one or more of other encoded data slices of the set of encoded data slices, but does not include the encoded data slice; and

generating one or more ZIG encoded data slices based on a ZIG function and the one or more partial encoding of the encoded data slice, wherein the one or more ZIG encoded data slices represent recovery information of the encoded data slice; and

outputting the subset of the encoded data slices and the one or more ZIG encoded data slices.

2. The method of claim 1 , wherein the determining whether to send the encoded data slice in the ZIG format comprises at least one of:

receiving an error message with regards to a previous transmission of the encoded data slice;

determining that the encoded data slice is of a first priority type;

receiving a request for transmission of the encoded data slice; and

determining that a slice name associated with the encoded data slice is on a list.

3. The method of claim 1 , wherein the selecting of the one or more partial encoding of the encoded data slice comprises:

selecting one or more encoded data slices of the set of encoded data slices to fulfill the decode threshold number of encoded data slices requirement for recreating the data, wherein the selecting the one or more encoded data slices includes at least one of:

selecting the one or more encoded data slices to include encoded error code blocks; and

selecting one or more encoded data slices to include encoded data blocks.

4. The method of claim 1 , wherein generating a ZIG encoded data slice of the one or more ZIG encoded data slices comprises:

generating a decoding matrix for the encoded data slice based on an encoding matrix of the dispersed storage error coding function; and

generating the ZIG encoded data slice by:

encoding a first encoded data slice of the one or more partial encoding of the encoded data slice using the decoding matrix to produce a vector; and

encoding the vector by a row of the decoding matrix corresponding to the encoded data slice to produce the ZIG encoded data slice.

5. The method of claim 4 , wherein the generating the decoding matrix comprises:

reducing the encoding matrix to produce a square matrix based on the one or more partial encoding of the encoded data slice; and

inverting the square matrix to produce the decoding matrix.

6. The method of claim 1 , wherein generating a ZIG encoded data slice of the one or more ZIG encoded data slices comprises:

generating a decoding matrix for the encoded data slice based on an encoding matrix of the dispersed storage error coding function; and

generating the ZIG encoded data slice by:

generating a first initial ZIG encoded data slice based on the decoding matrix and on a first encoded data slice of the one or more partial encoding of the encoded data slice;

generating a second initial ZIG encoded data slice based on the decoding matrix and on a second encoded data slice of the one or more partial encoding of the encoded data slice; and

combining the first and second initial ZIG encoded data slices to produce the ZIG encoded data slice.

7. The method of claim 1 , wherein the outputting the one or more ZIG encoded data slices comprises at least one of:

outputting a first one of the ZIG encoded data slices on a first path and outputting a second one of the ZIG encoded data slices on a second path;

outputting to a receiving entity in support of a communication with the receiving entity;

outputting to a dispersed storage network (DSN) memory for storage therein; and

outputting to at least one intermediary device.

8. The method of claim 1 , wherein the outputting further comprises:

prior to outputting the one or more ZIG encoded data slices, obfuscating at least one ZIG encoded data slice utilizing an obfuscation function.

9. A dispersed storage (DS) module comprises:

a first module, when operable within a computing device, causes the computing device to:

determine whether to send an encoded data slice of a set of encoded data slices or to send the encoded data slice in accordance with a zero information gain (ZIG) format, wherein data is encoded using a dispersed storage error coding function to produce the set of encoded data slices, and wherein the data can be recreated from a decode threshold number of encoded data slices of the set of encoded data slices, the decode threshold number of encoded data slices being less than a number of slices in the set of encoded data slices;

a second module, when operable within the computing device and when the encoded data slice is to be sent in accordance with the ZIG format, causes the computing device to:

select a subset of the set of encoded data slices, in which the subset of the set of encoded data slices having less than the decode threshold number of encoded data slices and the subset not including the encoded data slice

select one or more partial encoding of the encoded data slice, in which the one or more partial encoding associates the encoded data slice with one or more of other encoded data slices of the set of encoded data slices, but does not include the encoded data slice; and

generate one or more ZIG encoded data slices based on a ZIG function and the one or more partial encoding of the encoded data slice, wherein the one or more ZIG encoded data slices represent recovery information of the encoded data slice; and

a third module, when operable within the computing device, causes the computing device to:

output the subset of the set of encoded data slices and the one or more ZIG encoded data slices.

10. The DS module of claim 9 , wherein the first module functions to determine whether to send the encoded data slice in the ZIG format by at least one of:

receiving an error message with regards to a previous transmission of the encoded data slice;

determining that the encoded data slice is of a first priority type;

receiving a request for transmission of the encoded data slice; and

determining that a slice name associated with the encoded data slice is on a list.

11. The DS module of claim 9 , wherein the second module functions to select the one or more partial encoding of the encoded data slice by:

selecting one or more encoded data slices of the set of encoded data slices to fulfill the decode threshold number of encoded data slices requirement for recreating the data, wherein the selecting the one or more encoded data slices includes at least one of:

selecting the one or more encoded data slices to include encoded error code blocks; and

selecting one or more encoded data slices to include encoded data blocks.

12. The DS module of claim 9 , wherein the second module functions to generate a ZIG encoded data slice of the one or more ZIG encoded data slices by:

generating a decoding matrix for the encoded data slice based on an encoding matrix of the dispersed storage error coding function; and

generating the ZIG encoded data slice by:

encoding a first encoded data slice of the one or more partial encoding of the encoded data slice using the decoding matrix to produce a vector; and

encoding the vector by a row of the decoding matrix corresponding to the encoded data slice to produce the ZIG encoded data slice.

13. The DS module of claim 12 , wherein the second module functions to generate the decoding matrix by:

reducing the encoding matrix to produce a square matrix based on the one or more partial encoding of the encoded data slice; and

inverting the square matrix to produce the decoding matrix.

14. The DS module of claim 9 , wherein the second module functions to generate a ZIG encoded data slice of the one or more ZIG encoded data slices by:

generating a decoding matrix for the encoded data slice based on an encoding matrix of the dispersed storage error coding function; and

generating the ZIG encoded data slice by:

generating a first initial ZIG encoded data slice based on the decoding matrix and on a first encoded data slice of the one or more partial encoding of the encoded data slice;

generating a second initial ZIG encoded data slice based on the decoding matrix and on a second encoded data slice of the one or more partial encoding of the encoded data slice; and

combining the first and second initial ZIG encoded data slices to produce the ZIG encoded data slice.

15. The DS module of claim 9 , wherein the third module functions to output the one or more ZIG encoded data slices by at least one of:

outputting a first one of the ZIG encoded data slices on a first path and outputting a second one of the ZIG encoded data slices on a second path;

outputting to a receiving entity in support of a communication with the receiving entity;

outputting to a dispersed storage network (DSN) memory for storage therein; and

outputting to at least one intermediary device.

16. The DS module of claim 9 , wherein the third module further functions to output by:

prior to outputting the one or more ZIG encoded data slices, obfuscating at least one ZIG encoded data slice utilizing an obfuscation function.

Assignments (6)
TERMINATION AND RELEASE OF SECURITY INTEREST IN PATENT RIGHTS Recorded Jun 11, 2025
From: BARCLAYS BANK PLC, AS ADMINISTRATIVE AGENT
To: PURE STORAGE, INC.
Reel/Frame 071558/0523 →
SECURITY INTEREST Recorded Aug 26, 2020
From: PURE STORAGE, INC.
To: BARCLAYS BANK PLC AS ADMINISTRATIVE AGENT
Reel/Frame 053867/0581 →
CORRECTIVE ASSIGNMENT TO CORRECT THE 9992063 AND 10334045 LISTED IN ERROR PREVIOUSLY RECORDED ON REEL 049556 FRAME 0012. ASSIGNOR(S) HEREBY CONFIRMS THE ASSIGNOR HEREBY CONFIRMS THE ASSIGNMENT. Recorded Jan 14, 2020
From: INTERNATIONAL BUSINESS MACHINES CORPORATION
To: PURE STORAGE, INC.
Reel/Frame 052205/0705 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Jun 21, 2019
From: INTERNATIONAL BUSINESS MACHINES CORPORATION
To: PURE STORAGE, INC.
Reel/Frame 049556/0012 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded May 13, 2016
From: CLEVERSAFE, INC.
To: INTERNATIONAL BUSINESS MACHINES CORPORATION
Reel/Frame 038687/0596 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Apr 15, 2016
From: GRUBE, GARY W.; MARKISON, TIMOTHY W.
To: CLEVERSAFE, INC.
Reel/Frame 038296/0668 →