Relay-Based Synchronization of Replicated Data Types in Opportunistic Networks
Frédéric Guidec, Yves Mahéo · 2026
Read Relay-Based Synchronization of Replicated Data Types in Opportunistic Networks by Frédéric Guidec, Yves Mahéo (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-22491.txt.
Introduction
Guidec and Mahéo investigate relay-based synchronisation of conflict-free replicated data types (CRDTs) in opportunistic networks. In such networks, information spreads only through fleeting pairwise radio contacts between mobile peers. CRDT replicas update locally yet converge through background synchronisation. Whether replicas converge, and how fast, depends on radio contact patterns. Mobile relays are proposed as a boost, with new protocols and metrics for convergence. Simulations show relays improve convergence, even enabling it where replicas alone could not converge.
Catalog record
| CREATOR | Frédéric Guidec, Yves Mahéo |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 110143 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.22491
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Relay-Based Synchronization of Replicated Data Types in Opportunistic Networks Frédéric Guidec, Yves Mahéo Abstract In Opportunistic Networks (OppNets), the dissemination of information can only rely on transient pairwise radio contacts between mobile devices (peers). Designing distributed applications that can run in such conditions is a challenge, but replicated data types, and in particular Conflict-free Replicated Data Types (CRDTs), can help meet this challenge. A CRDT is inherently a replicated data type whose replicas can be updated locally, yet eventually converge thanks to an anti-entropy algorithm that allows all replicas to synchronize in the background. Whether the replicas of a CRDT can actually converge in an OppNet, and how fast they can converge, depend on the occurrence of radio contacts between mobile devices. In this paper we investigate the idea of using mobile relays as a means to boost the convergence of stated-based CRDT replicas in an OppNet. New protocols are presented that allow the synchronization of replicas and relays, and new metrics are defined to observe and characterize the convergence of replicas. Simulation results show that using relays can significantly improve this convergence, and even make it possible in scenarios where the replicas alone would be unable to converge. Keywords: Opportunistic networking, Peer-to-Peer networks, Ad hoc networks, Conflict-free replicated data types, Optimistic replication, Strong eventual consistency 1 Introduction 1.1 Opportunistic networking An opportunistic network (OppNet) is a category of peer-to-peer network in which the peers are mobile devices that can only interact pairwise via direct radio transmission links. Such networks can typically be used when no communication infrastructure is available (e.g., in disaster relief scenarios, or in V2V communication), or as a means to complement an existing infrastructure. Since an OppNet is often sparsely populated, and since the radio links between neighbor devices (or peers) are often short ranged, there is usually very little connectivity between the devices. An OppNet, if modelled as a graph, appears as a highly partitioned time-varying graph rather than as a connected static graph (see Figure 1 ). A consequence of the high level of partitioning in such a network is that routing algorithms such as those used in the Internet, or even in MANETs, are useless in OppNets. While permanent or quasi-permanent end-to-end connectivity between any pair of hosts is taken for granted in the Internet, it is simply unavailable in OppNets. For this reason, maintaining an overlay among peers is not an option. Each mobile device in an OppNet can only seize the opportunity to interact transiently with another mobile device (or peer) when a radio contact is established between them. Figure 1: Illustration of the evolution of an opportunistic network The very nature of OppNets requires that applications be fully distributed rather than based on the client-server architecture. Yet the development of distributed applications capable of running in OppNets, relying solely on transient radio contacts between neighbor nodes, is quite a challenge. 1.2 Conflict-free Replicated Data Types Conflict-free Replicated Data Types (CRDTs) can significantly help in the development of distributed applications in OppNets because of their ability to provide Strong Eventual Consistency (SEC) for replicated data types [ 2 , 24 ] . They can typically be used to implement distributed databases, as well as collaborative editing applications. A CRDT is basically a data type that can be replicated on many hosts. An update operation can be issued locally on any replica at any time, regardless of what may be happening on other replicas at the same time. A synchronization protocol (also called anti-entropy algorithm) runs in the background to ensure that each update is eventually delivered to —and applied by— every replica (eventual visibility/delivery), and replicas that have applied the same updates have equivalent states (strong convergence). With this consistency model, replicas keep converging as long as new updates are issued. If no new update is issued for long enough the replicas eventually reach equivalent states. CRDTs come in two main flavors: op-based CRDTs (i.e., operation-based CRDT, sometimes called commutative replicated data types), and state-based CRDTs (also known as convergent replicated data types). It has been demonstrated that op-based CRDTs can hardly be used in OppNets [ 12 ] , because their synchronization model yields too much traffic in the network. In contrast, state-based CRDTs are perfectly suited to be used in OppNets, as discussed below. In a state-based CRDT, the set of all possible states constitute a join semi-lattice. A join operator is implemented in a merge function, which takes two states as parameters and returns the least upper bound of both states. Replicas can therefore synchronize periodically (usually pairwise in a peer-to-peer manner) by exchanging their entire states, each receiver merging the received state with its own local state, so the two replicas involved end up with the same state. Causal consistency is ensured implicitly, since successive synchronizations between pairs of replicas ensure a transitive propagation of the causal past [ 2 ] . An illustration of how replicas can periodically synchronize pairwise is provided in Figure 2 . In this example we consider two replicas of a Map CRDT. To keep it simple, we assume that the values are of simple types (integer, float, string…). This map is initially empty on both replicas. An entry with key k_{1} and value v is first added locally to the map in replica R1, while an entry (k_{2},w) is added locally in replica R2. The state is thus temporarily different in R1 and R2, but as a synchronization occurs between them, R1 merges its local state with the state received from R2, and R2 likewise merges its own state with that received from R1. After this synchronisation, both replicas agree that the state of the map is now \left\{(k_{1},v),(k_{2},w)\right\} . Note that reconciling state \left\{(k_{1},v)\right\} (from R1) with state \left\{(k_{2},w)\right\} (from R2) is not an issue, because these are not conflicting states: although set(k 1 , v) and set(k 2 , w) occurred concurrently in R1 and R2, they apply to different entries (i.e., entries with different keys) in the shared map. Figure 2: Example of a run involving a Map CRDT (with set-wins semantics) replicated in two replicas R1 and R2 After the first synchronization, the value of entry k_{1} is first changed to x in R1, and this entry is then deleted in R1, while an entry with the same key k_{1} and value y is set in R2. The state is thus different again in R1 and R2, and this time the last del(k 1 ) on R1 conflicts with set(k 1 , y) on R2, as they occurred concurrently and both apply to entry k_{1} . If both replicas synchronize again, the final state depends on the concurrency semantics implemented in the merge function of the Map CRDT. If this function implements the set-wins semantics, giving set(k 1 , x) priority over del(k 1 ) , the final state is \left\{(k_{1},y),(k_{2},w)\right\} in both replicas, as shown in Fig. 2 . But the merge function could also implement the del-wins semantics, giving del(k 1 ) priority over set(k 1 , x) , in which case the final state on both replicas would be \left\{(k_{2},w)\right\} . Both concurrency semantics are thus perfectly viable, as they allow the replicas to