Quadratic worst-case message complexity for State Machine Replication in the partial synchrony model

We consider the message complexity of State Machine Replication protocols dealing with Byzantine failures in the partial synchrony model. A result of Dolev and Reischuk gives a quadratic lower bound for the message complexity, but it was unknown whether this lower bound is tight, with the most efficient known protocols giving worst-case message complexity O(n^3). We describe a protocol which meets Dolev and Reischuk’s quadratic lower bound, while also satisfying other desirable properties. To specify these properties, suppose that we have n replicas, f of which display Byzantine faults (with n≥3f+1). Suppose that Δ is an upper bound on message delay, i.e. if a message is sent at time t, then it is received by time max{t,GST}+Δ. We describe a deterministic protocol that simultaneously achieves O(n^2) worst-case message complexity, optimistic responsiveness, O(fΔ) time to first confirmation after GST and O(n) mean message complexity.

Message Goat, pdf

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s