Correctness of a Fault−Tolerant Real−Time Scheduler and its Hardware Implementation

Abstract

We formalize the correctness of a fault-tolerant scheduler in a time-triggered architecture. Where previous research elaborated on real-time protocol correctness, we extend this work to gate-level hardware. This requires a sophisticated analysis of analog bit-level synchronization and transmission. Our case-study is a concrete automotive bus controller (ABC), inspired by the FlexRay standard. For a set of interconnected ABCs, vulnerable to sudden failure, we prove at gate-level, that all operating ABCs are synchronized tightly enough such that messages are broadcast correctly. This includes formal arguments for startup, failures, and reintegration of nodes at arbitrary times. To the best of our knowledge, this is the first effort tackling fault-tolerant scheduling correctness at gate-level.