Methods and apparatus for a distributed database within a network

• US 9,529,923 B1
• Filed: 05/12/2016
• Issued: 12/27/2016
• Est. Priority Date: 08/28/2015
• Status: Active Grant

• Current Assignee: Hedera Hashgraph LLC
• Original Assignee: Swirlds, Inc.
• Inventors: Baird, Leemon C. III
• Primary Examiner(s): Spieler, William
• Application Number:
  US15/153,011
• Time in Patent Office: 229 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/182 Distributed file systems
• CPC Class Codes: G06F 16/1834 implemented based on peer-to-peer networks, e.g. gnutella p2p communication protocols H04L67/104
• CPC Class Codes: G06F 16/1837 Management specially adapted to peer-to-peer storage networks topology management mechanisms of peer-to-peer networks H04L67/1042
• CPC Class Codes: G06F 16/184 implemented as replicated file system
• CPC Class Codes: G06F 16/1844 Management specifically adapted to replicated file systems
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 16/273 Asynchronous replication or reconciliation
• CPC Class Codes: G06F 16/275 Synchronous replication
• CPC Class Codes: G06F 9/542 Event management; Broadcasting; Multicasting; Notifications
• CPC Class Codes: 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]

Abstract

In some embodiments, an apparatus includes an instance of a distributed database at a first compute device configured to be included within a set of compute devices that implement the distributed database. The apparatus also includes a processor configured to define a first event linked to a first set of events. The processor is configured to receive, from a second compute device from the set of compute devices, a signal representing a second event (1) defined by the second compute device and (2) linked to a second set of events. The processor is configured to identify an order associated with a third set of events based at least one a result of a protocol. The processor is configured to store in the instance of the distributed database the order associated with the third set of events.

Claims

1. An apparatus, comprising:

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

a processor operatively coupled to the instance of the distributed database,

the processor configured to define, at a first time, a first event linked to a first plurality of events, each event from the first plurality of events being a sequence of bytes,

the processor configured to receive, at a second time after the first time and from a second compute device from the plurality of compute devices, a signal representing a second event (1) defined by the second compute device and (2) linked to a second plurality of events, each event from the second plurality of events being a sequence of bytes,

the processor configured to identify an order associated with a third plurality of events based at least on a result of a protocol, each event from the third plurality of events being from at least one of the first plurality of events or the second plurality of events,

each event from the third plurality of events being associated with a set of attributes, the result of the protocol includes a value for each attribute from the set of attributes for each event from the third plurality of events,

the value for a first attribute from the set of attributes for each event from the third plurality of events including a first numeric value and the value for a second attribute from the set of attributes for each event from the third plurality of events including a binary value associated with the first numeric value,

the binary value for the second attribute for an event from the third plurality of events being based on whether a relationship between that event and a first set of events linked to that event satisfies a criterion,

each event from the first set of events being (1) an ancestor of the event from the third plurality of events and (2) associated with a first common attribute as the remaining events from the first set of events, the first common attribute indicative of an initial instance that a first event defined by each compute device from the plurality of compute devices is associated with a particular value,

the value for a third attribute from the set of attributes including a second numeric value based on a relationship between the event from the third plurality of events and a second set of events linked to the event from the third plurality of events,

each event from the second set of events being a descendant of the event from the third plurality of events and associated with a second common attribute as the remaining events from the second set of events,

the processor configured to store in the instance of the distributed database the order associated with the third plurality of events.

2. The apparatus of claim 1, wherein the processor is configured to alter a state associated with the distributed database based on the order associated with the third plurality of events.

3. The apparatus of claim 1, wherein

the criterion is based on a comparison of a quantity of events from the first set of events to a threshold value based on a quantity of compute devices from the plurality of compute devices.

4. The apparatus of claim 1, wherein

the criterion is based on a comparison of a combination of weighted values associated with each event from the first set of events to a threshold value defined based on a combination of weighted values associated with each compute device from the plurality of compute devices.

5. The apparatus of claim 1, wherein the particular value is a first particular value,

the second common attribute being associated with (1) a third common attribute indicative of an initial instance that a second event defined by each compute device from the plurality of compute devices is associated with a second particular value different from the first particular value and (2) a result based on a set of indications, each indication from the set of indications associated with an event from a third set of events, each event from the third set of events being associated with a fourth common attribute indicative of an initial instance that a third event defined by each compute device from the plurality of compute devices is associated with a third particular value different from the first particular value and the second particular value.

6. The apparatus of claim 1, wherein the particular value is a first particular value,

the second common attribute being associated with (1) a third common attribute indicative of an initial instance that a second event defined by each compute device from the plurality of compute devices is associated with a second particular value different from the first particular value and (2) a result based on a set of indications, each indication from the set of indications associated with an event from a third set of events, each event from the third set of events being associated with a fourth common attribute indicative of an initial instance that a third event defined by each compute device from the plurality of compute devices is associated with a third particular value different from the first particular value and the second particular value,

the first particular value being a first integer,

the second particular value being a second integer greater than the first integer,

the third particular value being a third integer greater than the second integer.

7. An apparatus, comprising:

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

