SYSTEMS AND METHODS FOR DISTRIBUTED RESOURCE ALLOCATION

Abstract

Resource allocation systems (aka distributed ledgers) can overcome scalability issues while still ensuring both that system resource amounts are not corrupted and that resource recipients can trust in resources delivered to them by requiring distributed nodes maintaining account histories—in return, for instance, for transaction fees—to probabilistically verify transaction history and maintain reserve resources in their own accounts for the repair of transactions impaired by invalid previous transactions. Even in a permissionless environment, such systems can maintain eventual consistency of transaction history without impairment of the accounts of non-maintaining users.

Claims

1. A computing device of a resource allocation system, the computing device comprising: at least one processor; and at least one non-transient, computer-readable storage medium having encoded thereon instructions which, when executed by the at least one processor, program the at least one processor to determine if a proposed transaction is impaired by lack of resource, at least in part by: selecting, probabilistically, one or more previous transactions from a transaction history recorded in the resource allocation system (or selecting with certainty when transaction history contains only one element); determining whether the one or more previous transactions are valid; and determine whether the proposed transaction is impaired, wherein the proposed transaction is determined to be impaired if it is determined that at least one previous transaction is invalid.

2-4. (canceled)

5. The computing device of claim 1, wherein: the resource is a selected type of resource used in the proposed transaction; the proposed transaction comprises a transfer of an amount of the selected type of resource out of one or more source accounts; and the one or more previous transactions are selected from a plurality of previous transactions that are traceable from the one or more source accounts.

6. (canceled)

7. The computing device of claim 5, wherein: the proposed transaction comprises a first transaction; the one or more source accounts comprise one or more first source accounts; the amount of the selected type of resource comprises a first amount of the selected type of resource to be transferred out of the one or more first source accounts; the plurality of previous transactions that are traceable from the one or more source accounts comprise a second transaction that transferred a second amount of the selected type of resource out of a second source account; and the plurality of previous transactions that are traceable from the one or more source accounts further comprise a third transaction that took place before the second transaction, the third transaction transferring a third amount of the selected type of resource into the second source account.

8. The computing device of claim 5, wherein selecting, probabilistically, one or more previous transactions comprises associating, with each of the one or more previous transactions, a respective probability based on an amount of the respective previous transaction relative to a total amount of the one or more previous transactions considered for selection.

9. The computing device of claim 5, wherein selecting, probabilistically, one or more previous transactions comprises associating, with each of the one or more previous transactions, a respective probability based on an amount that the previous transaction transferred into a target account relative to a total amount that the one or more previous transactions transferred into the target account.

10. The computing device of claim 5, wherein a total amount of checking by selection of the one or more previous transactions is based on a resource budget for checking, and the resource budget is determined based on the amount of the selected type of resource to be transferred in the proposed transaction.

11-14. (canceled)

15. The computing device of claim 1, wherein the transaction history comprises a plurality of transaction history replicas of a plurality of accounts; the at least one processor comprises a plurality of computing nodes which share responsibility for maintaining the plurality of accounts; the proposed transaction comprises transferring out of at least one source account; the source account replica nodes constitute one or more computing nodes from the plurality of computing nodes which share responsibility for maintaining the plurality of accounts, which are responsible for maintaining transaction history replicas of the at least one source account; the source account replica nodes are further programmed to independently select some of the one or more selected previous transactions, and obtain data from source accounts of the one or more selected previous transactions by querying one or more computing nodes responsible for maintaining the source accounts of the one or more selected previous transactions; at least one of the source account replica nodes independently determines whether the one or more previous transactions selected by the computing node are valid; and determining whether the proposed transaction is impaired comprises forming a quorum of source account replica nodes, wherein a joint result of the quorum is used to determine whether the proposed transaction is impaired.

16. The computing device of claim 15, wherein the quorum comprises the quorum of source account replica nodes; and at least one quorum node is further programmed to memorialize, in a transaction log, a consensus of the quorum with respect to the proposed transaction.

17. The computing device of claim 16, wherein the at least one processor additionally comprises a plurality of log nodes; and each node in the quorum has at least one associated log node responsible for collecting a log from the computing node in the quorum.

18-20. (canceled)

21. The computing device of claim 1, wherein the at least one processor is further programmed to: in response to determining that at least one previous transaction of the one or more previous transactions are invalid, modify the transaction history in the resource allocation system at least in part by replacing the at least one previous transaction with one or more substitute transactions.

22. The computing device of claim 21, wherein: the at least one previous transaction that is determined to be invalid comprises a transfer of a first amount of the selected type of resource out of a first source account; the at least one previous transaction is determined to be invalid in response to determining that a balance of the first source account was deficient by a second amount to support the transfer of the first amount; and replacing the at least one previous transaction with one or more substitute transactions comprises reducing the first amount transferred from the first source account by the second amount, and adding one or more other source accounts among which the second amount is apportioned.

23. The computing device of claim 22, wherein: the resource allocation system is maintained by a plurality of nodes; and the other one or more source accounts comprise at least one source account associated with a node that, acting as a replica for the first source account, accepted the at least one previous transaction that is determined to be invalid.

24. The computing device of claim 22, wherein: the resource allocation system is maintained by a plurality of nodes; the one or more other source accounts comprise one or more source accounts associated with a node that processed the at least one previous transaction that is determined to be invalid, and which are collectively responsible for a third amount, which is a portion of the second amount which constitutes a maximum amount supported by balances of the one or more other source accounts; and a difference between the second amount and the third amount is distributed among, and in sum removed from, one or more target accounts of the at least one previous transaction and/or one or more target accounts of subsequent transactions from the first source account; and the resource allocation system is further programmed to, in response to determining that another previous transaction becomes invalid as a result of repairing the at least one previous transaction, repair the other previous transaction.

25. The computing device of claim 23, wherein: the resource allocation system is further programmed, such that there are accounts associated with nodes; and nodes, managing each other's accounts reciprocally, are programmed to require that the accounts of other nodes which they manage maintain a minimum amount of resources.

26. The computing device of claim 22, wherein: the transaction history comprises a plurality of transaction history replicas of a plurality of accounts; the at least one processor comprises a plurality of computing nodes which share responsibility for maintaining the plurality of accounts; the first source account replica nodes constitute one or more computing nodes from the plurality of computing nodes which share responsibility for maintaining the plurality of accounts, which are responsible for maintaining transaction history replicas of the at least one source account; the one or more other source accounts comprise second source accounts associated with first source account replica nodes that accepted the at least one previous transaction that is determined to be invalid; the second amount is divided into a covered amount which is the total amount not more than the second amount supported by balances of the second source accounts, and a residual amount, which is any remainder once the covered amount has been deducted from the second amount; the second source account replica nodes constitute one or more computing nodes from the plurality of computing nodes which share responsibility for maintaining the plurality of accounts, which are responsible for maintaining transaction history replicas of the second source accounts; the third source accounts comprise accounts associated with the second source account replica nodes; and the resource allocation system is further programmed so that the residual amount is apportioned among the third source accounts.

