Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
DETAILED ACTION
This communication is responsive to Amendment, filed 09/11/2005.
Claims 1-17, 19-20 are pending in this application. This action is made Final.
Claim Rejections - 35 USC § 103
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102 of this title, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
The factual inquiries set forth in Graham v. John Deere Co., 383 U.S. 1, 148 USPQ 459 (1966), that are applied for establishing a background for determining obviousness under 35 U.S.C. 103 are summarized as follows:
1. Determining the scope and contents of the prior art.
2. Ascertaining the differences between the prior art and the claims at issue.
3. Resolving the level of ordinary skill in the pertinent art.
4. Considering objective evidence present in the application indicating obviousness or nonobviousness.
This application currently names joint inventors. In considering patentability of the claims the examiner presumes that the subject matter of the various claims was commonly owned as of the effective filing date of the claimed invention(s) absent any evidence to the contrary. Applicant is advised of the obligation under 37 CFR 1.56 to point out the inventor and effective filing dates of each claim that was not commonly owned as of the effective filing date of the later invention in order for the examiner to consider the applicability of 35 U.S.C. 102(b)(2)(C) for any potential 35 U.S.C. 102(a)(2) prior art against the later invention.
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
Claims 1-3, 5-17, 19, 20 are rejected under 35 U.S.C. 103 as being unpatentable over Hunt et al. (US Pub No. 20180158034), in view of KOMANDUR et al. (US Pub No. 20200151686).
As to claims 1, 19, 20, Hunt teaches a computer-implemented method performed by method performed by a blockchain node, the method comprising:
maintaining a data structure representing orphan transactions, wherein an orphan transaction is blockchain transaction having at least one parent blockchain transaction that is an unavailable transaction and/or at least one parent blockchain transaction that is a different orphan transaction, wherein an unavailable transaction is a blockchain transaction that is not available to a validation pipeline of the blockchain node, and wherein (i.e. When constructing a lattice of nodes having one or more transactions, given an ordered set of transactions to be verified, an empty lattice is initialized. This includes designating the ‘Top’ node, representing the start of execution of the transactions, and a ‘Bottom’ node representing the end of all transaction executions. Next, the read and write sets of each transaction must be determined by any number of means (including through annotations, static analysis or dynamic analysis). An iteration over all transactions in the transaction set is performed, including retrieving the next transaction, ‘NT’, in the transaction set. Each time a transaction is considered, it is place in a (new) node connected to Bottom. For each transaction considered, by iterating over the lattice in a breadth first manner starting at bottom, the node containing NT is placed into the lattice below all existing nodes in the lattice that have a write set containing a variable in NT's read set or write set or that read a variable in NT write set. If NT has no read/write set dependency on any prior transactions in the transaction set, the node containing NT can be inserted into the lattice just below ‘Top’, and parallel to any other nodes (transactions) just below Top. Repeated iterations must be performed over the set of transactions until all transactions have been inserted into the lattice, [0036]):
the data structure comprises a directed graph of nodes and edges, wherein each node of the graph represents either a respective orphan transaction or a respective unavailable transaction, wherein each edge connecting a respective parent node to a respective child node represents the spending of an output of the respective blockchain transaction represented by the respective parent node by an input of the respective blockchain transaction represented by the respective child node (i.e. a directed graph, [0045]; each node in the lattice contains one transaction ... The dependence graph is based on the relationship between the read and write sets for each of the blockchain functions to be invoked by the transactions and the given order of the transactions iterate over all of the transactions in the transaction set in the given order, [0037]); and
wherein each node of the graph is associated with a respective transaction
identifier of the respective blockchain transaction represented by that node and comprises (i.e. FIG. 4B illustrates a lattice structure 420 where the Top of the lattice 422 is defined along with the Bottom of the lattice 428. The first node 424 has one proposed transaction. The second node 423 has one proposed transaction, the third node 425 has one proposed transaction and the fourth node 426 has one proposed transaction. When constructing the lattice, the nodes must be searched in breadth first order starting at ‘Bottom’. The lattice construction algorithm iterates over all transaction in the list. Each time a new transaction, NT, is processed, the node that represents it is automatically connected to the Bottom. The NT is placed into the lattice below all existing nodes in the lattice that have a write set containing a variable in NT's read set or write set in NT's write set or that read a variable in NT's write set. Note that any proposed transaction that has no read or write set dependency on any prior proposed transactions in the transaction set can be inserted into the lattice just below Top, parallel to any other nodes (proposed transactions). This process is iterated until all proposed transactions for a block have been inserted into the lattice. There may be many iterations performed when constructing the lattice. A proposed transaction may be included as part of an existing node in the lattice when the proposed transaction to be added to the lattice would only have a single predecessor node in the lattice. The lattice in FIG. 4B represents the state of construction after four transactions from the list in FIG. 4A have been processed, [0038]):
a) a respective indegree value, wherein the respective indegree value is one of (i.e. CountPred is a function that goes through each node in a lattice and sets the count field to the number of non-Top predecessors nodes for each node in the lattice. If the only predecessor of a node is Top, the count is set to zero. Any method that successfully traverses the lattice without duplication (counting the same predecessors multiple times) is acceptable. This description uses a lattice node that contains a count. Any method of associating a predecessor count with the lattice node will be acceptable. This count represents the number of nodes (proposed transactions assuming one transaction per node) that must executed prior to the current node's proposed transaction(s) execution. The algorithm described below will decrement this count whenever a predecessor node (proposed transaction) completes execution, [0043]):
(i) a first value indicating that the respective blockchain transaction has an unknown number of parent blockchain transactions that are either unavailable transactions or orphan transactions (i.e. FIG. 6 illustrates a lattice creation algorithm flow diagram 600 according to another example embodiment. Referring to FIG. 6, the lattice creation algorithm builds the lattice based on an existing proposed transaction list, TxList, of transactions 602 ... The search for the correct location of NN in the lattice starts by initializing ‘found predecessor’ to false 618 and then LN is set to the next node from the breadth first ordered list of lattice nodes 622 ... The algorithm continues by selecting the next node in the breadth first search that needs to be checked to see if it is a predecessor to NN, [0049]), or
(ii) a zero value indicating that the respective blockchain transaction has no parent blockchain transactions that are either unavailable transactions or orphan transactions (i.e. If the only predecessor of a node is Top, the count is set to zero, [0043]), or
(iii) a value indicating the number of respective parent blockchain transactions of the respective blockchain transaction that are either unavailable transactions or orphan transactions (i.e. This description uses a lattice node that contains a count. Any method of associating a predecessor count with the lattice node will be acceptable. This count represents the number of nodes (proposed transactions assuming one transaction per node) that must executed prior to the current node's proposed transaction(s) execution. The algorithm described below will decrement this count whenever a predecessor node (proposed transaction) completes execution, [0043]); and
b) a list respective references of respective child nodes, if any, that are connected to that node by respective edges (i.e. ‘E’ is a list of nodes (proposed transactions) that are ready for execution; this list is constructed by the function find_ready. ‘F’ is a reference to a node in the lattice. ‘get_lock’ gets the lock for that node. The lock is a semaphore that only permits one process to decrement the predecessor count for the node. Manipulating semaphores for all system architectures is well understood in the art. ‘find_ready’ is a function which goes through a list of nodes in the lattice that still need to be scheduled and returns the list of nodes where the predecessor node count is zero and has not already executed the proposed transaction(s) represented by the node, [0044]).
Hunt implicitly teaches the term "orphan" (i.e. CountPred is a function that goes through each node in a lattice and sets the count field to the number of non-Top predecessors nodes for each node in the lattice. If the only predecessor of a node is Top, the count is set to zero, [0043]).
Hunt does not clearly state this term.
KOMANDUR teaches this term (i.e. the processor is configured to generate an orphan event entry for storing in an orphan list on the distributed ledger, [0394]; the state can define whether a subsequently received event message is inconsistent with the current state of the transaction data process (e.g. a completed payment message received before a received payment message, or a second received payment message), [0396]; the processor figured to traverse the orphan list or otherwise identify any orphan event entries which are now consistent with the state of the transaction ... this can ensure the state of the transaction is up to date and can ensure any out of order messages are properly processed, [0397]).
It would have been obvious to one of ordinary skill of the art having the teaching of Hunt, KOMANDUR before the effective filing date of the claimed invention to modify the system of Hunt to include the limitations as taught by KOMANDUR One of ordinary skill in the art would be motivated to make this combination in order to generate an orphan list event entry, and traverse the orphan list or otherwise identify any orphan event entries which are now consistent with the state of the transaction, in view of KOMANDUR ([0397]), as doing so would give the added benefit of ensuring the state of the transaction is up to date and ensuring any out of order messages are properly processed, as taught by KOMANDUR ([0397]).
As per claim 2, Hunt teaches the method of claim 1, wherein the data structure comprises some or all of the orphan transactions (i.e. Note that any proposed transaction that has no read or write set dependency on any prior proposed transactions
in the transaction set can be inserted into the lattice just below Top, [0038]).
As per claim 3, Hunt teaches the method of claim 2, wherein one, some or each node of the graph that represents a respective orphan transaction comprises the respective orphan transaction (i.e. In the final lattice, “forks” represent opportunities for parallel execution. For example, in FIG. 4B, it is clear that transaction three (3) 425 can be executed in parallel with transaction one (1) 424. In the lattice of FIG. 4B, the ‘join’ represents synchronization points. All blocks of transactions above the join must be completed before any transaction after the join. Before processing transaction four (4) 426, synchronization is required since transactions one (1) 424, two (2) 423 and three (3) 425 must have completed first, [0039]).
As per claim 5, Hunt teaches the method of claim 1, wherein each node of the graph further comprises:
c) the respective transaction identifier of the respective blockchain transaction represented by that node (i.e. Referring to FIG. 4C, execution of lattice forks can proceed in parallel. Execution of lattice joins are synchronization points. For example, if the dependency graph illustrated in the previous fork was scheduled on a four thread system, t1, t2, t3, and t4, the block starting with proposed transaction one could be scheduled on t1, [0040]).
As per claim 6, Hunt teaches the method of claim 1, further comprising:
obtaining a target orphan transaction and a list of respective target parent
blockchain transactions of the target orphan transaction that are either an unavailable transaction or an orphan transaction (i.e. When constructing a lattice of nodes having one or more transactions, given an ordered set of transactions to be verified, an empty lattice is initialized. This includes designating the ‘Top’ node, representing the start of execution of the transactions, and a ‘Bottom’ node representing the end of all transaction executions, [0036]); and
calling an add transaction algorithm with the target orphan transaction as an input, wherein calling the add transaction algorithm comprise determining whether the graph comprises a target child node representing the target orphan transaction, and based on said determining, updating the graph by creating or updating the target node (i.e. Next, the read and write sets of each transaction must be determined by any number of means (including through annotations, static analysis or dynamic analysis). An iteration over all transactions in the transaction set is performed, including retrieving the next transaction, ‘NT’, in the transaction set, [0036]).
As per claim 7, Hunt teaches the method of claim 6, wherein said determining comprises determining whether a respective node of the graph is associated with a target transaction identifier of the target orphan transaction (i.e. Referring to FIG. 4C, execution of lattice forks can proceed in parallel. Execution of lattice joins are synchronization points. For example, if the dependency graph illustrated in the previous fork was scheduled on a four thread system, t1, t2, t3, and t4, the block starting with proposed transaction one could be scheduled on t1, [0040]).
As per claim 8, Hunt teaches the method of claim 7, wherein said determining comprises generating the target transaction identifier (i.e. FIG. 4D illustrates a further example 440 the state of the lattice after inserting the 8 proposed transactions from FIG. 4A into the lattice according to example embodiments. In this example, node one 424 has one proposed transaction. The second node 423 also has one proposed transaction and the third node 425 also has one proposed transaction. The joins illustrate the completion point of several transactions. In this example, 441 and 443 are also included as proposed transactions 8 and 7, [0042]).
As per claim 9, Hunt teaches the method of claim 6, wherein calling the add transaction algorithm comprises:
for each target parent blockchain transaction in the list of respective target parent blockchain transactions of the target orphan node (i.e. Next an ordered list of nodes currently in the lattice is generated in breadth first order starting at Bottom and assigned to node_list 611, [0049]):
determining whether the graph comprises a respective target parent node representing the respective target parent blockchain transaction of the target orphan transaction (i.e. After that a new node (NN) is created including the NT, and attached to the Bottom 612. The write set WS is the write set of current transaction, NT, which is initialized 614. After that the read set, RS, of NT is initialized 616, [0049]); and
based on said determining, updating the graph by creating or updating the respective target parent node, wherein the respective node comprises a respective reference to the target child node (i.e. Then if found_pred≠F 644, then a dependency
edge is inserted between LN and created node NN 648, [0049]).
As per claim 10, Hunt teaches the method of claim 9, wherein said creating of the respective target parent node comprises setting the respective indegree value of that respective target parent node as the first value if the respective parent blockchain transaction is an unavailable transaction (i.e. The search for the correct location of NN in the lattice starts by initializing ‘found predecessor’ to false 618 and then LN is set to the next node from the breadth first ordered list of lattice nodes 622 ... The algorithm continues by selecting the next node in the breadth first search that needs to be checked to see if it is a predecessor to NN, [0049]).
As per claim 11, Hunt teaches the method of claim 1, further comprising:
obtaining a first blockchain transaction and calling a release transaction algorithm with the first transaction as an input, wherein calling the release transaction algorithm comprises (i.e. In the final lattice, “forks” represent opportunities for parallel execution. For example, in FIG. 4B, it is clear that transaction three (3) 425 can be executed in parallel with transaction one (1) 424. In the lattice of FIG. 4B, the ‘join’ represents synchronization points, [0039]):
identifying a first node of the graph that represents the first blockchain transaction (i.e. Each validating peer can independently construct the lattice based on the ordered set of transactions received as part of the PBFT consensus algorithm or any other algorithm that orders the transactions prior to consensus. A validating peer is a single node in the ledger system. This node can be a single processor with multiple threads or a collection of processors acting as a single node in the overall blockchain network, [0039]); and
if the indegree value of the first node is set as the zero value, sending the first blockchain transaction to the validation pipeline, and removing the first node from the graph (i.e. CountPred is a function that goes through each node in a lattice and sets the count field to the number of non-Top predecessors nodes for each node in the lattice. If the only predecessor of a node is Top, the count is set to zero, [0042]).
As per claim 12, Hunt teaches the method of claim 11, wherein calling the release transaction algorithm comprises updating the graph by:
for each respective child node referenced by the first node (i.e. FIG. 5 illustrates a flow diagram corresponding to the transaction scheduling algorithm. Referring to FIG. 5, the main algorithm includes scheduling a transaction list 502 by initializing, repeating and continuing until ‘L’ is empty. The lattice is built based on the transaction list 504. The count of predecessor nodes 506 may be performed, not including the Top node, [0046]):
if the indegree is a positive number, updating the respective indegree value by decreasing the number of the respective parent blockchain transaction that are either unavailable transactions or orphan transactions (i.e. Schedule(node) function 532 proceeds by obtaining the transaction from the node 534 and executing the transaction 536. Once the transaction has completed execution, the predecessor count on all successor nodes must be decremented, [0047]); and
calling the release transaction algorithm with the respective child node as an
input(i.e. Next, a list of successor nodes ‘SL’ is obtained 538. The next successor, F, is removed from the list 542. If the successor is empty 544 there are no remaining successors that need their predecessor count decremented so the scheduler exits 554. Otherwise, it obtains the lock for the successor node 546, decrements the counter 548, and then releases the lock 552. Once the lock has been released it returns to obtain the next successor from the list of successors 542, [0047]).
As per claim 13, Hunt teaches the method of claim 12, wherein calling the release transaction algorithm with the respective child nodes as input results in one or more child blockchain transactions being sent to the validation pipeline, and wherein the method comprises sending the first blockchain transaction and the one or more child blockchain transactions to the validation pipeline as a batch of blockchain transaction (i.e. One way to accomplish the processing is to schedule a block of proposed transactions on a thread and have them return to the scheduler when they complete. At this point the scheduler would identify what else could be scheduled at any given time, [0041]).
As per claim 14, Hunt teaches the method of claim 13, comprising sending the first blockchain transaction and the one or more child blockchain transactions to the same processor of the validation pipeline (i.e. In the final lattice, “forks” represent opportunities for parallel execution. For example, in FIG. 4B, it is clear that transaction three (3) 425 can be executed in parallel with transaction one (1) 424 ... This node can be a single processor with multiple threads or a collection of processors acting as a
single node in the overall blockchain network, [0039]).
As per claim 15, Hunt teaches the method of claim 11, wherein the first blockchain transaction is a respective unavailable transaction, and wherein the method further comprises:
associating a respective listener with one, some, or each respective unavailable transaction (First it checks to see if there are resources available so that transactions can be schedule 522. Once resources are available, it selects the next ready node 524. If there are no more nodes available to be scheduled 526, it returns to look for more nodes that are ready to be scheduled in 510, [0046]); and
in response to obtaining the respective unavailable transaction, the respective listener calling the release transaction algorithm (i.e. Schedule(node) function 532 proceeds by obtaining the transaction from the node 534 and executing the transaction 536. Once the transaction has completed execution, the predecessor count on all successor nodes must be decremented. Next, a list of successor nodes ‘SL’ is obtained 538. The next successor, F, is removed from the list 542, [0047]).
As per claim 16, Hunt teaches the method of claim 11, further comprising:
searching the data structure at regular intervals for one or more respective unavailable transactions that have become available to the validation pipeline (i.e. Schedule(node) function 532 proceeds by obtaining the transaction from the node 534 and executing the transaction 536. Once the transaction has completed execution, the predecessor count on all successor nodes must be decremented. Next, a list of successor nodes ‘SL’ is obtained 538. The next successor, F, is removed from the list 542, [0047]);
and
identifying at least one respective unavailable transactions that has become available to the validation pipeline, wherein the first blockchain transaction is the identified respective unavailable transaction, and wherein said calling of the release transaction algorithm is in response to said identifying (i.e. Schedule(node) function 532 proceeds by obtaining the transaction from the node 534 and executing the transaction 536. Once the transaction has completed execution, the predecessor count on all successor nodes must be decremented. Next, a list of successor nodes ‘SL’ is obtained 538. The next successor, F, is removed from the list 542, [0047]).
As per claim 17, Hunt teaches the method of claim 11, wherein the release transaction algorithm is called in response to one or both of:
the validation pipeline informing the data structure that the first blockchain transaction has entered or exited the validation pipeline (i.e. In the final lattice, “forks” represent opportunities for parallel execution. For example, in FIG. 4B, it is clear that transaction three (3) 425 can be executed in parallel with transaction one (1) 424, [0039]); and
the data structure determining that the first blockchain transaction is represented in the data structure as an unavailable transaction (i.e. Referring to FIG. 4C, execution of lattice forks can proceed in parallel. Execution of lattice joins are synchronization points. For example, if the dependency graph illustrated in the previous fork was scheduled on a four thread system, t1, t2, t3, and t4, the block starting with proposed transaction one could be scheduled on t1, [0040]).
Claim 4 is rejected under 35 U.S.C. 103 as being unpatentable over Hunt et al. (US Pub No. 2018/0158034), in view of KOMANDUR et al. (US Pub No. 2020/0151686), as applied to claims above, and further in view of Islam et al. (US Pub No. 2020/0097953).
As per claim 4, Hunt teaches the method of claim 2, further comprising: removing any respective orphan transaction from the data structure in response to the respective orphan transaction having been in the data structure for a predetermined time limit (i.e. A zero count indicates that all predecessor nodes (proposed transactions) have completed execution so that the node can be scheduled for execution. ‘L’ is a set that represents all of the nodes (proposed transactions) in the lattice, exclusive of the ‘Top’ and ‘Bottom’. ‘Lattice’ is a directed graph without cycles with a single start node, ‘Top’, and a single end node ‘Bottom’. ‘NextNode(X)’ is a function over the ready transaction in ‘R’ that removes a node from the list of nodes, X, and returns the node. A ‘Node’ represents each node of the lattice which contains, or references, a transaction request, a lock, a count of the number of predecessor nodes (exclusive of the Top), and a list (or set) of its predecessor and successor nodes in the lattice, [0045].
Hunt, KOMANDUR do not seem to specifically teach "a predetermined time limit".
Islam teaches this limitation (i.e. the orphaned block module can trigger execution of a second response module (e.g., 142) when no orphaned block is detected within a predetermined period of time (e.g., predetermined number of minutes, predetermined number of confirmation times, etc.), or perform any suitable set of functionalities, [0073]).
It would have been obvious to one of ordinary skill of the art having the teaching of Hunt, KOMANDUR, Islam before the effective filing date of the claimed invention to modify the system of Hunt, KOMANDUR to include the limitations as taught by Islam One of ordinary skill in the art would be motivated to make this combination in order to identify an orphaned block in response to detection of a mismatch between the received block information and the stored block information in view of Islam ([0073]), as doing so would give the added benefit of enabling the orphaned block module to trigger execution of a second response module when no orphaned block is detected within a predetermined period of time, as taught by Islam ([0073]).
Response to Arguments
Applicant's arguments with respect to claims 1-17, 19-20 have been considered but are moot in view of the new ground(s) of rejection.
Conclusion
Applicant's amendment necessitated the new ground(s) of rejection presented in this Office action. Accordingly, THIS ACTION IS MADE FINAL. See MPEP § 706.07(a). Applicant is reminded of the extension of time policy as set forth in 37 CFR 1.136(a).
A shortened statutory period for reply to this final action is set to expire THREE MONTHS from the mailing date of this action. In the event a first reply is filed within TWO MONTHS of the mailing date of this final action and the advisory action is not mailed until after the end of the THREE-MONTH shortened statutory period, then the shortened statutory period will expire on the date the advisory action is mailed, and any extension fee pursuant to 37 CFR 1.136(a) will be calculated from the mailing date of the advisory action. In no event, however, will the statutory period for reply expire later than SIX MONTHS from the mailing date of this final action.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to MIRANDA LE whose telephone number is (571)272-4112. The examiner can normally be reached M-F 7AM-5PM.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Kavita Stanley can be reached on 571-272-8352. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/MIRANDA LE/ Primary Examiner, Art Unit 2153
Prosecution Insights