Abstract
The Time-triggered Architecture (TTA) is a widely-recognized design framework for large distributed embedded real-time systems. This paper derives an elaborated startup scheme and discusses its temporal boundary for TTA-based systems, which require predictable communication in TDMA environments. The scheme introduces an arrival time window (ATW) with a dedicated lower time boundary for contention resolution during the startup phase without direct collision detection. While previous model checking approaches have analyzed startup temporal attributes, they struggle with arbitrary node counts and propagation delays. This paper provides the upper boundary of startup time for TTA systems with an arbitrary number of nodes through formal deduction.
Introduction
In safety-critical domains like aerospace and autonomous vehicles, timing is a fundamental safety requirement. Time-Triggered Architecture (TTA) ensures predictability by following a strict, pre-planned schedule. However, a critical challenge arises at system power-on: nodes start with independent internal clocks and must synchronize to a common "Time Zero" to establish the Time Division Multiple Access (TDMA) schedule without signal interference.
The Challenge of Startup in TTA
In a TTA system utilizing a bus topology, nodes are assigned specific time slots for communication. At startup, the system is asynchronous, necessitating a robust algorithm to transition nodes from individual clocks to a synchronized cluster.
The primary obstacle is contention. Physical contention occurs when signals overlap on the bus, while logical contention arises when propagation delays cause nodes to misinterpret the bus state. Traditional collision detection (like CSMA/CD) is often insufficient for TTA due to these propagation effects. Previous research relied heavily on model checking, which is limited by specific scenarios and cannot easily generalize to systems with an arbitrary number of nodes ($n$) or varying propagation delays ($\Delta_{prop}$).
Proposed Startup Scheme and Arrival Time Window
The authors propose an elaborated startup scheme based on a Finite State Machine (FSM) and a novel Arrival Time Window (ATW). Nodes transition through states—INIT, LISTEN, COLDSTART, and SYNC—based on bus activity.
The ATW (labeled as AT in the diagram) is central to resolving logical contention. When a node detects a signal, it opens an ATW to judge if the frame is valid for synchronization or a result of a collision. The authors determine that for effective contention resolution, the ATW's lower boundary must be at least $2\Delta_{prop} + \Delta_{frame}$. This mechanism allows nodes to accept valid frames earlier than standard schemes, potentially reducing overall startup time.
Formal Analysis and Results
Using formal deduction rather than simulation, the paper establishes a universal upper boundary for the startup process. The analysis divides startup into two phases:
- Contention Eliminating Phase: Ensuring overlapping startup attempts are resolved. Max duration: $2\Delta_{TDMA} - \Delta_{PSP} + \Delta_{prop}$.
- Clique Detecting Phase: Ensuring all nodes agree on the same schedule. Max duration: $(n - 1)\Delta_{slot} + \Delta_{PSP}$.
By combining these phases, the authors prove that the total Upper Boundary of Startup Time ($\Delta_{UBS}$) for a fault-free system is: $$\Delta_{UBS} = 3n\Delta_{slot}$$
This result provides a concrete worst-case bound that is independent of specific node configurations, offering a reliable metric for system designers to set timeouts and diagnostic parameters.
Conclusion and Future Work
This work fills a gap in TTA research by providing a mathematically rigorous upper bound for startup synchronization in bus topologies. While the current analysis assumes a fault-free environment, it establishes a foundation for future studies to incorporate fault models, such as "babbling idiot" nodes or transient signal failures. Additionally, extending this formal boundary analysis to star or mesh topologies remains an area for further exploration.
Summary updated