27-28. (canceled)

29. The computing device of claim 26, wherein: nodes which manage account history replicas comprise first replica nodes; the accounts of first replica nodes comprise first replica node accounts; the nodes which manage account history replicas of first replica node accounts comprise second replica nodes; and the resource allocation system is further programmed so that first replica nodes periodically ask for permission from second replica nodes to process transactions on the accounts whose history the first replica nodes manage.

30. The computing device of claim 1, which is additionally programmed to determine whether any of several proposed transactions are impaired, by following the procedure of the resource allocation system of claim 1, but using information retrieved by this process to determine whether any of the proposed transactions is impaired.

31-35. (canceled)

36. A computing device comprising: at least one processor; and at least one non-transient, computer-readable storage medium having encoded thereon instructions which, when executed by the at least one processor, program the at least one processor to determine if previous transactions are invalid because of lack of resource, at least in part by: selecting, probabilistically, one or more previous transactions from a transaction history recorded in a resource allocation system; and determining whether the one or more previous transactions are valid.

37-40. (canceled)

41. The computing device of claim 29, wherein the second source account replica nodes comprise the first level of chained replica nodes; the chained replica nodes of level greater than one constitute nodes who are responsible for maintain account replicas of chained replica nodes of the preceding level; and the system is further programmed so that, up to some level, chained replica nodes of previous levels periodically ask permission from nodes of subsequent levels to grant permission to lower levels.

42. (canceled)

43. The computing device of claim 29, wherein the permission to process transactions functions as a type of resource managed by the resource allocation system.

44-45. (canceled)

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0073] The accompanying drawings are not intended to be drawn to scale. In the drawings, each identical or nearly identical component that is illustrated in various figures is represented by a like numeral. For purposes of clarity, not every component may be labeled in every drawing. In the drawings:

[0074] FIG. 1 is a diagram showing the relation between proposed transaction, accounts, and previous transactions, according to some embodiments;

[0075] FIG. 2 shows a system and illustrates storage of account history replicas, according to some embodiments;

[0076] FIG. 3 shows a system and illustrates the relation between replica nodes and log nodes, according to some embodiments;

[0077] FIG. 4 shows a diagram showing repair of an invalid transaction, according to some embodiments;

[0078] FIG. 5 shows a diagram showing chaining of responsibility for invalid transactions, according to some embodiments; and

[0079] FIG. 6 is a block diagram of the system according to some embodiments.

DETAILED DESCRIPTION

1. Distributed Ledgers and Resource Allocation Systems

[0080] In some embodiments, a resource allocation system (“RAS”) may keep track of some valuable resource over time, while responding to orders from a plurality of parties to move, create, destroy or transform some or all of some type(s) of resource. In some embodiments, a RAS may use a distributed ledger to keep track of one or more types of resource. However, it should be appreciated that aspects of the present disclosure are not limited to using distributed ledgers, as discussed in the background, to keep track of a financial resource, and are not limited to distributed systems. The inventor has recognized and appreciated that resource allocation systems are not limited to financial resources, and thus may address other types of resources. Any one or more type of resource may be tracked. For instance, provision and/or consumption of electric power at given time periods may be tracked by a system, which may ensure an adequate allocation of electricity flows between producers and consumers. Alternatively, or additionally, for instance, one or more capacities of a computer network, such as computing, storage or messaging capacity, may be tracked, and may be allocated among computational tasks which consume such resource. Some embodiments of resource allocation systems may track types of resource created for the purpose of measuring and/or improving the function of some larger computing system, such as, for instance, systems of awards or penalties for nodes or system users as their actions are judged to cooperate or impede the functioning of the overall system. Some embodiments of a resource allocation system may track a resource implicitly as a cost or value function associated with some larger system: for instance, the number of nodes or other resources used by the system, and/or used by/attributable to parts of the system.

[0081] Some embodiments of the present invention can be seen as the application of the distributed-storage notion of eventual consistency [BG2013] to distributed ledgers or resource allocation system, while taking advantage of the specialized nature of resource allocation to improve on its usefulness.

[0082] In some embodiments, resource may be moved between accounts. An account may be identified in any suitable manner, for example, based on a network location, a cryptographic key, or another mechanism for account identification. An amount and type of resource held in an account may be represented in any suitable manner. For instance, an amount of resource may be represented directly (e.g., using numerical values, or, for different types, an associative map of type identifier to numerical value). Additionally, or alternatively, an amount of resource may be represented indirectly (e.g., based on a probability of the amount of resource being present, or based on evidence of a presence or absence of the amount of resource). It should be appreciated that aspects of the present disclosure are not limited to representing amounts numerically. Any system is a resource allocation system independent of the specific representations of resources—which are termed here amounts, but can contain arbitrary information—as long as they can be combined and compared, such that: (i) if a first amount may be accounted not less than a second amount, and the second amount may be accounted not less than a third amount, then the first amount may be accounted not less than the third amount; and (ii) if a first amount may be accounted not less than a second amount, and a third amount may be accounted not less than a forth amount, then a sum of the first and third amount may be accounted to be not less than a sum of the second and forth amount.

[0083] For example, a resource allocation system may record the permission to use a resource which is imperfectly transferrable. For instance, a peer-to-peer car sharing service may foresee the responsibility of users to maintain a car during the time they are allowed to use the vehicle. If they transfer some or all of the time to other users, some additional uncertainty may accrue as to the state of resource as it is transferred. Hence the representation of the permission to use includes the identifier for the underlying resource together with a string of names of previous holders, and the act of combining a set of previously held permissions with a set of newly transferred permissions may involve accounting for a slight degradation of the value of the incoming permissions by a representation of the uncertainty accumulated during the transfers. Comparison and combination still accord to the stipulations expressed above.

[0084] In some embodiments of a RAS, a resource may not be transferrable between different parts of the system. For instance, the “accounts” may simply be data objects, and the resource the size or the importance of the objects. In such cases, it may not be possible to transfer resources from one account to another. Such systems still embody a RAS if transactions are subject to some consistency constraint with respect to the resource. For instance, if objects have importance, a system such as an object cache may constrain transactions so as to never decrease the sum importance of objects. Many computational systems, even if they are not RASes overall, nevertheless contain them as critical components. In the description below, in cases where the resource is a computed attribute of some object or part of the system, “account” may mean the object and/or part, from which the value of the resource can be calculated (The resource value may, but need not be explicitly stored.) An account transaction history in such cases may be the history of transactions that modify and/or involve that object and/or part, from which the value and/or changes in the value of the resource may be calculated, whether or not it is explicitly stored.

