combines it together with the message, which arrives at time 19 into an output message set, which is sent to the fusion task. Then, the fusion task sends the message to the actuator task at time 26, and the actuator task finishes its execution at time 28. Note that the messages arriving at time 7 and 13 will be discarded and not included in any output message sets.

In this example, the passing latency of the message arriving at time 19 caused by the synchronizer is the time difference between its arrival at time 19 and the publishing of the output message set at time 24, i.e., 24 -19 = 5. The corresponding end-to-end delay is the duration from the start time of sensor task 1 at time 18 to the completion of the actuator task at time 28, i.e., 28-18 = 10, which includes the passing latency from time 19 to 24. The reaction latency is the time duration from the arrival of the message at time 1 to the publishing of the output message set at time 24, i.e., 24 -1 = 23, which includes the passing latency and the extra latency caused by the discarded messages. And the corresponding end-to-end reaction time is the time duration from the occurrence of event B at time 0 to the completion of the actuator task at time 28, i.e., 28 -0 = 28, which includes the reaction latency from time 1 to 24.

It is worth mentioning that the reaction latency of the synchronizer is defined regarding the arrival time of the last nondiscarded message but not the occurrence time of the external event, which seems problematic. For example, if an external event A occurs at time 10, then the end-to-end reaction time regarding this event should be 28 -10 = 18. However, by our definition, the reaction latency of the synchronizer is 24 -1 = 23, which is larger than the end-to-end reaction time 28 -10 = 18. This is actually not a problem as our interest is to analyze the worst-case end-to-end reaction time no matter when the event actually occurs. The worst-case scenario is that the external event happens right after the sampling time of the last non-discarded message (event B in Fig. 2-(b)). Therefore, the worst-case time gap between the occurrence of event B and the generation of the first output message group containing the information of event B (24 -0 in this example) equals the sum of two parts (1) the difference between the timestamp of the last non-discarded message and its arrival time to the synchronizer (1 -0 in this example) and (2) the reaction latency (24 -1 in this example). The former can be bounded using existing response time analysis techniques, while analyzing the latter is the goal of this paper. In summary, we define the reaction latency of the synchronizer assuming the worst-case scenario, i.e., the external event occurs right after the sampling time of the last non-discarded message. In this way, the definition of the reaction latency is simple yet sufficient to serve the purpose of bounding the worst-case endto-end reaction time.

There are two synchronization policies in ROS, i.e., the Exact Time policy [28] and the Approximate Time policy [29]. The Exact Time policy only combines messages from different input channels with exactly the same timestamp into an output set and discards any messages without an exact match. As a result, any output message set published under the Exact Time policy will have a time disparity of 0. However, in reality, it is too restrictive to require data from different sensors to have exactly the same timestamp, so the Exact Time policy is rarely used in practice. Consequently, we focus on the Approximate Time policy in this paper, which is used to combine messages under a certain tolerance of time disparity. Please note that the model and results of this paper apply to both ROS 1 (the first generation of ROS) and ROS 2. More specifically, the Approximate Time policy is the same for all ROS 1 C++ versions since Diamondback and ROS 2 C++ versions until the latest Rolling, which was also stated in [3]. For the sake of brevity, we use the term "ROS" in this paper to include both ROS 1 and ROS 2. Throughout the remainder of this paper, we will use the term "policy" or "synchronization policy" interchangeably to represent the Approximate Time policy. In this paper, we adopt the abstract model presented in [3], but to keep our paper self-contained, we will provide a detailed explanation of this model in its entirety. We first define some concepts, followed by the abstract policy model.

We use S = {m 1 , ..., m N } to denote a regular set containing N messages, each of which comes from a different queue. The time disparity of a regular set is defined as: Definition 3 (Time Disparity). Let S = {m 1 , ..., m N } be a regular set. The time disparity of S, denoted by ∆(S), is the maximum difference between the timestamps of the messages in S, i.e.,

Each queue Q i stores not only messages that are already arrived (called arrived messages), but also an artificial predicted message at the end of Q i . The timestamp of a predicted message is set based on the timestamp of the latest arrived message in Q i and T B i . It is important to note that the selection procedure of the output message set is not solely based on the arrived messages but also considers the predicted messages, which can provide auxiliary information for the selection procedure. Nevertheless, a predicted message is never included in output message sets. Suppose there are currently k messages

