Definition 3 (Selected Set). Let Λ be the set of all regular message sets consisting of messages currently in queues (either arrived or predicted) and including the pivot. The selected set 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 element S ′ = {m ′ 1 , ..., m ′ N } in Λ s.t. (i) ∆(S ′ ) = ∆(S) and (ii) ∃m i ∈ S : t(m ′ i ) < t(m i ). If only one regular message set in Λ has the smallest time disparity, it is clearly the selected set. If multiple regular message sets in Λ all have the smallest time disparity, according to the second half of Definition 3, the one with as-early-aspossible messages is the selected set. For example, in Fig. 3, among all regular message sets including the pivot m 1 4 , the two sets S = {m 2 1 , m 2 2 , m 3 3 , mfoot_0 4 } and S ′ = {m 2 1 , m 2 2 , m 4 3 , m 1 4 } both have the smallest time disparity 6. According to the second half of Definition 3, S ′ is not the selected set because there exists S containing m 3 3 which is earlier than its correspondence m 4 3 in S ′ . S is the selected set, because there is no other regular message set containing the pivot has the same time disparity as S and satisfies ∃m i ∈ S : t(m ′ i ) < t(m i ). Although the selected set is defined as selecting among all regular message sets including the pivot, which could be exponentially many, it is found by a polynomial-time procedure in its implementation in the ROS Message Synchronizer. As we aim to provide a high-level model focusing on what is the result generated by the policy, but not how the results are obtained, we will not further discuss details of its polynomialtime implementation in ROS.

Algorithm 1 shows the pseudo-code for the Approximate-Time policy to select and publish the output message set when a new message arrives. Suppose at the current moment Q i originally has k messages {m 1 i , ..., m k i }, where m k i is a predicted message (recall that the last message in a queue must be a predicted message). The algorithm first updates Q i with the newly arrived message m i (Line 1 to 3), by discarding the original predicted message m k i , putting the newly arrived message to the end of Q i as m k i , and finally generating a new predicted message

Next, the algorithm repeatedly checks whether each queue currently contains at least one arrived message or not. If not, i.e., some queue only has a predicted message, it is impossible to publish an output message set anyway, so the algorithm simply stops without any further checking. If yes, it first sets the current pivot according to Definition 2 (Line 5). Then it checks whether all predicted messages' timestamps are no earlier than t(m P ) (Line 6). If not, the algorithm returns without publishing any output message set (Line 15), the intuition behind which is explained as follows. If a predicted message m k in some queue Q k has t(m k ) < t(m P ), then the timestamps of the arrived messages (if any) in this queue are even smaller, so this predicted message has the closest timestamp to the pivot m P . Therefore, the next message to arrive in this queue has a chance to make a better output message set than the existing arrived messages in Q k , so it makes sense to wait until the next message of Q k arrives (and its actual timestamp is revealed) to make the decision 1 . If all predicted messages' timestamps are no earlier than t(m P ), the algorithm will find the selected set S according to Definition 3 (Line 7), and checks whether all messages in S are arrived messages (Line 8). If not, i.e., S contains at least one predicted message, S cannot be published and the algorithm stops (Line 13). If yes, S is published as an output message set (Line 9). After that, for each queue Q j , the corresponding message m j in S and all messages in Q j before m j are discarded.

From Algorithm 1, we can see that under the Approximate-Time policy, the output message sets are decided based on the messages' timestamps, but not their arrival times. The arrival Lemma 7. Let S PUB = {m 1 , ..., m N } be an output message set published at time t. The required size of

Proof. If a message is in Q i at time t, its timestamp is no later than t -D B i . On the other hand, the timestamp of m i is no earlier than a(m 1 i ) -D W i . Therefore, the total length of the time interval to generate messages that are after m 1 i and have arrived at

Lemma 8. Let S PUB = {m 1 , ..., m N } be an output message set published at time t and m P ∈ S PUB is the pivot. Then for each m i ∈ S PUB and m 1 i is the corresponding earliest message in Q i , we have

where ∆ denotes the RHS of (12).

Proof. By Theorem 1, for each m j ∈ S PUB , we know

On the other hand, we also have

Since m P ∈ S PUB , the lemma is proved.

Lemma 9. Let S PUB = {m 1 , ..., m N } be an output message set published at time t and m P is the pivot in S PUB , then

Proof. Let t ′ denote the earliest time point at which each nonpivot contains at least one arrived message with timestamp larger than t(m P ). By the definition of t ′ , some message arrives at t ′ and thus Algorithm 1 is executed at t ′ . We will first prove S PUB is published no later than t ′ . We prove this by contradiction, assuming S PUB is published after t ′ . By the definition of t ′ , the while-condition in Line 4 and the if-condition in Line 6 in Algorithm 1 are both true, so the selected set at t ′ must not be S PUB (otherwise S PUB is published at t ′ ). Let S be the selected set at t ′ . First, S does not contain any predicted message, since for each Q i there exists an arrived message with timestamp later than t(m P ) (so the predicted message is "further away" from the m P than this arrived message). Therefore, the selected set S must be published, so the pivot m P must not be in S (since the same message cannot be included in two published output message sets). Therefore, for the queue of m P , S includes a message after m P . After S is published, all messages before the published message in S are discarded, and in particular, m P is discarded, which contradicts that m P is in S PUB which is published after t ′ . Therefore, our assumption is false, so S PUB is published no later than t ′ , i.e., t ≤ t ′ . We assume message m ′ i of Q i arrived at t ′ and triggers the execution of Algorithm 1, so m ′ i is the first message in

