Synthesizing time-triggered schedules for switched networks with faulty links

Guy, Avni and Shibashis, Guha and Guillermo, Rodriguez-Navas (2016) Synthesizing time-triggered schedules for switched networks with faulty links. In: EMSOFT: International Conference on Embedded Software, 2-7 Oct 2016, Pittsburgh, PA, USA.

[img] Text
emsoft-no-format.pdf - Accepted Version
Available under License All rights reserved.
Download (272Kb)
Official URL:


Time-triggered (TT) switched networks are a deterministic communication infrastructure used by real-time distributed embedded systems. These networks rely on the notion of globally discretized time (i.e. time slots) and a static TT schedule that prescribes which message is sent through which link at every time slot, such that all messages reach their destination before a global timeout. These schedules are generated offline, assuming a static network with fault-free links, and entrusting all error-handling functions to the end user. Assuming the network is static is an over-optimistic view, and indeed links tend to fail in practice. We study synthesis of TT schedules on a network in which links fail over time and we assume the switches run a very simple error-recovery protocol once they detect a crashed link. We address the problem of finding a (κ, ℓ)-resistant schedule; namely, one that, assuming the switches run a fixed error-recovery protocol, guarantees that the number of messages that arrive at their destination by the timeout is at least ℓ, no matter what sequence of at most κ links fail. Thus, we maintain the simplicity of the switches while giving a guarantee on the number of messages that meet the timeout. We show how a (κ, ℓ)-resistant schedule can be obtained using a CEGAR-like approach: find a schedule, decide whether it is (κ, ℓ)-resistant, and if it is not, use the witnessing fault sequence to generate a constraint that is added to the program. The newly added constraint disallows the schedule to be regenerated in a future iteration while also eliminating several other schedules that are not (κ, ℓ)-resistant. We illustrate the applicability of our approach using an SMT-based implementation.

Item Type: Conference or Workshop Item (Paper)
Additional Information: © Authors | ACM 2016. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in EMSOFT '16 Proceedings of the 13th International Conference on Embedded Software,
Subjects: 000 Computer science, knowledge & general works > 000 Computer science, knowledge & systems
Research Group: Henzinger Group
Depositing User: Guy Avni
Date Deposited: 27 Oct 2016 06:55
Last Modified: 04 May 2017 11:16

Actions (login required)

View Item View Item