# US 11,909,528 B2 · Safely overwriting decided slots > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,909,528 B2 - Document ID: US11909528B2 - Status: Granted - Kind: B2 - Application number: 17/249,535 - Filed: 2021-03-04 - Published: 2022-09-08 - Granted: 2024-02-20 - Earliest claimed: 2021-03-04 - Assignees: Cisco Technology, Inc. - Applicants: Cisco Technology, Inc. - Inventors: Jonathan G. Rossie, Jr. - Web page: https://patentgrep.com/patent/US11909528B2 ## CPC - G06F 11/3476: {Data logging (G06F11/14, G06F11/2205 take precedence)} - H04L 1/1642: {Formats specially adapted for sequence numbers} - G06F 11/004: {Error avoidance (G06F11/07 and subgroups take precedence)} - G06F 11/3006: {where the computing system is distributed, e.g. networked systems, clusters, multiprocessor systems (multiprogramming arrangements G06F9/46; allocation of resources G06F9/50)} - G06F 16/1748: {De-duplication implemented within the file system, e.g. based on file segments (de-duplication techniques in storage systems for the management of data blocks G06F3/0641)} - G06F 16/2308: {Concurrency control (transaction processing G06F9/466)} - H04L 12/1881: {with schedule organisation, e.g. priority, sequence management} - H04L 69/12: Protocol engines - H04L 67/1095: Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## Abstract Techniques are described for safely overwriting decided slots and in-order fault tolerant consensus logs for replicated services. Using techniques described herein, a broad class of already-existing consensus log protocols may be enhanced/extended to safely overwrite decided slots and provide in-order fault tolerant consensus logs. When changing to a different epoch of a consensus log, slots determined to be unreachable may be changed/deleted even if slots after the gap were decided. A sequencer protocol establishes distributed consensus among a group of services. The sequencer protocol provides in-order execution of messages from multiple clients, and flow control from within the sequencer protocol, without offloading de-duplicate and reorder (DDRO) logic to the application layer. Fault tolerance is provided by egress cursors and ingress cursors, which provide awareness of which specific messages from each client sender should be executed next, even if those messages are not presently in the consensus log. ## Claims ### Claim 1 A method, comprising: receiving, at a sequencer process associated with implementing a consensus log, a message that indicates a proposal of initial log assignments for slots of the consensus log to transition the consensus log from a first epoch to a second epoch, wherein the sequencer process implements a consensus protocol and maintains a copy of the consensus log; storing the initial log assignments for the second epoch while maintaining current log assignments for the first epoch; determining that the second epoch is activated; and activating the initial log assignments for the second epoch, wherein one or more previously decided slots associated with the first epoch are overwritten when the second epoch is activated. ### Claim 2 (depends on 1) The method of claim 1, further comprising maintaining, at the sequencer process, first data that indicates a highest activated epoch, and wherein determining that the second epoch is activated is based, at least in part, on the highest activated epoch. ### Claim 3 (depends on 1) The method of claim 1, wherein the message includes an identity of a sender sequencer process of the message, a successor epoch ordinal, a prior epoch ordinal, the initial log assignments, and an indication of a lowest slot position above a state transfer range. ### Claim 4 (depends on 3) The method of claim 3, wherein determining that the second epoch is activated is based, at least in part, the prior epoch ordinal included in another message. ### Claim 5 (depends on 3) The method of claim 3, wherein activating the initial log assignments comprises deleting log data above the state transfer range. ### Claim 6 (depends on 1) The method of claim 1, further comprising receiving, from a different sequencer process, a second message that indicates second initial log assignments for the slots of the consensus log to transition the consensus log from the first epoch to the second epoch; transmitting, to the different sequencer process, a second acknowledgement message that acknowledges the second initial log assignments; and storing the second initial log assignments in addition to the initial log assignments and the current log assignments, and wherein activating the second epoch comprises selecting one of the initial log assignments or the second initial log assignments. ### Claim 7 (depends on 1) The method of claim 1, wherein determining that the second epoch is activated is based, at least in part, on receipt of a steady state message that proposes log assignments or acknowledges log assignments. ### Claim 8 (depends on 1) The method of claim 1, wherein determining that the second epoch is activated is based, at least in part, on a unanimous quorum of one or more sequencer processes that are associated with the second epoch. ### Claim 9 (depends on 1) The method of claim 1, wherein the initial log assignments for slots determined to be unreachable from survey results contain commands chosen by a potential leader sequencer process that transmitted the message. ### Claim 10 A system comprising: one or more processors; and one or more non-transitory computer-readable media storing computer-executable instructions that, when executed by at least one of one or more processors, cause the at least one of the one or more processors to perform actions including: receiving, at a sequencer process associated with implementing a consensus log, a message that indicates a proposal of initial log assignments for slots of the consensus log to transition the consensus log from a first epoch to a second epoch, wherein the sequencer process implements a consensus protocol and maintains a copy of the consensus log; storing the initial log assignments for the second epoch while maintaining current log assignments for the first epoch; determining that the second epoch is activated; and activating the initial log assignments for the second epoch, wherein one or more previously decided slots associated with the first epoch are overwritten when the second epoch is activated. ### Claim 11 (depends on 10) The system of claim 10, the actions further comprising maintaining, at the sequencer process, first data that indicates a highest activated epoch, and wherein determining that the second epoch is activated is based, at least in part, on the highest activated epoch. ### Claim 12 (depends on 10) The system of claim 10, wherein the message includes an identity of a sender sequencer process that sent the message, a successor epoch ordinal, a prior epoch ordinal, the initial log assignments, and an indication of a lowest slot position above a state transfer range. ### Claim 13 (depends on 12) The system of claim 12, wherein determining that the second epoch is activated is based, at least in part, the prior epoch ordinal included in another message. ### Claim 14 (depends on 12) The system of claim 12, wherein activating the initial log assignments comprises deleting log data above the state transfer range. ### Claim 15 (depends on 10) The system of claim 10, the actions further comprising receiving, from a different sequencer process, a second message that indicates second initial log assignments for the slots of the consensus log to transition the consensus log from the first epoch to the second epoch; transmitting, to the different sequencer process, a second acknowledgement message that acknowledges the second initial log assignments; and storing the second initial log assignments in addition to the initial log assignments and the current log assignments, and wherein activating the second epoch comprises selecting one of the initial log assignments or the second initial log assignments. ### Claim 16 (depends on 10) The system of claim 10, wherein determining that the second epoch is activated is based, at least in part, on one or more of receipt of a steady state message that proposes log assignments or acknowledges log assignments or on a unanimous quorum of one or more sequencer processes that are associated with the second epoch. ### Claim 17 A system comprising: one or more processors; and one or more non-transitory computer-readable media storing computer-executable instructions that, when executed by at least one of the one or more processors, cause the at least one of the one or more processors to perform actions including: transmitting a survey request to one or more sequencer processes associated with implementing a consensus log; generating, based at least in part on survey results received from the one or more sequencer processes, a message that includes initial log assignments for a second epoch that follows a first epoch of the consensus log, wherein the initial log assignments overwrite one or more previously decided slots associated with the first epoch; transmitting the message to the one or more sequencer processes; determining that the second epoch is activated; and at least partly in response to determining that the second epoch is activated, using the initial log assignments. ### Claim 18 (depends on 17) The system of claim 17, the actions further comprising: determining the one or more previously decided slots based at least in part on one or more decided values for at least one of the one or more sequencer processes above a gap detected in an instance of the consensus log associated with the at least one of the one or more sequencer processes. ### Claim 19 (depends on 18) The system of claim 18, wherein the initial log assignments contain commands chosen by a potential leader sequencer process that transmitted the message. ### Claim 20 (depends on 17) The system of claim 17, wherein determining that the second epoch is activated is based, at least in part, on a unanimous quorum of the one or more sequencer processes.