a processor operatively coupled to the instance of the distributed database,

the processor configured to receive a signal representing an event linked to a plurality of events, each event from the plurality of events is associated with a set of attributes,

the processor configured to identify an order associated with the plurality of events based at least on a result of a protocol,

the result of the protocol includes a value for each attribute from the set of attributes for each event from the plurality of events, the value for a first attribute from the set of attributes for each event from the plurality of events including a numeric value and the value for a second attribute from the set of attributes for each event from the plurality of events including a binary value associated with the numeric value,

the binary value for the second attribute for an event from the plurality of events being based on whether a relationship between that event and a first set of events linked to that event satisfies a criterion,

each event from the first set of events being (1) an ancestor of the event from the plurality of events and (2) associated with a first common attribute as the other events from the first set of events, the first common attribute indicative of an initial instance that a first event defined by each compute device from the plurality of compute devices is associated with a particular value,

the value for a third attribute from the set of attributes including a second numeric value based on a relationship between the event from the plurality of events and a second set of events linked to the event from the plurality of events,

each event from the second set of events being a descendant of the event from the plurality of events and associated with a second common attribute as the remaining events from the second set of events,

the processor configured to store in the instance of the distributed database the order associated with the plurality of events.

8. The apparatus of claim 7, wherein the particular value is a first particular value,

the second common attribute being associated with (1) a third common attribute indicative of an initial instance that a second event defined by each compute device from the plurality of compute devices is associated with a second particular value different from the first particular value and (2) a result based on a set of indications, each indication from the set of indications associated with an event from the second set of events and an event from a third set of events, each event from the third set of events being associated with a fourth common attribute indicative of an initial instance that a third event defined by each compute device from the plurality of compute devices is associated with a third particular value different from the first particular value and the second particular value,

each indication from the set of indications being a binary value based on whether the event from the third set of events is a descendant of the event from the second set of events.

9. The apparatus of claim 7, wherein the particular value is a first particular value,

the second common attribute being associated with (1) a third common attribute indicative of an initial instance that a second event defined by each compute device from the plurality of compute devices is associated with a second particular value different from the first particular value and (2) a result based on a set of indications, each indication from the set of indications associated with an event from the second set of events and an event from a third set of events, each event from the third set of events being associated with a fourth common attribute indicative of an initial instance that a third event defined by each compute device from the plurality of compute devices is associated with a third particular value different from the first particular value and the second particular value, the result based on a relationship between the third set of events and a fourth event associated with a fourth particular value different from the first particular value, the second particular value, and the third particular value.

10. The apparatus of claim 7, wherein the particular value is a first particular value,

the second common attribute being associated with (1) a third common attribute indicative of an initial instance that a second event defined by each compute device from the plurality of compute devices is associated with a second particular value different from the first particular value and (2) a result based on a set of indications, each indication from the set of indications associated with an event from the second set of events and an event from a third set of events, each event from the third set of events being associated with a fourth common attribute indicative of an initial instance that a third event defined by each compute device from the plurality of compute devices is associated with a third particular value different from the first particular value and the second particular value, the result based on a relationship between the third set of events and a fourth event, the fourth event being associated with a binary value configured to change based on the result.

11. 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:

receive a signal representing an event linked to a plurality of events;

identify an order associated with the plurality of events based on a round associated with each event from the plurality of events and an indication of when to increment the round associated with each event by;

associating each event from the plurality of events with a set of events from a plurality of sets of events, each set of events from the plurality of sets of events associated with a common round;

identifying, for each set of events from the plurality of sets of events, a subset of events from that set of events, each event from that subset of events being an initial instance that an event defined by each compute device from the plurality of compute devices is associated with the common round;

identifying a binary attribute of each event from that subset of events based on a relationship of that event in that subset of events to the remaining events from the plurality of events;

identifying, for an event from that subset of events, a received round value based on a relationship between that event and a set of events having a positive value for the binary attribute; and

identifying the order associated with the plurality of events based at least on the received round value of that event; and

store, in an instance of a distributed database at a first compute device configured to be included within a plurality of compute devices that implements the distributed database via a network operatively coupled to the plurality of compute devices, the order associated with the plurality of events, the instance of the distributed database operatively coupled to the processor.

12. The non-transitory processor-readable medium of claim 11, the code further comprising code to cause the processor to:

alter a state associated with the distributed database based on the order associated with the plurality of events.

13. The non-transitory processor-readable medium of claim 11, wherein the associating each event from the plurality of events with a set of events from the plurality of sets of events is based on a relationship between that event and a group of events linked to that event satisfying a criterion,

the criterion being based on a comparison of a quantity of events from the group of events to a threshold value defined based on a quantity of compute devices from the plurality of compute devices.

14. The non-transitory processor-readable medium of claim 11, wherein the associating each event from the plurality of events with a set of events from the plurality of sets of events is based on a relationship between that event and a group of events linked to that event satisfying a criterion,

the criterion being based on a comparison of a combination of weighted values associated with each event from the group of events to a threshold value defined based on a combination of weighted values associated with each compute device from the plurality of compute devices.