Themis: An AST-Based Lock-Free Routes Synchronizing and Sharing System for Self-Driving in Edge Computing Environments

Te Jiang, Tun Lu, Ning Gu

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.

The partial replication strategy divides the map into areas, ensuring vehicles only sync data relevant to their current location.

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.

Themis system architecture illustrating the interaction between the user interface, the network, and the cloud-side synchronization services.

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

Abstract

The rapid development of self-driving technology has made self-driving cars come into reality, and some people have already adopted different levels of self-driving technology in real driving practices. With the help of self-driving technology, nowadays people can share and schedule their routes together while driving. However, currently, there are poor supports for such activities, as it demands highly responsiveness, strong consistency guarantees, and low transmission costs. As to support the novel scenario, we developed an edge computing oriented and highly efficient AST-Based lock-free synchronizing and sharing system called Themis on a fundamental itinerary planning model. We optimized the system by adopting partial replication, snapshots of history operations, and compression on consecutive operations strategies, which leave certain calculations at the cloud side, and reduce the amount and size of transmission data in the network. Besides, we have analyzed and proved the correctness of our scheme in detail; examining the significant improvements in performances through experiments.
BibTeX
@article{jiang2019themis,
  author = {Te Jiang and Tun Lu and Ning Gu},
  title = {{Themis: An AST-Based Lock-Free Routes Synchronizing and Sharing System for Self-Driving in Edge Computing Environments}},
  journal = {IEEE Access},
  year = {2019},
  doi = {10.1109/access.2019.2948021},
}
Figure