  Most methods for Byzantine fault tolerance (BFT) in the partial synchrony
setting divide the local state of the nodes into views, and the transition from
one view to the next dictates a leader change. In order to provide liveness,
all honest nodes need to stay in the same view for a sufficiently long time.
This requires \emph{view synchronization}, a requisite of BFT that we extract
and formally define here.
  Existing approaches for Byzantine view synchronization incur quadratic
communication (in $n$, the number of parties). A cascade of $O(n)$ view changes
may thus result in $O(n^3)$ communication complexity. This paper presents a new
Byzantine view synchronization algorithm named Cogsworth, that has
optimistically linear communication complexity and constant latency. Faced with
benign failures, Cogsworth has expected linear communication and constant
latency.
  The result here serves as an important step towards reaching solutions that
have overall quadratic communication, the known lower bound on Byzantine fault
tolerant consensus. Cogsworth is particularly useful for a family of BFT
protocols that already exhibit linear communication under various
circumstances, but suffer quadratic overhead due to view synchronization.
