Increasing fault tolerance in a multi-node replication system

Abstract

The disclosed technology includes fault-tolerant data replication system implemented by a cluster of compute devices. The system includes a witness comprising persistent data storage and multiple nodes configured to selectively execute leader node operations when serving as a leader of the cluster. The leader node operations include detecting an availability status change for a follower node of the cluster and, in response, updating a subterm and a replication set. The subterm identifies a total number of availability status changes detected within the cluster over a given time interval, and the replication set identifies set of entities designated to provide acknowledgments counted when determining whether to commit a message following message replication. The leader node operations further include writing the replication set, the subterm, and other metadata to the witness in response to receiving a first client message from a client application following the availability status change.