, and since t ≤ t ′ , the lemma is proved. Theorem 2. The required size of Q i for any published output message set is upper bounded by

where ∆ denotes the RHS of (12).

Proof. The theorem is proved by combining Lemma 7, Lemma 9 and Lemma 8.

We conduct experiments to both validate our high-level model of the ApproximateTime policy and evaluate the analysis precision of the time disparity bound in Theorem 1. The source codes of all experiments are anonymously available online at https:// github.com/ ruoxianglee/ synchronizer.

We implement Algorithm 1 (called our implementation) in the Message Filter package of ROS2 (the Dashing version) and let it run in parallel with the original implementation of the Ap-proximateTime policy in ROS2. We implement Algorithm 1 in a straightforward way, without any performance optimization, to reduce the chance of introducing implementation errors. When a new message arrives at the Message Synchronizer, our implementation and the original implementation will update their own queues, select and publish the output message set independently. We compare all the output message sets published in the two implementations to see if they are the same. We run the experiments on an Intel i7 desktop computer with ROS2 Dashing installed on Ubuntu 18.04, using artificial input messages generated using timers with different settings, including different number of input channels (from 2 to 9, as currently the ROS Message Filter supports up to 9 input channels), different timestamp separation of each channel (T B i chosen between 10ms and 100ms, and the ratio between T B i and T W i chosen between 1 and 1.8). For the experiments in each setting, the delay experienced by the messages randomly varies between 1ms and 40ms. We in total conduct experiments with 700 different settings, and run the system for 0.5 hours in each setting. In all these experiments, the output message sets produced by our implementation and the original implementation are exactly the same. Besides artificial input messages, we also conduct experiments with sensor data inputs generated by the SVL simulator [13] (including camera, LiDAR and IMU sensors in SVL, with different frequency settings), where the outputs of the two implementations are also the same. These experiments justify the correctness of our model with high confidence. software development, [21] proposes a multipurpose lowoverhead framework for tracing ROS application. Some work aimed to improve the real-time capability of ROS from the system architecture perspective. [22] presented a real-time ROS architecture for separately executing real-time and non-real-time tasks on a integrated OS environment with multi-core processors. [23] proposed an offline scheduling framework for ROS considering both ROS scheduling restrictions and CPU/GPU coordination mechanism. [24] presented a priority-based message transmission mechanism to reduce the worst-case execution time for node processing and inserting a sync node to harmonize the frequencies of different sensor data to improve the time disparity. In [25], a fixed-priority based DAG scheduling framework was proposed with endto-end latency guarantees. The authors also introduced a synchronization mechanism to reduce the time disparity, but their work is based on measurement for the specific case but does not provide any formal analysis.

Some recent work has been done on formal real-time performance analysis of ROS2. [26], [27] modeled the singlethread Executor in ROS2 and studied response time analysis of processing chains executing on it. [28] redesigns the ROS2 executor with a fixed priority assignment policy to overcome the limitations of the default scheduling strategy of ROS2, and analyze the end-to-end latency based on the proposed scheduling policy. [29] proposes an automatic latency manager and apply existing real-time scheduling theory to latency control of the critical callback chains in ROS2 applications, which adaptively estimates and adjusts the scheduling parameters without the user's involvement. In [30], the authors take both the starvation freedom and execution-time variance of the default ROS2 scheduler into consideration, and propose a more accurate response time analysis for processing chains. [31] presents two new executors based on the thread dispatch model and producer-consumer model and developed corresponding response time analysis techniques. The above work all focus on the executor component in ROS, while in this paper we consider another important component: the Message Synchronizer.

Past work on real-time scheduling and analysis studied different real-time performance metrics, such as response time [32], [33], tardiness [34] and data freshness [35]. However, existing analysis and design techniques developed oriented to these constraints do not apply to the analysis of time disparity studied in this paper.

In this paper, we model the ApproximateTime message synchronization policy in ROS and formally analyze the worst-case time disparity of their output message sets. We conduct experiments to evaluate the precision of the developed time disparity upper bound against the maximal observed time disparity in real execution, and compare them with the synchronization policy in Apollo CyberRT. Experiment results show that our analysis has good precision and the synchronization policy in ROS greatly outperforms Apollo CyberRT in terms of both observed worst-case time disparity and the theoretical bound. This is the first step towards the analytical study of the data synchronization in multi-sensor data fusion regarding the worst-case time disparity metrics, and many problems along this direction are still open. For example, the required queue size bound derived in this paper is only to show that our time disparity analysis is applicable without assuming infinite queue sizes, but it is unclear whether we could develop tighter bound than that, which will be a topic for our future work. We will also study how to improve the design and implementation of the ROS Message Synchronizer for average-case time disparity performance while maintaining the same (or even better) worst-case time disparity bound. For an arbitrary slave queue Q i (2 ≤ i ≤ N ), let m ′ i be the next message after m i . We have

Combing ( 14)-( 17), we have

• If t(m 1 ) > t(m i ), by (18), we have

• If t(m 1 ) ≤ t(m i ), by (18), we have

The theorem can be proved by combining these two cases.