When the system starts at time 0, a predicted message with timestamp 0 was initially put into each queue. Note that sometime a queue may only have a predicted message but no arrived message.

Definition 4 (Pivot). Let S 1 = {m 1 1 , ..., m 1 N }, where each m 1 i is the arrived message with the earliest timestamp in Q i . The pivot m P is the one with the largest timestamp among all elements in S 1 . If several messages in S 1 all have the latest timestamp, the message with the maximum queue number is the pivot.

The queue to which the pivot belongs is denoted as the pivot queue, while the remaining queues are denoted as the non-pivot queues. We use Λ to denote all the regular sets corresponding to the pivot m P . Note that the regular sets in Λ consist of messages currently in queues (either arrived or predicted) and must include m P . The selected set has the smallest time disparity among all regular sets in Λ.

Definition 5 (Selected Set). Let m P be a pivot and Λ be the corresponding set of the regular sets that include m P . The selected set is the set that has the smallest time disparity among all elements in Λ. If multiple elements in Λ all have the smallest time disparity, the selected set S = {m 1 , ..., m N } must satisfy the following condition: there does not exist another regular set

A selected set can include both arrived messages and predicted messages. We call a selected set containing only arrived messages a published set (denoted as S PUB ). The messages in a published set are called published messages. If the selected set contains any predicted messages, the synchronizer must wait for them to arrive. Intuitively, the predicted message(s) can be used to combine a regular set with a smaller time disparity compared with the current selected set. However, in the case of

i , a message may arrive with a larger timestamp than predicted. If the difference between the actual and predicted timestamp is significant, the message cannot be included in a selected set as expected. Therefore, the synchronizer can waste some time waiting for messages to arrive, further contributing to passing latency or reaction latency. The insight here is that if the predicted timestamp is too large (e.g., the difference between the predicted timestamp and the timestamp of the pivot exceeds the worst-case time disparity of the published set), the synchronizer does not need to wait for the predicted message, thereby to avoid wasting time. We will explain more about the above insights as well as the aspects relevant to the passing latency and reaction latency with an illustrative example in Section III-B.

When a new message m i arrives, the synchronizer will invoke Algorithm 1. First, the last message (must be a predicted message) is discarded from Q i (Line 1). Then, m i is put into the end of Q i , which then is followed by a new predicted message with timestamp τ (m i )+T B i (Line 2-3). After that, the pivot is set (Line 5) once there is at least one arrived message in each queue. And a selected set can only be obtained (Line 7) if all predicted messages have timestamps greater than τ (m P ). If the selected set only contains arrived messages, it will be published and all published messages should be discarded from the queues. Additionally, the messages earlier than the published messages will also be discarded from the queues, which are not included in any published sets (Line 8-11). Otherwise, if a selected set contains one or several predicted messages, Algorithm 1 exits immediately to wait for the predicted message(s) to arrive. We assume that the time required by Algorithm 1 to identify a selected set is negligible, i.e., it is considered to be 0. This assumption is made to simplify our analysis and to focus solely on the latency caused by waiting for messages to arrive and also the discarded messages. Furthermore, we use ∆ to represent the upper bound of time disparity for any published set, which is equal to the RHS of (12) in [3].

We use Fig. 3 to illustrate Algorithm 1. The x-axis represents the timestamp and the messages' arrival time is not explicitly depicted in the figure. The downward arrows represent the messages buffered in the queues.

At some time point, a message with timestamp 0 arrives in Q 3 and is set as the pivot as shown in Fig. 3-(a). The message set {m 1 1 , m 1 2 , m 1 3 } in Fig. 3-(a) is the first published set and the corresponding published messages will be discarded from the queues. Then, a message with timestamp 10 arrives at Q 3 , which is set as the new pivot as shown in Fig. 3-(b). Please note that the indexes of messages are automatically updated in Algorithm 1 after discarding messages. For example, from Fig. 2-(a) to Fig. 2-(b), the notation of the message with timestamp of 3 in Q 1 is updated from m 2 1 to m 1 1 after m 1 1 with timestamp 0 is discarded.

