Scalable leader-based total order broadcast protocol for distributed computing systems

A system of executing a leader-based, total order broadcast (LBTOB) protocol, in a Byzantine fault-tolerant, distributed computing system of nodes configured to process client requests, which comprises:

• a computer system comprising a computer readable storage medium having program instructions embodied therewith, the program instructions executable by a computer to cause the computer to:
• concurrently execute multiple instances of the LBTOB protocol at the nodes, on respective disjoint partitions of the client requests, wherein the disjoint partitions are assigned to said instances using a deterministic function of the state of the system;
• and
• multiplex outputs of the executing instances in a single, totally ordered log of the client requests, wherein the single log is maintained at each of the nodes;
• map the client requests to subdomains of a domain of the requests, so as to obtain buckets of the client requests;
• and
• at each epoch of several epochs, distribute the obtained buckets of the client requests through said instances, using said deterministic function, so as to obtain the disjoint partitions of the client requests on which the respective instances concurrently execute, wherein each position in the ordered log corresponds to a unique sequence number, which is assigned a respective one of the client requests, or a respective batch of the client requests, as a result of multiplexing said outputs of the executing instances;
• and
• the system further causes the computer to segment a portion of the ordered log corresponding to said each epoch into non-overlapping segments of sequence numbers and assigning the segments to respective ones of the instances;
• and
• the obtained buckets are distributed through said instances by causing the computer to distribute the buckets through the assigned segments at said each epoch, so as to obtain said disjoint partitions of the client requests.

A computer program product for executing a leader-based, total order broadcast (LBTOB) protocol, in a Byzantine fault-tolerant, distributed computing system of nodes configured to process client requests, the computer program product comprising a computer readable storage medium having program instructions embodied therewith, the program instructions executable by one or more processors, to:

• concurrently execute multiple instances of the LBTOB protocol at the nodes, on respective disjoint partitions of the client requests, wherein the disjoint partitions are assigned to said instances using a deterministic function of the state of the system;
• and
• multiplex outputs of the executing instances in a single, totally ordered log of the client requests, wherein the single log is maintained at each of the nodes;
• map the client requests to subdomains of a domain of the requests, so as to obtain buckets of the client requests;
• and
• at each epoch of several epochs, distribute the obtained buckets of the client requests through said instances, using said deterministic function, so as to obtain the disjoint partitions of the client requests on which the respective instances concurrently execute, wherein each position in the ordered log corresponds to a unique sequence number, which is assigned a respective one of the client requests, or a respective batch of the client requests, as a result of multiplexing said outputs of the executing instances;
• and
• the computer program product further comprising program instruction to segment a portion of the ordered log corresponding to said each epoch into non-overlapping segments of sequence numbers and assigning the segments to respective ones of the instances;
• and
• the obtained buckets are distributed through said instances by program instructions to distribute the buckets through the assigned segments at said each epoch, so as to obtain said disjoint partitions of the client requests.