BYZANTINE AGREEMENT USING COMMUNICATIONS HAVING LINEAR COMPLEXITY

In some embodiments, a method receives a share of a signature of a decision block from at least a portion of the plurality of replicas. The share of the signature being generated when a respective replica signs the decision block and the decision block includes a set of requests from a client for a service. A combined signature is created based on the share of the signature block from at least the portion of the plurality of replicas. The method broadcasts a message that includes the combined signature to the plurality of replicas. The plurality of replicas use the combined signature to determine whether to process the decision block for the service.