Fault-tolerant Transmission of Messages of Differing Criticalities across a Shared Communication Medium

We discuss the motivation behind, and the design and analysis of, an algorithm for synthesizing communication schedules for shared media networks in some safety-critical hard-real-time applications such as autonomous navigation and factory automation. Communication media may be inherently noisy in many such environments, and occasional transmission errors hence inevitable. Therefore it is essential that some degree of fault-tolerance be built into the communication protocol that is used - in some safety-critical application domains, fault-tolerance requirements may be mandated by statutory certification requirements. Since the severity of the consequences of failing to successfully transmit different messages may be different, we consider a mixed-criticality setting in which the fault-tolerance requirement specification for messages are dependent on their criticality: more critical messages are required to be able to tolerate a larger number of faults. We advocate that communication schedules be “as static as possible” in safety-critical applications in order to facilitate verification and validation, and discuss the synthesis of semi-static schedules - schedules that are driven by precomputed lookup tables - with the desired fault-tolerance properties for such applications.