# US 12,224,949 B2 · Systems and methods for epoch last in first out (LIFO) admission control > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,224,949 B2 - Document ID: US12224949B2 - Status: Granted - Kind: B2 - Application number: 18/046,693 - Filed: 2022-10-14 - Published: 2024-04-18 - Granted: 2025-02-11 - Earliest claimed: 2022-10-14 - Assignees: Cockroach Labs, Inc. - Applicants: Cockroach Labs, Inc. - Inventors: Sumeer Kumar Bhola - Web page: https://patentgrep.com/patent/US12224949B2 ## CPC - H04L 47/6245: {Modifications to standard FIFO or LIFO} - H04L 43/106: using time related information in packets, e.g. by adding timestamps - H04L 47/6225: {Fixed service order, e.g. Round Robin} - H04L 43/0852: Delays - H04L 43/16: Threshold monitoring - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## Abstract Methods and systems for managing requests in a distributed computing system are provided. A plurality of requests are received by one or more of the plurality of computing nodes in the distributed computing system. A respective timestamp is assigned to each of the plurality of requests. A subset of the plurality of requests are assigned to an epoch, wherein the epoch corresponds to an interval of time comprising the respective timestamp of each request of the subset of the plurality of requests. A present time is compared to a closing time of the epoch. Based on the comparison, the subset of the plurality of requests are queued for execution in a waiting data structure by last-in, first-out (LIFO) ordering based on the respective timestamp of each request of the subset. ## Claims ### Claim 1 A method for managing requests in a distributed computing system comprising a plurality of computing nodes, the method comprising: receiving, by one or more of the plurality of computing nodes in the distributed computing system, a plurality of requests; assigning a respective timestamp to each of the plurality of requests; assigning a first subset of the plurality of requests to a first epoch of a plurality of epochs, wherein each of the plurality of epochs comprises a respective predetermined closing time of a plurality of predetermined closing times, and wherein the first epoch corresponds to a first interval of time comprising the respective timestamp of each request of the first subset of the plurality of requests; comparing a present time to the predetermined closing time of the first epoch, wherein the predetermined closing time of the first epoch is after the first interval of time and based on (i) a duration of the first interval of time and (ii) a grace period of time; and queuing, based on the comparison and when the present time is equivalent to or greater than the predetermined closing time of the first epoch, the first subset of the plurality of requests for execution in a waiting data structure by last-in, first-out (LIFO) ordering based on the respective timestamp of each request of the first subset. ### Claim 2 (depends on 1) The method of claim 1, wherein a work-sequence comprises one or more work items, and wherein the one or more work items comprise the first subset of the plurality of requests. ### Claim 3 (depends on 1) The method of claim 1, wherein each respective timestamp is assigned by a respective gateway node of the plurality of computing nodes in the distributed computing system. ### Claim 4 (depends on 1) The method of claim 1, wherein each request of the first subset of the plurality of requests is directed to a receiving node of the plurality of computing nodes in the distributed computing system. ### Claim 5 (depends on 4) The method of claim 4, wherein the present time corresponds to a time of a clock of the receiving node. ### Claim 6 (depends on 1) The method of claim 1, further comprising: receiving, by a receiving node of the plurality of computing nodes in the distributed computing system, the first subset of the plurality of requests. ### Claim 7 (depends on 1) The method of claim 1, wherein comparing the present time to the predetermined closing time of the first epoch further comprises: determining the present time is less than the predetermined closing time of the first epoch or determining the present time is equivalent to or greater than the predetermined closing time of the first epoch. ### Claim 8 (depends on 1) The method of claim 1, further comprising: queuing, based on the comparison and when the present time is less than the predetermined closing time of the first epoch, the first subset of the plurality of requests for execution in an open data structure by first-in, first-out (FIFO) ordering based on the respective timestamp of each request of the first subset. ### Claim 9 (depends on 8) The method of claim 8, further comprising: determining (i) the waiting data structure does not include at least one request of the plurality of requests and (ii) the open data structure includes at least one request of the plurality of requests; and dequeuing, based on the determination, the at least one request from the open data structure for execution. ### Claim 10 (depends on 8) The method of claim 8, further comprising: moving, based on the comparison and when the present time is equivalent to or greater than the predetermined closing time of the first epoch, the first subset of the plurality of requests from the open data structure to the waiting data structure. ### Claim 11 (depends on 1) The method of claim 1, further comprising: determining the waiting data structure includes at least one request of the plurality of requests; and dequeuing, based on the determination, the at least one request from the waiting data structure for execution. ### Claim 12 (depends on 1) The method of claim 1, wherein the grace period of time is selected based on an expected clock synchronization skew between the plurality of computing nodes. ### Claim 13 (depends on 1) The method of claim 1, wherein the queuing the first subset of the plurality of requests for execution in the waiting data structure further comprises: queuing the first subset of the plurality of requests for execution in the waiting data structure (i) by last-in, first-out (LIFO) ordering based on the respective timestamp of each request of the first subset and (ii) based on a respective priority level of each request of the first subset. ### Claim 14 (depends on 1) The method of claim 1, further comprising: assigning a second subset of the plurality of requests to a second epoch of the plurality of epochs, wherein the second epoch corresponds to a second interval of time comprising the respective timestamp of each request of the second subset of the plurality of requests, and wherein the timestamp assigned to at least one request of the second subset of the plurality of requests is (i) greater than the timestamps assigned to the first subset of the plurality of requests and (ii) less than the predetermined closing time of the first epoch. ### Claim 15 (depends on 14) The method of claim 14, wherein the first epoch and the second epoch are consecutive, and wherein the second interval of time is directly after the first interval of time. ### Claim 16 (depends on 14) The method of claim 14, wherein a duration of the second interval of time is equivalent to the duration of the first interval of time. ### Claim 17 A system for managing requests comprising: a plurality of computing nodes programmed to perform operations comprising: receiving, by one or more of the plurality of computing nodes, a plurality of requests; assigning a respective timestamp to each of the plurality of requests; assigning a first subset of the plurality of requests to a first epoch of a plurality of epochs, wherein each of the plurality of epochs comprises a respective predetermined closing time of a plurality of predetermined closing times, and wherein the first epoch corresponds to a first interval of time comprising the respective timestamp of each request of the first subset of the plurality of requests; comparing a present time to the predetermined closing time of the first epoch, wherein the predetermined closing time of the first epoch is after the first interval of time and based on (i) a duration of the first interval of time and (ii) a grace period of time; and queuing, based on the comparison and when the present time is equivalent to or greater than the predetermined closing time of the first epoch, the first subset of the plurality of requests for execution in a waiting data structure by last-in, first-out (LIFO) ordering based on the respective timestamp of each request of the first subset. ### Claim 18 (depends on 17) The system of claim 17, wherein a work-sequence comprises one or more work items, and wherein the one or more work items comprise the first subset of the plurality of requests. ### Claim 19 (depends on 17) The system of claim 17, wherein each respective timestamp is assigned by a respective gateway node of the plurality of computing nodes. ### Claim 20 (depends on 17) The system of claim 17, wherein each request of the first subset of the plurality of requests is directed to a receiving node of the plurality of computing nodes. ### Claim 21 (depends on 20) The system of claim 20, wherein the present time corresponds to a time of a clock of the receiving node. ### Claim 22 (depends on 17) The system of claim 17, wherein the operations further comprise: receiving, by a receiving node of the plurality of computing nodes, the first subset of the plurality of requests. ### Claim 23 (depends on 17) The system of claim 17, wherein comparing the present time to the predetermined closing time of the first epoch further comprises: determining the present time is less than the predetermined closing time of the first epoch or determining the present time is equivalent to or greater than the predetermined closing time of the first epoch. ### Claim 24 (depends on 17) The system of claim 17, wherein the operations further comprise: queuing, based on the comparison and when the present time is less than the predetermined closing time of the first epoch, the first subset of the plurality of requests for execution in an open data structure by first-in, first-out (FIFO) ordering based on the respective timestamp of each request of the first subset. ### Claim 25 (depends on 24) The system of claim 24, wherein the operations further comprise: determining (i) the waiting data structure does not include at least one request of the plurality of requests and (ii) the open data structure includes at least one request of the plurality of requests; and dequeuing, based on the determination, the at least one request from the open data structure for execution. ### Claim 26 (depends on 24) The system of claim 24, wherein the operations further comprise: moving, based on the comparison and when the present time is equivalent to or greater than the predetermined closing time of the first epoch, the first subset of the plurality of requests from the open data structure to the waiting data structure. ### Claim 27 (depends on 17) The system of claim 17, wherein the operations further comprise: determining the waiting data structure includes at least one request of the plurality of requests; and dequeuing, based on the determination, the at least one request from the waiting data structure for execution. ### Claim 28 (depends on 17) The system of claim 17, wherein the grace period of time is selected based on an expected clock synchronization skew between the plurality of computing nodes. ### Claim 29 (depends on 17) The system of claim 17, wherein the queuing the first subset of the plurality of requests for execution in the waiting data structure further comprises: queuing the first subset of the plurality of requests for execution in the waiting data structure (i) by last-in, first-out (LIFO) ordering based on the respective timestamp of each request of the first subset and (ii) based on a respective priority level of each request of the first subset. ### Claim 30 (depends on 17) The system of claim 17, wherein the operations further comprise: assigning a second subset of the plurality of requests to a second epoch of the plurality of epochs, wherein the second epoch corresponds to a second interval of time comprising the respective timestamp of each request of the second subset of the plurality of requests, and wherein the timestamp assigned to at least one request of the second subset of the plurality of requests is (i) greater than the timestamps assigned to the first subset of the plurality of requests and (ii) less than the predetermined closing time of the first epoch. ### Claim 31 (depends on 30) The system of claim 30, wherein the first epoch and the second epoch are consecutive, and wherein the second interval of time is directly after the first interval of time. ### Claim 32 (depends on 30) The system of claim 30, wherein a duration of the second interval of time is equivalent to the duration of the first interval of time.