[0085] It should be appreciated that aspects of the present disclosure apply not only to systems in which resource allocation is a central purpose, but to those in which resource allocation, or the allocation of quantities and/or tokens whose value may be assigned by convention, serves as a book keeping device in the service of some other goal. For instance, in some embodiments the purpose of the system may be the storage and maintenance of arbitrary data. For instance, a database system may use a resource and/or resource-like entity and/or measure to govern the amount of verification done on a particular transaction and/or by a particular node in the system.

2. Probabilistic Transaction Verification in RAS

[0086] Some RASes, linearize all actions in order to avoid inconsistent behavior. Some RAS implementations attempt to ameliorate scalability problem by sharding data and using a divide and conquer strategy of linearizing within and then among shards. The inventor has recognized and appreciated that ensuring consistency by linearizing all transactions in resource allocation systems may create a bottleneck to scalability, and that sharding is of limited effectiveness at overcoming such a bottleneck. Nevertheless, the inventor has recognized and appreciated that it may be desirable to provide a RAS with a mechanism for identifying and eliminating inconsistent transactions (for instance, if the transactions reduce an account balance to below a selected threshold). Accordingly, in some embodiments, techniques are provided that maintain a partial order among transactions, and verify, possibly partially or probabilistically, that a given new transaction which transfers resource between two or more accounts is consistent by checking previous transactions from source accounts. In some embodiments the verification check uses a probabilistic probe of previous transactions. It should be appreciated that the notion of previous in a RAS may but need not refer to clock time, but may mean previous in terms of effective order of operations at one or more of the computing nodes involved in the RAS. In cases where the order of some given operations is unknown or not specified, previous may mean “not following” in terms of the order induced, possibly transitively, by any other operations whose order is known and whose order or simultaneity with regard to the given operations is known, specified and/or postulated.

[0087] In some embodiments, the amount of resource in an account is determined by the transaction history of properly formed (for instance, cryptographically signed) transactions to and from the account recorded in the transaction history of the account, possibly augmented by an initial balance. In some embodiments, a transaction which has been recorded properly as determined by the rules of the particular embodiment may be termed accepted. In some embodiments, a valid transaction may be one in which the amount of resources in source accounts is enough so that the amount of resources in any of the source accounts does not fall under the minimum amount for those source accounts. In some embodiments, an invalid transaction may be a transaction that is not valid. In some embodiments, an impaired transaction may be a transaction in which the amounts in source accounts are such that the transaction should be valid, but for which the transitive closure of the transactions upon which the amounts in the source accounts depend includes an invalid transaction.

[0088] In some embodiments, given a proposed transaction, Tp, the system may choose at random from among all of the previous transactions, and verify that that the account(s) from which that transaction transfer resource had sufficient amount of appropriate resource type to do so. If it does not, then the system has discovered that it is in an inconsistent state, and may undertake various of several actions discussed below, such as, for instance repair, and/or putting the current and/or other transactions on hold. Whatever variant is chosen, if the random choice is made uniformly, then a given previous transaction is checked with probability 1/d when there are d total previous transactions in the system, and therefore is checked unboundedly often with a probability approaching certainty as the number of previous transactions continues to grow. This property, or a similar one, is preserved, or preserved under some conditions, by many of the variants discussed below.

[0089] In some embodiments, the previous transactions checked may be related to the proposed transaction. FIG. 1 shows a diagram 100 of example of previous transactions 101, 102, 103, . . . 114 between accounts 151, 152, . . . 160, as well as a proposed transaction 120. The system may maintain a local transaction history for each account. The local transaction history may include all incoming and outgoing transactions pertaining to the account, and the transactions may be linearly ordered (e.g., based on the order in which they were accepted). In some embodiments, however, the local transaction history may not be linear. Rather, in some embodiments, the system may accept a set of transactions for a given account if there exists some order for which no outgoing transaction causes the account's balance to fall below some selected threshold. For instance, if, while considering and/or within a certain period after considering a given transaction which would in isolation reduce the balance of an account to below a given threshold, another transaction is presented such that the balance of the account, when the two transactions are taken together, is maintained at the level equal to or above the threshold, then the set of transactions may be deemed valid regardless of the order that the transactions were presented.

[0090] In some embodiments, to verify that a proposed transaction from an account is not impaired, given the apparent account balance, which, in turn, depends on the amounts, types and validity of incoming and outgoing transactions, the system checks probabilistically among incoming transactions the account. For instance, with reference to proposed transaction 120 from account 151 in diagram 100, they system might decide to check either or both of previous transactions 101 and 102 with a given probability, and conditioned on the choice of transaction 101, it may go on to choose which of transactions 103, 104 to check, possibly then checking one or both of transactions 111, 112 as a result.

[0091] In some embodiments, given a transaction Ti with a source account Aj the system may check whether Aj held a sufficient amount of resource when Ti was proposed. For instance, Ti may be considered invalid if a balance of all incoming and outgoing transactions in the transaction history of Aj, up to a point at which Ti was proposed, was insufficient to support Ti (e.g., Ti caused Ajs balance to fall below a selected threshold).

[0092] In some embodiments, a transaction Ti with source account Am may be considered impaired if some of the resources in account Am deemed to be present before the transaction can be traced backward via a path of transactions ending at Am to an invalid transaction Tj.

[0093] In some embodiments, the system may select one or more incoming transactions of Aj at random from all incoming transactions recorded in Ajs account history before Ti, and check whether these transactions are impaired. In some embodiments, this validity check may involve checking whether a selected incoming transaction Tk (with source account Al) is invalid. In some embodiments, this validity check may involve recursively checking whether any incoming transaction of Al that happened before Tk is impaired.

[0094] In some embodiments, the system may choose a transaction uniformly at random from all incoming transactions. In this manner, it may ensure that every transaction is checked an expected number of times which grows without bound as the number of transactions in the account grows. In some embodiments, the system may weigh more recent transactions more heavily than less recent transactions. For instance, if there are n transactions, the system may choose the kth most recent transaction (k>=1) with probability

[00001]$\frac{1}{\log \left(k+1\right)}*\frac{n}{.Math.\frac{1}{\log \left(1+i\right)}}$

