In the near future, self-driving cars will transition from isolated autonomous units to social, collaborative entities. Whether navigating a disaster zone in a convoy or coordinating a group road trip, vehicles will need to share and adjust routes in real-time. However, maintaining a synchronized shared map across multiple moving nodes is a significant technical challenge. High speeds, massive data generation, and the inherent latency of mobile networks make traditional "locking" mechanisms—where one user waits for another to finish an edit—completely impractical for safety-critical driving scenarios.
In their research, Te Jiang, Tun Lu, and Ning Gu from Fudan University propose Themis, a high-performance synchronization system designed specifically for the edge computing era. Themis enables self-driving cars to share and edit routes with sub-50ms latency, ensuring consistency without the wait.
The Challenge: Consistency vs. Responsiveness
Collaborative mobile environments face a classic trade-off between consistency and responsiveness. Standard approaches often rely on locks to ensure that everyone eventually sees the same data. However, if a vehicle loses connection (e.g., while driving through a tunnel) while holding a lock, the entire system can stall.
Furthermore, human perception begins to notice lag at approximately 150ms. In high-speed autonomous driving, where positions change every millisecond, traditional cloud-based syncing is too slow and consumes excessive bandwidth. Themis addresses this by maintaining a "single source of truth" across fast-moving nodes without requiring them to wait for network permissions.
The Themis Architecture
The researchers built Themis on three core pillars designed to optimize performance in edge environments:
1. Address Space Transformation (AST)
At the heart of Themis is the AST algorithm, a lock-free approach to data editing. Instead of waiting for permission, a vehicle performs edits locally and immediately. If a conflict arises—such as two cars attempting to modify the same waypoint simultaneously—the system uses timestamps and a predefined "T-Order" to resolve the conflict mathematically across all sites. This ensures all vehicles eventually arrive at the same final state without blocking operations.
2. Partial Replication
To minimize network traffic, Themis employs a partial replication strategy. Rather than syncing the entire global map, the system divides the map into discrete blocks. Vehicles only synchronize data for the specific "active blocks" they are currently occupying.
3. Snapshots and Compression
Themis optimizes data transmission through two key techniques:
- Snapshots: By identifying the "covering effect"—where the last operation on a point often renders previous edits irrelevant—Themis sends a "snapshot" of the final state rather than a full operation history.
- Compression: For continuous movements like GPS trails, the system groups operations under a single timestamp to reduce data header overhead.
Edge-Cloud Synergy
Themis utilizes a hybrid architecture that splits labor between the edge and the cloud. The Edge handles high-frequency, low-latency local syncs for immediate responsiveness. Meanwhile, the Cloud maintains a "Virtual History Buffer" (VHB) to help new vehicles joining an area catch up on the history they missed.
Experimental Evaluation
The system was evaluated using a simulation environment integrated with Baidu Map APIs, featuring 11 concurrent sites generating operations. The results demonstrate that Themis is highly optimized for real-world mobile networks:
- Latency: Remote operation execution time remained consistently between 20ms and 35ms, well below the 150ms human perception threshold.
- Bandwidth Efficiency: Partial replication showed a linear reduction in data transmission. At a 10% replication ratio, the data load was nearly 10x smaller than a fully replicated system.
- Compression & Snapshots: The compression strategy achieved a 25% reduction in data size for long operation sequences, while snapshots reduced execution time by up to 85% in high-edit scenarios.
Conclusion and Future Work
Themis demonstrates that lock-free, AST-based synchronization is a viable path forward for collaborative autonomous driving. By prioritizing responsiveness and reducing bandwidth through partial replication, it ensures that a single vehicle's poor connection does not compromise the coordination of an entire fleet. Future work will focus on managing local storage growth and integrating Themis into actual autonomous driving stacks to handle higher-frequency machine-generated data.
Summary updated