Fewer False Deaths, Shorter Tails: Failure Detection and Request Routing for a Dynamo-Style Key-Value Store

Dynamo-style key-value stores trade consistency for availability, but two parts of their design remain fragile. Failure detection relies on fixed timeouts, so packet loss or a slow node makes healthy nodes look dead, while longer timeouts delay the detection of real failures. Request handling sends every read to all replicas and spreads keys, not traffic, so one slow replica inflates tail latency and one popular key overloads its replicas. We build a complete Dynamo-style store with SWIM membership in a deterministic simulator and replace these two parts. Suspicion lasts longer when it is unconfirmed and shortens as independent nodes confirm it; reads go to the replicas that have answered fastest lately, are hedged when slow, avoid overloaded nodes, and spread hot keys over temporary extra replicas. Against a classic baseline on identical seeds and faults, false death verdicts at 20% packet loss fall from 77.7 to 0.3 per run, the 99th-percentile latency with one slow node falls from 1338 ms to 210 ms, and a key receiving half of all traffic leaves the busiest node at 1.16x the average load instead of 2.25x. The costs are about 0.5 s slower failure detection on a clean network, 2 s under high latency, and 5-8 ms per request when nothing is wrong.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-15
DOI
https://doi.org/10.5281/zenodo.24243378
Primary Topic
Distributed systems and fault tolerance
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Fewer False Deaths, Shorter Tails: Failure Detection and Request Routing for a Dynamo-Style Key-Value Store

Martim Baltazar
Zenodo (CERN European Organization for Nuclear Research)
Distributed systems and fault tolerance
preprint

Fewer False Deaths, Shorter Tails: Failure Detection and Request Routing for a Dynamo-Style Key-Value Store

Martim Baltazar
preprint en

Abstract

Dynamo-style key-value stores trade consistency for availability, but two parts of their design remain fragile. Failure detection relies on fixed timeouts, so packet loss or a slow node makes healthy nodes look dead, while longer timeouts delay the detection of real failures. Request handling sends every read to all replicas and spreads keys, not traffic, so one slow replica inflates tail latency and one popular key overloads its replicas. We build a complete Dynamo-style store with SWIM membership in a deterministic simulator and replace these two parts. Suspicion lasts longer when it is unconfirmed and shortens as independent nodes confirm it; reads go to the replicas that have answered fastest lately, are hedged when slow, avoid overloaded nodes, and spread hot keys over temporary extra replicas. Against a classic baseline on identical seeds and faults, false death verdicts at 20% packet loss fall from 77.7 to 0.3 per run, the 99th-percentile latency with one slow node falls from 1338 ms to 210 ms, and a key receiving half of all traffic leaves the busiest node at 1.16x the average load instead of 2.25x. The costs are about 0.5 s slower failure detection on a clean network, 2 s under high latency, and 5-8 ms per request when nothing is wrong.

Zenodo (CERN European Organization for Nuclear Research)
Distributed systems and fault tolerance
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon
Fewer False Deaths, Shorter Tails: Failure Detection and Request Routing for a Dynamo-Style Key-Value Store — Martim Baltazar · Zenodo (CERN European Organization for Nuclear Research) (2026) | TGRS Research Map | TGRS