where the sum is over i ranging from 1 to n. In such a manner, by choosing a method according to which the sums of the probabilities by which a given transaction is chosen diverge, while also weighting more recent transactions more highly, the system may ensure that (i) a given transaction is checked without bound in expectation as the number of transactions in a given account grows, while also (ii) limiting the growth, as a function of the total number of transactions in an account, in the lag before which a given transaction is checked a given number of times.

[0095] In some embodiments, the system nodes may probabilistically check all transactions and/or all accounts which they are aware of. They may perform these checks at a given rate, in response to new transactions and/or in the background—for instance, during periods of lower system activity. In some embodiments, the system may weigh the choice of transaction by the size of the transaction.

[0096] On discovery of an impaired transaction, various actions may be taken. In some embodiments, for instance, the impaired transaction may be put on hold while other actions are taken. In some embodiments, additional random checks on source accounts may be performed when a transaction is found to be impaired. In this manner, the total amount of resource actually present, after removing any amounts purportedly transferred without resources having been available, may be estimated, and the transaction may be marked as invalid if it is estimated that sufficient resources are not available for it because of impairment. Further actions may be based on probabilities or other quantities calculated during this estimation procedure. In some embodiments, repair of the invalid transaction (discussed below) may allow the impairment to be removed. In some embodiments, when an invalid transaction is found in the history of a given proposed transaction, repair and additional random checks may be conducted in parallel, with the proposed transaction proceeding when it has reached a threshold of certainty that it is not invalid, either by repair or by additional checks on other transactions, while repair of invalid transactions discovered can proceed asynchronously even after the main transaction is cleared.

3. Replication

[0097] In some embodiments, responsibility for record storage and acceptance of transactions for accounts may be distributed among different computing nodes, which may replicate some or all the data. In the following, a replica node is a node that stores a replica of certain data, such as data that comprises an account record. The copy of the data itself will be denoted as replica data—for example a replica account. A replica node together with the replica account data is known simply as a replica. In some embodiments, each account may have associated therewith one or more replica nodes that maintain a transaction history for the account. In this manner, the system may continue to function even if one or several nodes fail, and the actions of faulty or malicious nodes may be overcome. It should be appreciated that a given computing node may serve as the replica node for possibly many different accounts; when speaking of a replica node for an account, we regard the node in its role as replica node for that account, but do not preclude other functions within the RAS or other system, such as serving to replica data for other accounts, and/or to perform other operations such as, for example, logging.

[0098] To accept a transaction, replica nodes may use a system which chooses subset of replica nodes, called a quorum, which is possibly but not necessarily a majority of them, and which is chosen using a consensus protocol to make decisions with regard to data changes, such as approval or rejection of a transaction. The literature contains many possible consensus protocols (e.g., a Byzantine agreement protocol). In some embodiments, a quorum may use a threshold signature or other cryptographic techniques to sign transactions, and/or to prove that one transaction immediately follows its predecessor; for instance, it may use techniques as detailed in [KG2009]. In this manner, any node querying an account's transaction history may be assured that no node has omitted an outgoing transaction or misrepresented an incoming transaction without the collaboration of a quorum of its peers.

[0099] In some embodiments, replica nodes, before agreeing to join a quorum for the acceptance of a transaction, may check account histories using independent random choices. In this manner, impaired transactions may be more easily uncovered.

[0100] FIG. 2 shows an example system 200, according to some embodiments, having six accounts, namely accounts 210, 220, 230, 240, 250, and 260. Each account has five account replicas with each replica at an identified replica node. Specifically account 210 has a replica at each of nodes 211, 212, 213, 214, and 215; account 220 has replicas at nodes 221, 222, 223, 224, and 225; account 230 has account replicas at replica nodes 231, 232, 233, 234, and 235; account 240 has replicas at nodes 241, 242, 243, 244, and 245; account 250 has replicas at nodes 251, 252, 253, 254, and 255; and account 260 has account replicas at nodes 261, 262, 263, 264, and 265. Arrows 271-287 represent the one or more actions that may be performed in response to a proposed transaction from account 210. It should be appreciated that the choice of six accounts with five nodes each is illustrative; there may be any suitable number of accounts and each account may have any suitable number of nodes. Each node, given its local knowledge of a transaction history of an account, independently choses a node controlling replicas of other accounts. For instance, node 213 may have chosen to verify the status of incoming transactions from accounts 220 and 230 with nodes 223 and 234, respectively (see arrows 273 and 275). The chain of verification may then proceed to the verification of transactions from accounts 4 and 5 (arrows 279 and 287).

[0101] In some embodiments, verification may be carried out by original nodes (for example, 213 and other replica nodes of account 210) requesting records from account histories maintained by subsequent nodes (e.g., nodes 223 and 234), and performing additional random selections from the retrieved account histories itself. In other embodiments, original nodes may not retrieve account histories, retrieving, for example hashes or samples to ensure integrity, and instead delegate one or more sub-verification steps to nodes that store or have direct access to that history, e.g., node 213 could delegate the checking of transactions of account 220 to a replica node for that account.

[0102] In some embodiments, the number of replicas serving each account may be a fixed property of the system. In other embodiments, the number of replicas may vary. For instance, the number of replicas may be chosen or adjusted so as to vary according to, and/or be roughly proportional to a statistic calculated on the resource or change in resources in the account. For instance, it can be chosen so as to be proportional to, and/or to vary according to, the amount of resource in the account, a moving average amount over time, and/or a moving average over time of the amount and/or sum of transaction amounts, and/or other statistic. In some embodiments, the number of replicas serving a given account may depend on other system properties. For instance, the system may adjust it to reflect network connectivity, throughput and/or latency data of replica nodes, and/or some other statistic which reflects the reliability and/or availably of the nodes.

[0103] In some embodiments, the number of replicas who participate in a quorum accords with the choice of consensus protocol, as above. In other embodiments, smaller quorums may be able to accept transactions in conditions specified by the system. For instance, if replica nodes themselves commit resource into escrow, the system may allow them to accept small transactions, and/or transactions smaller than the amount of escrow they have set aside, without building a full quorum. If, for instance, the transaction turns out to be impossible because of other conflicting transactions, the system may create a transaction from the escrow, to cover whatever portion of the transaction may be in conflict. In this manner, nodes operators may choose to accept risk when that risk is small and/or when it is manageable in relation to their escrow, in return for a larger share of any transaction fees.

