Zijian Qin will present his General Exam "Avicenna: Fail-Slow Fault-Tolerant Replicated State Machines Using Counterfactual Evaluation" on Weds 5/6/2026 at 9:30am at 194 Nassau St, R. 213. Committee: Wyatt Lloyd (adviser), Jialin Ding, Mae Milano Abstract: Geo-distributed replicated state machines (RSMs) are at the heart of many production distributed systems, offering linearizability and fault tolerance via consensus protocols. Most existing protocols target crash fault tolerance, however, and are vulnerable to fail-slow faults, where a single slow replica can significantly degrade system latency. Existing protocols that tolerate fail-slow faults do so with much higher normal-case latency in geo-distributed settings. Avicenna is the first consensus protocol for geo-distributed RSMs that maintains low normal-case latency while tolerating a single fail-slow replica. Avicenna uses a single leader to order commands, naturally tolerating a fail-slow follower. To tolerate a fail-slow leader, Avicenna compares the current latency with the counterfactual latency clients would experience if a different replica, the shadow leader, were the leader. When that comparison indicates the current leader might be slow, Avicenna quickly promotes the shadow leader with a fast leader rotation protocol. Our evaluation shows Avicenna has the same normal-case latency as Multi-Paxos while tolerating fail-slow faults. Reading List: [ https://docs.google.com/document/d/1tSJQW1Z5HbBKJgwAZj09oknyg1-nWeyidS04n4-L... | https://docs.google.com/document/d/1tSJQW1Z5HbBKJgwAZj09oknyg1-nWeyidS04n4-L... ]