Latency-Aware Leader Selection for Geo-Replicated Byzantine Fault-Tolerant Systems

In a geo-replicated setting, the response time of a leader-based Byzantine fault-tolerant (BFT) protocol often differs significantly depending on which of the replicas in the system is currently acting as leader. Identifying a single optimal leader position in general is impossible due to workload characteristics usually varying over the course of the day. As a consequence, the approach used in many existing BFT replication protocols, which assign the leader role in a static manner and only change the leader in case of suspected or detect faulty behavior, results in unnecessarily high latency in wide-area environments. In this paper we address this problem with ARCHER, a latency-aware mechanism to select the leader of a geo-replicated BFT system based on end-to-end response times measured by clients. To prevent faulty replicas from gaining an unfair advantage by sending protocol messages early, ARCHER relies on a hash-chain-based approach that enables clients to detect if a protocol phase has been skipped. In addition, ARCHER offers means to tolerate incorrect latency values reported by faulty clients and can also be extended to solve other selection problems such as the placement of active and passive replicas in resource-efficient BFT systems.