[0104] In some embodiments, after a quorum accepts an outgoing transaction, the decision may be recorded by one or more log nodes (discussed more fully below and illustrated in FIG. 3) which do not participate in the quorum. It should be appreciated that a node serving as a log node does not rule out, in general, that the node serve other roles in the system. In some embodiments, the system may designate log nodes in such a way so as to preclude that a log node for a given account will also be a replica node for the same account. In some embodiments, for each source account replica node participating in the decision quorum there may be several nodes designated to serve as log nodes for the decisions of that replica node. Additionally, or alternatively, the decision may be communicated to one or more client computers and/or replicas responsible for one or more target accounts of the transaction. In this manner, digital signatures may ensure that the sequence of previous transactions present when a quorum accepts a give transaction cannot be changed surreptitiously without discovery by anyone with a copy of the signatures. In this manner, the communication of accepted transactions together with such signatures to log nodes may ensure that the number of nodes that must collaborate to omit mention of outgoing transactions so as to subvert the discovery of impaired transactions may be increased.

[0105] In some embodiments, one or more nodes that collect logs may be identified by some dynamically changing but easily computable method. In this manner, it may be difficult for a malicious attacker to predict which nodes to subvert, but easy for a verifier to compute afterwards which nodes should be queried to find putative omitted outgoing transactions. For example, one or more nodes may be chosen based on one or more numbers derived from an agreed hashing technique based on a public identifier for an account and a number of incoming transactions, or upon a timestamp or logical view number as chosen by a Byzantine consensus algorithm.

[0106] In some embodiments, the number of nodes serving as log nodes for a given transaction may be a fixed property of the system. In other embodiments, the number of log nodes may vary. For instance, the number of log nodes may be chosen or adjusted so as to be roughly proportional to a statistic based on the size of the transaction. In some embodiments, the number of log nodes for a given transaction may depend on other system properties. For instance, the system may adjust it to reflect network connectivity, throughput and/or latency data of log nodes, and/or some other statistic which reflects the reliability and/or availably of the nodes.

[0107] In some embodiments, variants or additions to the protocol by which log nodes receive transaction records may be employed. In some embodiments, although the log nodes do not participate in the source account quorum, the formation of a quorum of log nodes and the presentation of a certificate signed by that log quorum by the participant in the source account quorum may serve as an additional condition for the commitment of the source account quorum to the proposed transaction. Additionally, or alternatively, one or more nodes associated with one or more target accounts for the proposed transaction may be responsible for communicating a log record for the transaction with replicas. In this manner, nodes for accounts which have an incentive to preserve a record of the transaction may be responsible for insuring memorialization and searchability of the transaction.

[0108] FIG. 3 shows an example system 300, according to some embodiments, with account replica nodes 310, 320, 330, 340, 350, and 360. Account replica node 310 has log nodes 311, 312, 313, 314, and 315; account replica node 320 has log nodes 321, 322, 323, 324, and 325; account replica node 330 has log nodes 331, 332, 333, and 334; account replica node 340 has log nodes 341, 342, 343, 344, and 345; account replica node 350 has log nodes 351, 352, 353, 354, 355, and 356; and account replica node 360 has log nodes 361, 362, 363, 364, and 365. The log nodes log the transactions accepted by the respective account replica node.

4. Transaction Weighting

[0109] In some embodiments, a verifier may randomly choose, from an account's transaction history, an incoming transaction to verify using other than equal weighting of the transactions. For instance, in some embodiments, an incoming transaction may be chosen from the account history before the verified outgoing transaction with a probability proportional to an amount of resource transferred by the incoming transaction, out of all incoming transactions in the account history. In this manner, the transactions which are most likely to cause invalidation may be most likely to be checked.

[0110] In some embodiments, a total verification budget may be split up randomly among the incoming transactions, such that each chosen transaction (e.g., transaction 101 in the example of FIG. 1) is accorded a sub-budget, which may be then split recursively to verify preceding transactions (e.g., transactions 103 and 104 in the example of FIG. 1). In some embodiments, the verification budget may be chosen randomly from a distribution whose mean depends on the size of the transaction.

[0111] In some embodiments, the verification budget may be specified in units of the number of transactions checked. Alternately, or additionally, the verification budget units may represent a measure of work performed for the verification, such as, for instance, the number of messages sent, the CPU time spent, and/or the amount of computer memory used.

[0112] In some embodiments, a verifier may split up an overall budget between verifying incoming transactions and verifying with replicas and/or log nodes that no outgoing transactions depleting account resources were omitted. In some embodiments, this allocation strategy may also be used recursively.

5. Repair

[0113] In some embodiments, when an invalid transaction is found, it may be repaired by adjusting the amount transferred from one or more source accounts and supplementing them with one or more other source accounts. In this manner, source accounts may avoid transferring more than the amount of resource available, while target accounts may receive the same amount of resources. In some embodiments, only invalid transactions, when found, may be replaced. For instance, a source account that did not have a sufficient balance to support the transaction at the time the transaction took place may be supplemented by one or more other accounts which, collectively, do have a sufficient balance. In this manner, account history may be brought back into a consistent state after discovery of an invalid transaction, without unravelling future transactions.

[0114] In some embodiments, an account that supplements a source account for an invalid transaction may be an account associated with a node, or an owner of a node, that is responsible for maintaining the source account. In some embodiments, accounts of replica nodes that maintain accounts along a path of outgoing transactions subsequent to the invalid transaction may be made responsible, because such replica nodes had an opportunity to check and discover the invalid transaction. In this manner, responsibility for repair may provide an incentive to properly check a transaction history of an account prior to accepting an outgoing transaction from the account.

[0115] In some embodiments, the RAS may require node owners to maintain accounts, and to maintain some minimum amount of resource in these accounts as a condition for the operation of nodes. In this manner, the system may ensure that there are always some resources available for the repair of transactions. In some embodiments, nodes may charge a transaction fee to process transactions. In this manner, the system may ensure that processing transactions may on the average be profitable for node owners, despite the fact that they may be required to repair transactions from time to time.

[0116] For example, as shown in diagram 400 of FIG. 4, if, by way of verifying proposed transaction 405, replica node 411 finds, by following incoming transaction 404, and checking with replica node 421 of the replica nodes 426 of account 420 and then, following transaction 402, checking replica node 435 of the replica nodes 436 of the account 410, and/or one of the log nodes 438 associated with replica node 435, that the transaction 402 of resources from account 430 to account 420 was invalid, it may initiate a repair process, whereby the accounts 450 associated with the owners of the nodes in the replica groups 426 and 436 provide resources to account 420 to replace any amount illegitimately transferred from account 430, thereby restoring the resources for the impaired transaction 404, and enabling the proposed transaction 405.

