Working Notes: What Raft Actually Guarantees

Safety properties (hold unconditionally)

Election safety. At most one leader can be elected in any given term $t$.

Log matching. If two logs contain an entry with index $i$ and term $t$, then the logs are identical in all entries up through index $i$. Formally, for logs $L_a$ and $L_b$:

Leader completeness. If entry $e$ is committed in term $t$, then $e$ is present in the log of every leader elected in any term $t' > t$.

State machine safety. If server $s_i$ applies log entry at index $i$ to its state machine, no server $s_j$ will ever apply a different entry at index $i$.

Liveness requires timing

Raft guarantees progress only under partial synchrony. Specifically, the system makes progress if:

where $\text{broadcastTime}$ is the average round-trip time, $\text{electionTimeout}$ is the window before a follower starts an election, and $\text{MTBF}$ is the mean time between server failures.

There is no liveness guarantee in a fully asynchronous model — a direct consequence of the FLP impossibility result, which states that no deterministic consensus protocol can guarantee termination if even one process may fail.

The election timeout problem

In practice the optimal timeout $\tau^*$ minimises:

for some weights $\alpha, \beta > 0$. The two terms pull in opposite directions: smaller $\tau$ reduces recovery latency after a genuine failure but increases spurious elections under network jitter. The original paper recommends $\tau \in [150\text{ms}, 300\text{ms}]$ — essentially a guess for a LAN. In a geo-distributed deployment it is almost certainly wrong in one direction or the other.

AdaptRaft treats $\tau$ as a bandit action and learns $\tau^*$ online from observed round-trip times and election frequency.