English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

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

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