[0117] In some embodiments, the verification of the transaction history may result in multiple possible invalid transactions, only a subset of which need be invalidated to satisfy consistency constraints. For example, it may be that in account 430 there were two transactions of size X and Y, with X to account 420 and Y to some other account, such that X and Y together exceeded the maximum resources available. In some embodiments, in such cases, the system may choose which of a set of transactions to invalidate according to other criteria. In some embodiments, where there is a set of outgoing transactions whose sum jointly exceeds the limit, a subset to be invalidated may be chosen so as to be as small as possible given the available resources. In some embodiments, where there are several such subsets, one may be chosen at random. In some embodiments, where there are a large number of transactions, a suitable polynomial time approximation scheme to the knapsack problem (such as described in [KU1999]) can be used to choose a subset. In some embodiments, in order to join the system, nodes must put up an assigned amount of escrow. In this manner, the system may be assured that some resources are available for repair.

[0118] Embodiments may use various methods to distribute responsibility. For example, in some embodiments, nodes which were originally responsible for accepting an invalid transaction may be jointly responsible up to their full capability to repair the invalid transaction. In some embodiments, any additional responsibility may be divided proportionately among accounts of replicas responsible for all outgoing transactions after the first invalid transaction. In some embodiments, the amount of resources for which a node not directly responsible may be bounded, and responsibility for remaining lacking resources may be propagated forward recursively to accounts of nodes responsible for the replicas of accounts into which resources, from the invalid transaction or subsequent outgoing transactions from the same account, have flowed. In this manner, nodes which may have been simply unlucky, and not malicious, may be limited to a bounded responsibility for any repairs, but will still have an incentive to perform verification checks so as to minimize the likelihood of this possibility. In this manner, if nodes receive a reward for the successful processing of transactions, they may expect that, on the average, transaction processing is advantageous, even though it may incur an occasional unexpected resource cost.

[0119] In some embodiments, repair may proceed so as to minimize cost or maximize value with respect to a resource. For example, in cases in which the resource is a computed attribute of underlying objects and/or parts, a repair mechanism which must invalidate a transaction may not be able to substitute for a transaction in its entirety. In such cases, the repair step can invalidate the transaction(s) with the least value and/or greatest cost. For example, if the system tracks parts and their planned inclusion into assemblages, using a resource which is the value of these assemblages, and the system finds that a certain part has been erroneously recorded as included in two disjoint assemblages, the system may choose to invalidate the inclusion which reduces the overall value of the assemblages minimally. In some embodiments, other sorts of resources may be transferred to compensate for any loss that may be incurred. For example, if the system tracks both parts, assemblages and their owners, and keeps accounts with some valuable, transferrable resource associated with owners, it may transfer such transferrable resources from the account of an owner of a part to the account of an owner of an invalidated assemblage in order to compensate for the loss of value associated with the invalidation.

6. Responsibility Chaining

[0120] In addition to, or as an alternative to the above method of distributing responsibility for repair, the system may specify that resources from other accounts should be used for repairs. In some embodiments, if certain immediately responsible accounts belong to the nodes owners of replicas which accepted an invalid account, then the system may make the owners of the replicas keeping the records of the immediately responsible accounts responsible for some or all of any amount which the immediately responsible accounts cannot provide. In some embodiments, this responsibility may extend farther in a like manner to other accounts recursively, with responsibility flowing to levels in a breadth-first manner, which will be transitively jointly responsible for any amount that the previous level did not rep air.

[0121] In some embodiments, aside from nodes that maliciously accept invalid transactions, nodes in the responsibility chain may have a responsibility bounded per transaction and/or per account for which they are responsible. In this manner, unlucky nodes' expected costs are bounded.

[0122] FIG. 5 shows a diagram 500 illustrating responsibility for an invalid transaction in an account 512 according to some embodiments. Account 512 has account replica nodes 520 (consisting of replica nodes 521, 522, and 523). On the first level (level 510) the responsibility for repairing the deficit in account 512 may be with the accounts 530 owned by replica nodes 520 (namely, account 531, account 532, and account 533). As replicas 520 were responsible for verifying the transaction originally, their responsibility may not be bounded and drawn from their accounts 530. However, the ability of accounts 530 to repair the lacking amount and type of resource may be insufficient. Accordingly, in some embodiments, any residual deficit may flow to the second level 540 consisting of the replica nodes 550 (nodes 551, 552, 553) responsible for account 531, replica nodes 560 (nodes 561, 562, 563) responsible for account 532 and replica nodes 570 (nodes 571, 572, 573) responsible for account 533. These accounts may bear a limited liability for repairing any remaining deficit, and any further residual amount may flow to the third level and any subsequent levels 590, containing the replica nodes responsible for maintaining the accounts of the nodes in level 540 (and subsequent levels) in a like manner.

[0123] In some embodiments, nodes which process transactions, and whose owners maintain accounts, may periodically request the ability to process more transactions from the replica nodes which manage their accounts, called chained replica nodes. In some environments, the evidence of these permissions may be cryptographic authorization tokens signed by quorum of chained replica nodes for each replica node in a source account that may be used in transaction signatures. In some embodiments, a transaction may not be considered accepted unless the transaction includes a signed reference to a valid authorization token issued by appropriate chained replica nodes. Chained replica nodes in the responsibility chain may grant requests for more tokens, for instance, in return for a given percentage of the transaction fee. In some embodiments, these requests may be used transitively. In this manner, managing accounts for nodes that manage accounts may on balance be advantageous, despite occasionally participating in transaction repair.

[0124] In some embodiments, the system may manage authorization tokens from chained replica node quorums as a separate resource, with replica nodes verifying transactions using up authorization tokens from chained replica node quorums as they process transactions for the accounts they replicate. In some embodiments, the amount of authorization tokens required to process a given transaction for the primary resources may be proportionate to the total amount of the primary resource(s), to the of outgoing primary resources and/or the amount of incoming primary resources. In some embodiments, verification of the authorization tokens may be accomplished as part of the overall verification of transactions, whereby the verifier probabilistically choses to verify either the primary resource(s) or the resource of authorization tokens, or both depending on verification budget and/or the details of the probabilistic choice method employed.

[0125] In some embodiments, the creation of authorization tokens may be governed by chained replica nodes. In some embodiments, the creation of authorization tokens at a given level in the responsibility chain requires the use of authorization tokens at the next level. In some embodiments, the grant of authorization tokens at any level by quorums of chained replica nodes may depend on both the amount of escrow and the perceived riskiness of transactions processed to chained replica node owners. In this manner the apparent regress of requiring authorization tokens to process transactions from a higher level to process at a lower level need not be an essential impediment to system scaling as the provision of escrow and/or the average validity of transactions may allow a high volume and/or value of transactions to be processed while involving only a limited number of levels of responsibility chaining.

