Targeting Tail Latency in Replicated Systems with Proactive Rejection

When put under stress, traditional state-machine replication protocols typically exhibit response times that by far exceed the average level of normal-case operation. The common way to mitigate such overload-induced tail latency is to overprovision computing and network resources. However, this method often leads to large amounts of resources left unused over extended periods of time, especially in application scenarios in which high loads are mostly limited to short phases. In this paper, we circumvent the need for overprovisioning with Idem, a replication protocol specifically designed to process client requests with low latency even during load spikes. Most notably, Idem replicas avoid overload by proactively rejecting requests in a collaborative manner. In contrast to centralized overload-prevention strategies, the collaboration among replicas allows Idem to always timely notify clients about rejections of their requests, not only under favorable conditions but also in the presence of replica crashes.