The regular set {m 3 1 , m 2 2 , m 1 3 } in Fig. 3-(b) has the minimum time disparity, so it is the selected set. However, it cannot be published since m 2 2 is a predicted message. So the synchronizer will wait for m 2 2 to arrive. At some later point, m 4 1 and m 2 2 arrive successively as illustrated in Fig. 3-(c). Then the selected set {m 3 1 , m 2 2 , m 1 3 } in Fig. 3-(c) will be published

Below, we derive the second upper bound for the passing latency by dividing the published set S PUB into three casesfoot_0 :

• Case 1: all published messages in S PUB from non-pivot queues have timestamp later than τ (m P ). • Case 2: all published messages in S PUB from non-pivot queues have timestamp earlier than τ (m P ). • Case 3: some published messages in S PUB have timestamp earlier than τ (m P ), while others' timestamp is later than τ (m P ). We begin by demonstrating that in Case 1, the term M in inequality (1) can be simplified to only account for the delay element D W j , without the need to consider the minimal timestamp difference element T W j . Lemma 5. Let S PUB be any arbitrary published set and m P ∈ S PUB be the pivot. If S PUB falls into Case 1, the passing latency experienced by m

Proof. The published message in each non-pivot queue must be the first message with a timestamp later than τ (m P ). When the latest arrived message m L ∈ S PUB arrives, a selected set can be obtained from Line 7 in Algorithm 1. This selected set does not contain any predicted messages and must be the published set S PUB . So we have t f = α(m L ). Since both m L and m P are included in S PUB , we can have τ (m L ) ≤ τ (m P ) + ∆. In the worst-case, m ρ(i) i can be m P . So, we have

The lemma is proved.

The key insight learned from Lemma 5 is that in Case 1, the latest arrived message is precisely the last one that Algorithm 1 should wait for, leading to the published set being obtained at the time t f = α(m L ). In this case, the algorithm only needs to wait for all published messages included in the published set to arrive. However, in Case 2 or Case 3, there is a possibility that Algorithm 1 may need to wait for additional messages to arrive, even if the latest arrived message m L has already been arrived (i.e., all published messages have already arrived). More specifically, certain predicted messages have the potential to be included a selected set with a smaller time disparity. If these messages arrive with the predicted timestamps, the time disparity of the published set could be reduced. However, it is possible that they may arrive with timestamps that are later than predicted, thus disqualifying them from being included in a selected set, thereby prolonging the passing latency. In this case, the publishing time t f > α(m L ) must hold. For example, in Fig. 3-(d), m 3 1 is a predicted message with a timestamp of 21. The selected set is {m 3 1 , m 2 2 , m 1 3 }. Suppose that m 2 2 and m 3 2 arrive at Q 2 , and then m 3 1 arrives with a timestamp of 31, as shown in Fig. 3-(e). Therefore, the published set will be {m 2 1 , m 2 2 , m 1 3 }, and we have

1 ≥ 4, Algorithm 1 would not wait for m 3 1 to arrive. In both Case 2 and Case 3, the challenge is to identify and exclude those predicted messages that will not be waited for (after m L arrives), so that we can reduce the pessimism in the analysis of passing latency. Below, we first introduce how to do this by adding constraints on the minimal timestamp difference T B j in Lemmas 7 and 8 for Case 2 and Case 3. Then we analyze how to incorporate these constraints into the term M for Case 2 (in Lemma 9) and Case 3 (in Lemma 10). Lemma 6. Let m P be any pivot, and S be a selected set corresponding to m P . If m j ∈ S is a predicted message in Q j (j ∈ [1, N ]), then it satisfies:

• τ (m j ) > τ (m P ), and • ∄m ′ j : τ (m P ) < τ (m ′ j ) < τ (m j ). Proof. By line 6 of Algorithm 1, S can only be obtained when all predicted messages have timestamps later than τ (m P ). m j is a predicted message so τ (m j ) > τ (m P ) must hold. We can assume that there exist m ′ j in Q j such that τ (m P ) < τ (m ′ j ) < τ (m j ). Therefore, m ′ j must be an arrived message and τ (m ′ j )τ (m P ) < τ (m j )τ (m P ). We can construct a regular set S ′ with all messages in S, replacing only m j with m ′ j . Then, we have ∆(S ′ ) ≤ ∆(S), which contradicts the fact that S is a selected set. The lemma is proved.