7. Batch Transactions

[0126] In some embodiments, for instance due to transaction processing costs, nodes may be unwilling or unable to process small transactions without compensation which may be larger as a portion of the transaction as the transaction size gets smaller. The inventor has recognized that it is often desirable to process small transactions without prohibitive fees. Accordingly, in some embodiments, groups of transactions may be processed together using random verification. In some embodiments, this may be accomplished by checking the source accounts in the transaction batch as if the batch were one larger transaction. In this manner, any of the previous techniques described above for the verification of may be applied to the whole group of transactions.

[0127] In some embodiments, the batch of transactions may represent a joint responsibility: for instance, a responsibility for many small actions taken. Verification may be regarded as the taking of an assay of the batch; the total of this responsibility may be accepted as a whole, or with a penalty, depending on the proportion of invalid and/or impaired transactions as discovered in a sample.

8. Maintenance

[0128] It should be appreciated that RASes, in some embodiments, may be able to eventually find and correct invalid transactions. However, in some embodiments, the length of period in which the probability that a given invalid transaction is found converges to certainty as a function of the number of subsequent transactions. It may be desirable for this probability to converge independent of the number of subsequent transactions. In some embodiments, the system may periodically verify accounts and/or independent of subsequent transactions. In some embodiments, a transaction or account may be chosen at random for probabilistic verification of its history. In some embodiments, accounts with fewer than a threshold number of transactions may incur a periodic maintenance fee implemented as a transaction with verifying node(s), which as a side effect would trigger verification of history. In some embodiments, the maintenance threshold may be proportional with the assets in the account. In this manner, invalid transactions may be discovered irrespective of subsequent transactions.

9. System Diagram

[0129] FIG. 6 shows a block diagram of resource allocation system 600 according to some embodiments in which various embodiments may be implemented. RAC 600 includes a plurality of nodes, here shown as nodes 610, 620, 621 . . . 629 connected over a network 650. schematically, an illustrative computer 600 on which any aspect of the present disclosure may be implemented.

[0130] A node may be a computing device. In some embodiments, a node may be implemented by several computers, and/or several nodes may be implemented by the action of a single computer. A computing node may have several roles, for instance it may be both an account replica node and a log node; alternately, different roles may be implemented by disjoint computing nodes. Each node may be implemented through a suitable computing device or in any suitable way. In some embodiments, multiple nodes are implemented on the same computing device and may share some computer hardware. In some embodiments one or more nodes may be implemented on virtual machines. In some embodiments the computing device may itself be distributed utilizing hardware resources that are connected over a network or communications bus, or dynamically allocated. Each node need not be implemented in the same way, though a plurality of nodes may have the same or similar implementation. Node 610 according to some embodiments, includes a processor 611, a memory 612, a network interface 613, and user input/output 615.

[0131] Processor 611 may be configured to control various aspects of node 610 and may be operatively connected to memory 612. Processor 611 may be any suitable processing device such as for example and not limitation, a central processing unit (CPU), digital signal processor (DSP), controller, addressable controller, general or special purpose microprocessor, microcontroller, addressable microprocessor, programmable processor, programmable controller, dedicated processor, dedicated controller, or any suitable processing device. In some embodiments, processor 611 comprises one or more processors, for example, processor 611 may have multiple cores and/or be comprised of multiple microchips. In various embodiments, processing by processor 611 may be performed sequentially, in parallel, or by some other method or combination of methods.

[0132] Memory 612 may be integrated into processor 611 and/or may include “off-chip” memory that may be accessible to processor 611, for example, via a memory bus (not shown). Memory 612 may store computer executable instructions that when executed by processor 611 perform desired functions. Memory 612 may store one or more application programs and/or external components used by application programs (e.g., software libraries), which may be loaded into memory 612. To perform any of the functionality described herein, processor 611 may execute one or more processor-executable instructions stored in memory 612 which may serve as non-transitory computer-readable storage media storing processor-executable instructions for execution by the processor 611.

[0133] Memory 612 may be any suitable type of non-transient computer-readable storage medium such as, for example and not limitation, RAM, a nanotechnology-based memory, optical disks, volatile and non-volatile memory devices, magnetic tapes, flash memories, hard disk drive, circuit configurations in Field Programmable Gate Arrays (FPGA), or other semiconductor devices, or other tangible, non-transient computer storage medium.

[0134] Network interface 613 may be any suitable combination of hardware and software configured to communicate over a network. The network interface may be configured to receive instructions from other components of node 610 to send and/or receive information of the network using electrical signals. Network interface 613 may have a cabled and/or non-cabled (“wireless”) connection to the network.

[0135] Node 610 may have one or more input and output devices 615 for interacting with a user (user I/O 615). I/O 615 may be used, among other things, to present a user interface. Examples of output devices that can be used to provide a user interface include printers or display screens for visual presentation of output and speakers or other sound generating devices for audible presentation of output. Examples of input devices that can be used for a user interface include keyboards and pointing devices, such as mice, touch pads, and digitizing tablets. As another example, the input devices may include a microphone for capturing audio signals, and the output devices may include a display screen for visually rendering, and/or a speaker for audibly rendering, recognized text.

[0136] Nodes 610-649 may communicate over network 650. Network 650 may be any suitable network such the internet, another private or public network, a wired (e.g., ethernet, fiber optic) network, wireless network, or any suitable combination of networks and network technologies.

[0137] In some embodiments, account transactions are initiated from any number of terminals, such as terminals 660-669. Terminals may have suitable computer hardware and software for facilitating such transactions. For example, authentication of an account owner may be required before a transaction can be initialized in RAS 600. In some embodiments, transactions are created by other computing systems performing arbitrary other functions, which may have occasion to use a resource allocation system operating on the same or overlapping computer hardware and/or available via a suitable network interface.

[0138] Having thus described several aspects of at least one embodiment, it is to be appreciated that various alterations, modifications, and improvements will readily occur to those skilled in the art. Such alterations, modifications, and improvements are intended to be within the spirit and scope of the present disclosure. Accordingly, the foregoing description and drawings are by way of example only.

[0139] The above-described embodiments of the present disclosure can be implemented in any of numerous ways. For example, the embodiments may be implemented using hardware, software or a combination thereof. When implemented in software, the software code can be executed on any suitable processor or collection of processors, whether provided in a single computer or distributed among multiple computers.

[0140] Also, the various methods or processes outlined herein may be coded as software that is executable on one or more processors that employ any one of a variety of operating systems or platforms. Additionally, such software may be written using any of a number of suitable programming languages and/or programming or scripting tools, and also may be compiled as executable machine language code or intermediate code that is executed on a framework or virtual machine.

