Application US20200145387

METHODS AND APPARATUS FOR EFFICIENTLY IMPLEMENTING A DISTRIBUTED DATABASE WITHIN A NETWORK
[+] Show Details

US20200145387

1. An apparatus, comprising: (6) (2)

a memory associated with an instance of a distributed database at a first compute device configured to be included within a plurality of compute devices that implement the distributed database via a network operatively coupled to the plurality of compute devices; and

a processor operatively coupled to the memory, and configured to: define a first group of compute devices from the plurality of compute devices and a second group of compute devices from the plurality of compute devices, based on a deterministic pseudorandom function;

receive, from a second compute device from the plurality of compute devices, an event linked to a first set of events defined by a set of compute devices from the plurality of compute devices, the set of compute devices including at least one compute device from the first group of compute devices and at least one compute device from the second group of compute devices;

identify an order associated with a second set of events, as a result of a consensus protocol (1) using a value for a parameter of an event from the first set of events that was defined by a compute device from the first group of compute devices, and (2) not using a value for the parameter of an event from the first set of events that was defined by a compute device from the second group of compute devices;

identify an order associated with a plurality of transactions indicated in the instance of the distributed database based at least in part on the order associated with the second set of events; and

store in the instance of the distributed database the order associated with the plurality of transactions.

2. The apparatus of claim 1, wherein the processor is configured to identify the order associated with the second set of events by executing a byzantine fault tolerant consensus protocol based on a value of the parameter of events defined by the first group of compute devices and not a value of the parameter of events defined by the second group of compute devices. (0)

3. The apparatus of claim 1, wherein the first group of compute devices is an absolute complement of the second group of compute devices with respect to the plurality of compute devices that implement the distributed database. (0)

4. The apparatus of claim 1, wherein the processor is further configured to: (0) (3)

define a third group of compute devices from the plurality of compute devices that implement the distributed database, the third group of compute devices associated with an upper limit threshold value and a lower limit threshold value;

establish a communication session for a synchronization of events with each compute device from the third group of compute devices; and

after synchronization with a compute device from the third group of compute devices: terminate the communication session with the compute device from the third group of compute devices when a number of compute devices in the third group of compute devices reaches the upper limit threshold value;

maintain the communication session with a compute device from the third group of compute devices when the number of compute devices in the third group of compute devices remains below the upper limit threshold value and above the lower limit threshold value; and

establish a communication session for the synchronization of events with a third compute device from the plurality of compute devices when the number of compute devices in the third group of compute devices is below the lower limit threshold value, the third compute device not included in the third group of compute devices.

5. The apparatus of claim 1, wherein the processor is further configured to: (0) (2)

6. The apparatus of claim 1, wherein the processor is further configured to: (0) (2)

7. The apparatus of claim 1, wherein the processor is further configured to: (0) (1)

8. A non-transitory processor-readable medium storing code representing instructions to be executed by a processor, the code comprising code to cause the processor to: (8) (4)

designate, at a compute device from a plurality of compute devices that implements a distributed database, a first group of compute devices from the plurality of compute devices as lazy compute devices, a second group of compute devices from the plurality of compute devices being non-lazy compute devices, the second group of compute devices being an absolute complement of the first group of compute devices with respect to the plurality of compute devices;

receive, from a set of compute devices from the plurality of compute devices, a first set of events, each event from the first set of events defined by a compute device from the plurality of compute devices;

identify an order associated with a second set of events as a result of a consensus protocol (1) using a parameter of a first event from the first set of events based on the first event being defined by a compute device from the second group of compute devices, and (2) not using the parameter of a second event from the first set of events based on the second event being defined by a compute device from the first group of compute devices; and

store the order associated with the second set of events.

9. The non-transitory processor-readable medium of claim 8, further comprising code to cause the processor to: (0) (1)

10. The non-transitory processor-readable medium of claim 8, wherein the code to cause the processor to designate includes code to cause the processor to select the first group of compute devices from the plurality of compute devices using a deterministic pseudorandom function. (0)

11. The non-transitory processor-readable medium of claim 8, wherein each event from the first set of events is associated with a common round. (0)

12. The non-transitory processor-readable medium of claim 8, wherein the code to cause the processor to designate includes code to cause the processor to designate for a first round of the consensus protocol, the code further comprising code to cause the processor to: (0) (1)

13. The non-transitory processor-readable medium of claim 8, wherein the code to cause the processor to designate includes code to cause the processor to select the first group of compute devices from the plurality of compute devices based on an amount of stake associated with each compute device from the plurality of compute devices. (0)

14. The non-transitory processor-readable medium of claim 8, wherein the parameter of the first event from the first set of events is determined using a first method and the parameter of the second event from the first set of events is determined using a second method different from the first method. (0)

15. The non-transitory processor-readable medium of claim 8, wherein the compute device from the plurality of compute devices is a first compute device from the plurality of compute devices, the code further comprising code to cause the processor to: (0) (2)

16. The non-transitory processor-readable medium of claim 8, wherein a first event from the second set of events was defined by a compute device from the first group of compute devices and a second event from the second set of events was defined by a compute device from the second group of compute devices. (0)

17. A method, comprising: (7) (7)

identifying, at a compute device from a plurality of compute devices that implements a distributed database, a first group of compute devices from the plurality of compute devices and a second group of compute devices from the plurality of compute devices, the second group of compute devices being an absolute complement of the first group of compute devices with respect to the plurality of compute devices;

receiving, from a set of compute devices from the plurality of compute devices, a first set of events, each event from the first set of events defined by a compute device from the plurality of compute devices;

identifying, using a first process, a round number for each event from the first set of events that was defined by a compute device from the first group of compute devices;

identifying, using a second process different from the first process, a round number for each event from the first set of events that was defined by a compute device from the second group of compute devices;

determining a subset of events from the first set of events based on the round number for each event from the first set of events, each event from the subset of events being defined by a compute device from the second group of compute devices;

calculating an order associated with a second set of events as a result of a consensus protocol using the subset of events; and

storing the order associated with the second set of events.

18. The method of claim 17, further comprising: (0) (1)

19. The method of claim 17, wherein the first process includes identifying the round number for each event from the first set of events as equal to a round number of at least one parent event for that event from the first set of events. (0)

20. The method of claim 17, wherein the round number for each event from the subset of events is an initial instance that a compute device defining that event has defined an event with the round number. (0)

21. The method of claim 17, wherein the identifying the first group of compute devices includes identifying the first group of compute devices from the plurality of compute devices using a deterministic pseudorandom function. (0)

22. The method of claim 17, wherein the identifying the first group of compute devices includes identifying the first group of compute devices for a first round of the consensus protocol, the method further comprising: (0) (1)

23. The method of claim 17, further comprising: (0) (2)

24. The method of claim 17, further comprising: (0) (2)

View Abstract and Specification Size

PDF with Images and Document Face >

Full Text Publication >

Application US20200145387

METHODS AND APPARATUS FOR EFFICIENTLY IMPLEMENTING A DISTRIBUTED DATABASE WITHIN A NETWORK

Patent Matrix® Search