In the following, we analyze the constraints on T B j under the context that for any pivot m P , the corresponding published set S PUB falls into Case 2 or Case 3, m L ∈ S PUB is the latest arrived message, and S is a selected set obtained by Algorithm 1 not earlier than α(m L ).

We prove this by contradiction, assuming T B j > 2∆. By Lemma 6, m ρ(j)-1 j is an arrived message satisfying:

Since S PUB falls into Case 2 or Case 3, the published message (it must be an arrived message) m ρ(j)-x j ∈ S PUB (x ∈ N + ) must satisfy:

The predicted message m ρ(j) j has a timestamp τ (m

) + T B j . Combining it with ( 4) and ( 3), we have τ (m ρ(j) j

)τ (m P ) > ∆. Therefore, any regular set containing m ρ(j) j and m P will have a time disparity greater than ∆. Since S is obtained not earlier than α(m L ), there must exist a regular set that contains only arrived messages (which actually is the published set for m P ) and it has a time disparity less than ∆. So, the synchronizer will not wait for m ρ(j) j to arrive in any case, i.e., m ρ(j) j can not be included in the selected set S, which contradicts the prerequisite m ρ(j) j ∈ S. Therefore, our assumption is incorrect and T B j ≤ 2∆ must hold. Lemma 7 states that in both Case 2 and Case 3, the selected set obtained not earlier than α(m L ) for a given pivot can only include the predicted messages from the non-pivot queue Q j that satisfies the condition T B j ≤ 2∆. These predicted messages will be waited to arrive until the publishing time. It is noted that the above condition is necessary but not sufficient.

) must satisfy 4 :

Proof. Since the predicted message m ρ(j) j is included in S, τ (m ρ(j) j

)τ (m P ) must not be large than ∆, i.e., τ (m

Lemma 8 reveals that for any pivot, when ∆ ≤ T B j ≤ 2∆, the predicted messages in Q j can be included into a selected set and then be waited for arrival before the selected set for this pivot can be published, but only if the condition specified in Eq. ( 5) is satisfied.

To derive the upper bound for Case 2 and Case 3, we first introduce some auxiliary notations. For any pivot m P , the time disparity of its published set is upper-bounded by ∆. We define two sets for the queue index j:

Lemma 9. Let S PUB be any arbitrary published set and m P ∈ S PUB be the pivot. If S PUB falls into Case 2, the passing latency experienced by m

where

Proof. Suppose that before publishing S PUB , m ρ(j) j

(j ∈ [1, N ]) be the first message, that arrives in Q j , with a timestamp of τ (m ρ(j) j ) > τ (m P ). By Lemma 7, the synchronizer 4 Of course, there exists a minimal limit as well, i.e., τ (m ρ(j)-1 j ) > τ (mP) -∆. However, our focus here lies on the maximum limit. waits for m ρ(j) j to arrive only if T B j ≤ 2∆. When j ∈ φ 2 , by Lemma 8, the message m ρ(j)-1 j has a maximum timestamp value of τ (m ρ(j)-1 j ) = τ (m P ) + ∆ -T B j . Therefore, the timestamp of m ρ(j) j (when it arrives) must satisfy

When j ∈ φ 1 , the message m ρ(j)-1 j has a timestamp not later than τ (m P ). In the worst case, we have

be the first message with a timestamp larger than τ (m P ) in Q h , and let it be the last one to arrive among all such messages in the queues. Based on Eqs. ( 7) and ( 8), we can derive

Proved.

Lemma 10. Let S PUB be any arbitrary published set and m P ∈ S PUB be the pivot. If S PUB falls into Case 3, the passing latency experienced by m

) be the first message that arrives in Q j before publishing S PUB and τ (m ρ(j) j ) > τ (m P ). Let τ (m P ) + σ (0 < σ < ∆) be the timestamp of the published message that has the latest timestamp among all messages in S PUB . By Lemma 7, T B j ≤ 2∆ must hold. Similarly, we have τ (m

is the first message with a timestamp larger than τ (m P ) in Q h , and let it be the last one to arrive among all such messages in the queues. We have

In conclusion, the lemma is proved.

Theorem 2 (Passing Latency Upper Bound 2). Let S PUB be any arbitrary published set. The passing latency experienced by m ρ(i) i ∈ S PUB is upper-bounded by

reach the same evaluation conclusion for all other channels.

To further demonstrate this, we also illustrate the results of all six channels in Fig. 6-(b) as an example, where we use the same setting as Fig. 6-(a), except that the number of channels was kept constant at 6. In Fig. 6-(c), the messages are no longer generated periodically, but with timestamp separation randomly distributed between T B i and T W i , and the ratio between T W i and T B i varies as indicated by the x-axis. In Fig. 6-(d), we use the same setting as in Fig. 6-(a), but set the number of channels to 6 and change the range of delay experienced by each message as shown by the x-axis.

For the reaction latency evaluation, we use the same setting in Fig. 7-( 7-(c) and (d)). And an example with the results of all six channels is illustrated in Fig. 7-(b).

From the experiment results in Fig. 6-(a) to (d), we can see that our upper bounds for the passing latency (Theorem 1 and 2) have good precision. As depicted in Fig. 6-(c), as the ratio between T W i and T B i increases, particularly at ratios of 1.6 and 1.8), the difference between Upper Bound 1 and Upper Bound 2 becomes negligible. The reason is that as the ratio increases, it exacerbates the difference between T B i and T W i . Since ∆ is calculated based on T W i , T B i > ∆ can always hold, and the constraints introduced in the second upper bound for the passing latency become invalid. From the experiment results (Fig. 7-(a) to (d)), we can know that our upper bound for the reaction latency (Theorem 3) has a certain level of pessimism. Further analysis and refinement may be necessary to assess the upper bound accurately.