[0141] In this respect, the concepts disclosed herein may be embodied as a non-transitory computer-readable medium (or multiple computer-readable media) (e.g., a computer memory, one or more floppy discs, compact discs, optical discs, magnetic tapes, flash memories, circuit configurations in Field Programmable Gate Arrays or other semiconductor devices, or other non-transitory, tangible computer storage medium) encoded with one or more programs that, when executed on one or more computers or other processors, perform methods that implement the various embodiments of the present disclosure discussed above. The computer-readable medium or media can be transportable, such that the program or programs stored thereon can be loaded onto one or more different computers or other processors to implement various aspects of the present disclosure as discussed above.

[0142] The terms “program” or “software” are used herein to refer to any type of computer code or set of computer-executable instructions that can be employed to program a computer or other processor to implement various aspects of the present disclosure as discussed above. Additionally, it should be appreciated that according to one aspect of this embodiment, one or more computer programs that when executed perform methods of the present disclosure need not reside on a single computer or processor, but may be distributed in a modular fashion amongst a number of different computers or processors to implement various aspects of the present disclosure.

[0143] Computer-executable instructions may be in many forms, such as program modules, executed by one or more computers or other devices. Generally, program modules include routines, programs, objects, components, data structures, etc. that perform particular tasks or implement particular abstract data types. Typically, the functionality of the program modules may be combined or distributed as desired in various embodiments.

[0144] Also, data structures may be stored in computer-readable media in any suitable form. For simplicity of illustration, data structures may be shown to have fields that are related through location in the data structure. Such relationships may likewise be achieved by assigning storage for the fields with locations in a computer-readable medium that conveys relationship between the fields. However, any suitable mechanism may be used to establish a relationship between information in fields of a data structure, including through the use of pointers, tags or other mechanisms that establish relationship between data elements.

[0145] Various features and aspects of the present disclosure may be used alone, in any combination of two or more, or in a variety of arrangements not specifically discussed in the embodiments described in the foregoing and is therefore not limited in its application to the details and arrangement of components set forth in the foregoing description or illustrated in the drawings. For example, aspects described in one embodiment may be combined in any manner with aspects described in other embodiments.

[0146] Also, the concepts disclosed herein may be embodied as a method, of which an example has been provided. The acts performed as part of the method may be ordered in any suitable way. Accordingly, embodiments may be constructed in which acts are performed in an order different than illustrated, which may include performing some acts simultaneously, even though shown as sequential acts in illustrative embodiments.

[0147] Use of ordinal terms such as “first,” “second,” “third,” etc. in the claims to modify a claim element does not by itself connote any priority, precedence, or order of one claim element over another or the temporal order in which acts of a method are performed, but are used merely as labels to distinguish one claim element having a certain name from another element having a same name (but for use of the ordinal term) to distinguish the claim elements.

[0148] Also, the phraseology and terminology used herein is for the purpose of description and should not be regarded as limiting. The use of “including,” “comprising,” “having,”, “containing,” “involving,” and variations thereof herein, is meant to encompass the items listed thereafter and equivalents thereof as well as additional items.

10. Referenced Documents

[0149] [AS2007] Awerbuch, Baruch, and Christian Scheideler. “Towards Scalable and Robust Overlay Networks.” IPTPS. Vol. 7. 2007. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.176.6088&rep=rep1&type=pdf [0150] [BG2013] Bailis, Peter, and Ali Ghodsi. “Eventual consistency today: Limitations, extensions, and beyond.” Queue 11.3 (2013): 20, http://www.bailis.org/papers/eventual-queue2013.pdf [0151] [FC2005] Feldman and Chuang, “Overcoming Free-Riding Behavior in Peer-to-Peer Systems,” ACM sigecom exchanges 5.4 (2005): 41-50. http://www.sigecom.org/exchanges/volume_5_(04)/5.4-feldman.pdf [0152] [FYS2005] Fiat, Amos, Jared Saia, and Maxwell Young. “Making chord robust to byzantine attacks.” European Symposium on Algorithms. Springer, Berlin, Heidelberg, 2005. https://s3.amazonaws.com/academia.edu.documents/32883830/chord.pdf?AWSAccessKeyId=AKIAIWOWYYGZ2Y53UL3A&Expires=1537461008&Signature=wT9jeMWBS4izqreaGsEG Mv5bbE8%3D&response-content-disposition=inline %3B %20filename %3DMaking_Chord_Robust_to_Byzantine_Attacks.pdf [0153] [KG2009], Kate and Goldberg, Kate, Aniket, and Ian Goldberg. “Distributed key generation for the internet.” 2009 29th IEEE International Conference on Distributed Computing Systems. IEEE, 2009. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.216.7018&rep=rep1&type=pdf [0154] [KU1999] Kellerer, Hans, and Ulrich Pferschy. “A new fully polynomial time approximation scheme for the knapsack problem.” Journal of Combinatorial Optimization 3.1 (1999): 59-71. [0155] [L2010] Lamport, Leslie. “Byzantizing Paxos by refinement.” International Symposium on Distributed Computing. Springer, Berlin, Heidelberg, 2011. https://lamport.azurewebsites.net/tla/byzsimple.pdf [0156] [LSP1982] Lamport, Leslie, Robert Shostak, and Marshall Pease. “The Byzantine generals problem.” ACM Transactions on Programming Languages and Systems (TOPLAS) 4.3 (1982): 382-401. [0157] [LCP2005] Lua, Eng Keong, et al. “A survey and comparison of peer-to-peer overlay network schemes.” IEEE Communications Surveys and tutorials 7.1-4 (2005): 72-93, https://ieeexplore.ieee.org/abstract/document/1610546/ [0158] [YKG2013] Young et al, “Towards Practical Communication in Byzantine-Resistant DHTs,” http://www.cypherpunks.ca/˜iang/pubs/ByzantineDHT_Journal.pdf

Patents

[0159] [M2016] Michali 2016, “Distributed transaction propagation and verification system”, US Patent PCT/US2017/031037 [0160] [U.S. Pat. No. 6,463,532B1] System and method for effectuating distributed consensus among members of a processor set in a multiprocessor computing system through the use of shared storage resources. [0161] [US20130290249A1] Large distributed database clustering systems and methods [0162] [US20180341930A1] Sharded Permissioned Distributed Ledgers [0163] [WO2019032891A1] Verification of interactions system and method [0164] [US20170264428A1] Data storage system with blockchain technology [0165] [U.S. Ser. No. 10/135,609B2] Managing a database management system using a blockchain database