Deadline-Aware SRPT Scheduling for Paxos Consensus

Abstract

Paxos consensus protocol is widely used in distributed systems, yet their performance can degrade under heterogeneous workloads and deadline-constrained requests. Traditional priority-based Paxos extensions rely on static scheduling policies that are unable to adapt to dynamically changing urgency. This paper proposes a deadline-aware scheduling framework for Paxos based on the Shortest Remaining Processing Time (SRPT) discipline. The proposed approach dynamically prioritizes requests according to their expected completion behavior and their likelihood of meeting assigned deadlines, enabling preemptive scheduling decisions at the consensus leader. An analytical queueing model is developed to characterize the mean waiting time, mean residence time, and mean response time under SRPT scheduling. Using these results, a probabilistic measure of deadline satisfaction is derived and employed to guide scheduling decisions. Analytical and numerical evaluations demonstrate that the proposed framework significantly improves deadline satisfaction while preserving the delay-optimal properties of SRPT, making it well suited for latency-sensitive Paxos deployments.