Based on the experiment results, we can observe that the synchronization policy can produce considerable latency. As illustrated in Fig. 6-(

Data fusion algorithms are commonly developed with the assumption that data from multiple sensors are perfectly aligned, although this is rarely the case in reality. To address this issue, various techniques have been proposed to compensate for the temporal inconsistency of input data [30]- [33], which only work when the temporal inconsistency falls within a certain range. Message synchronization before data fusion is a crucial component that warrants careful consideration and attention. Previous studies [2], [34]- [36] have focused on precisely timestamping sensor data in the context of multisensor data fusion. In this paper, we assume that sensor data has already been associated with valid timestamps in the same coordinate system using these existing techniques. Our focus is on the problem that arises after timestamping, i.e., the latency caused when managing the sensor data flows in the computing system based on these timestamps.

In recent years, some work has been conducted on formal real-time performance analysis of ROS2, such as exploring response time analysis by modeling execution of ROS2 applications as processing chains or a DAG [16], [17], [20], [22], [24] executing on the ROS2 default scheduler, i.e., the executor. [18], [21], [23], [24] proposed to address the limitations of the default scheduling strategy of ROS2 by enhancing or redesigning the executor. In [19], the authors propose an automatic latency manager that applies existing real-time scheduling theory to latency control of critical callback chains in ROS2 applications. [14] proposed an end-to-end timing analysis for cause-effect chains in ROS2, considering the maximum end-to-end reaction time and maximum data age metrics. However, all of the research mentioned above focuses solely on the executor component in ROS2 only for the endto-end latency (response time) analysis without considering the Message Synchronizer. [37] proposed a synchronization system implemented in a node to harmonize communication between nodes, which works similarly to the message synchronization policy in ROS. Recent work [3], [7] modeled the message synchronization policy in ROS and formally analyzed the worst-case time disparity of the output message set as well as the important properties of the policy. However, their analysis only focuses on the time disparity metric and neglects to consider the latency caused by the policy, which is closely tied to end-to-end latency and is a critical factor in the reaction time of the system as a whole.

Previous research on real-time scheduling and analysis has investigated various real-time performance metrics, including response time [38], [39], tardiness [40] and data freshness [10]- [13], [41]. However, these analysis techniques cannot be directly applied to ROS systems. Furthermore, analyzing latency associated with the message synchronization policy in ROS remains an open research question.

In this paper, we explore two types of latency metrics associated with the ROS message synchronization policy, i.e., the passing latency and the reaction latency, and formally analyze the upper bounds for both latency. We conduct experiments under different settings, including the different number of channels, the varied data sampling periods, and the random delay time experienced by messages before arriving at the synchronization policy, to evaluate the precision of our proposed latency upper bounds against the maximal observed latency in real execution. In the future, we plan to improve the design and implementation of the ROS message synchronization policy, considering both the time disparity and latency aspects, with the ultimate goal of achieving better real-time performance in ROS systems.