Sub-Linear Overhead in Static Schedules for Fault-Tolerant Transmission
Zhe Wang, Kunal Agrawal, Jeremy T. Fineman
Abstract
Shared communication media are widely used in many applications including safety critical applications such as control systems on flights or autonomous vehicles. Noise and transient errors can cause transmission failures. We consider the problem of designing fault tolerant static schedules for transmitting messages in these media. In particular, we assume that the schedule of transmission over all messages must be computed in advance and must guarantee that all messages will be delivered as long as the number of medium errors falls below a provided upper bound, regardless of when the medium errors occur. It is crucial that the messages be delivered in a timely manner, and hence we are interested in minimizing the length of the schedule that achieves the desired level of fault tolerance. In this paper, we provide an efficient algorithm for producing a schedule for n messages with total length n + O(f2log2n) that can tolerate f medium errors. We also prove that fault-tolerant schedules with length n+O(f logf logn) exist. Since n steps are required to transmit n messages, the overhead of fault tolerance is characterized by the additive terms of O(f2log2n) and O(f logf logn), respectively. Both of these terms are sublinear in n and represent asymptotic improvements to the previously best known schedule, which has overhead fn/2.
Ask Lune
Know where this paper stands in minutes, not an afternoon.
Lune can read the top-tier papers that cite it and the ones closest to it, and tells you what it claims, what came after and where it falls short, each point cited to the paper it comes from. No skimming, no AI slop.
Related papers
- Fault Tolerance in Time-Sensitive Networking with Mixed-Critical TrafficWenhong Ma, Xiangzhen Xiao, Guoqi Xie, Nan Guan et al.DAC 2023 · 15 citations
- Tight Bounds for General Computation in Noisy Broadcast NetworksKlim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh R. SaxenaFOCS 2021 · 3 citations
- Improved Shortest Path Restoration Lemmas for Multiple Edge Failures: Trade-offs Between Fault-tolerance and SubpathsGreg Bodwin, Lily WangSODA 2025
- RTailor: Parameterizing Soft Error Resilience for Mixed-Criticality Real-Time SystemsShao-Yu Huang, Jianping Zeng, Xuanliang Deng, Sen Wang et al.RTSS 2023 · 11 citations
- Constant Rate Codes for Adaptive Broadcasts Do Not ExistKlim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh R. SaxenaFOCS 2025
