pith. sign in

arxiv: 2605.22491 · v1 · pith:EUTXTSZ7new · submitted 2026-05-21 · 💻 cs.DC · cs.NI

Relay-Based Synchronization of Replicated Data Types in Opportunistic Networks

Fr\'ed\'eric Guidec , Yves Mah\'eo This is my paper

Pith reviewed 2026-05-22 03:59 UTC · model grok-4.3

classification 💻 cs.DC cs.NI
keywords opportunistic networksCRDTreplicated data typesdata synchronizationmobile relaysanti-entropyconvergencetransient contacts
0
0 comments X

The pith

Mobile relays can make replicated data types converge in opportunistic networks even when replicas rarely meet directly.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

In opportunistic networks, devices connect only through brief and unpredictable radio contacts, which makes keeping replicated data consistent a challenge. The paper examines state-based conflict-free replicated data types that rely on background anti-entropy exchanges to reach eventual consistency. It introduces protocols that let mobile relays participate in these exchanges by carrying updates between replicas. Simulations show that relays increase the speed of convergence and enable it in contact patterns where replicas by themselves never synchronize.

Core claim

The paper claims that new protocols allowing mobile relays to carry and exchange state updates for state-based CRDT replicas can markedly raise convergence rates in opportunistic networks and can produce convergence in contact scenarios where replica-to-replica meetings alone are too infrequent or mistimed to succeed.

What carries the argument

Relay-assisted anti-entropy protocols that extend synchronization so relays ferry CRDT state between replicas during transient contacts.

If this is right

  • Replicas reach consistency faster once relays assist with message delivery.
  • Convergence occurs in networks whose replica contact graph is otherwise too sparse.
  • New metrics quantify how relay participation changes the pace and reliability of consistency.
  • Synchronization traffic now flows through both replica and relay nodes, expanding effective connectivity.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Applications built on CRDTs could run on moving sensor or phone swarms without fixed base stations.
  • Real deployments would need to address relay energy costs or participation incentives.
  • The same relay-carrying idea could be tested on other eventually consistent replication schemes.
  • Validation against actual human or vehicle mobility traces would show whether simulation gains survive outside synthetic models.

Load-bearing premise

Mobile relays are present and will actively carry and forward synchronization messages whenever they contact replicas.

What would settle it

Simulations or field tests that add relays yet show no reduction in time to convergence or no success in previously impossible scenarios would falsify the claimed benefit.

Figures

Figures reproduced from arXiv: 2605.22491 by Fr\'ed\'eric Guidec, Yves Mah\'eo.

Figure 1
Figure 1. Figure 1: Illustration of the evolution of an opportunistic network [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Example of a run involving a Map CRDT (with set-wins semantics) replicated in two replicas R1 and R2 [PITH_FULL_IMAGE:figures/full_fig_p002_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Definitions of the basic functions expected from any CRDT library [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Example of synchronization between two replicas [PITH_FULL_IMAGE:figures/full_fig_p007_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Example of synchronization between a replica and a relay [PITH_FULL_IMAGE:figures/full_fig_p009_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Example of synchronization between two relays [PITH_FULL_IMAGE:figures/full_fig_p010_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Illustration of the selection of states to be transferred by a relay to a peer [PITH_FULL_IMAGE:figures/full_fig_p013_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Snapshot of the Östermalm scenario (with replica nodes in red and relay nodes in blue) [PITH_FULL_IMAGE:figures/full_fig_p016_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Evolution of the convergence latency (left) and distance to the global state (right) when running the Östermalm scenario [PITH_FULL_IMAGE:figures/full_fig_p019_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Evolution of the average latency and distance over time against the ratio of relays (left), and evolution of the number of [PITH_FULL_IMAGE:figures/full_fig_p020_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: Snapshot of the VBN scenario, with mobile relay nodes (buses) in blue and static replica nodes in red [PITH_FULL_IMAGE:figures/full_fig_p021_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: Evolution of the convergence latency (left) and distance to the global state (right) when running the VBN scenario with [PITH_FULL_IMAGE:figures/full_fig_p023_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: Evolution of the average latency and distance over time against the ratio of relays (left), and evolution of the number of [PITH_FULL_IMAGE:figures/full_fig_p023_13.png] view at source ↗
Figure 14
Figure 14. Figure 14: Snapshot of the Disaster Relief scenario, with replica nodes (rescue workers) in red and relay nodes (drones) in blue [PITH_FULL_IMAGE:figures/full_fig_p026_14.png] view at source ↗
Figure 15
Figure 15. Figure 15: Evolution of the convergence latency (left) and distance to the global state (right) when running the Disaster relief [PITH_FULL_IMAGE:figures/full_fig_p027_15.png] view at source ↗
Figure 16
Figure 16. Figure 16: Evolution of the average latency and distance over time against the ratio of relays (left), and evolution of the number of [PITH_FULL_IMAGE:figures/full_fig_p028_16.png] view at source ↗
read the original 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 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper investigates using mobile relays to boost convergence of state-based CRDT replicas in opportunistic networks. It introduces new synchronization protocols for replicas and relays, defines new metrics to observe convergence, and presents simulation results claiming that relays can significantly improve convergence and enable it in scenarios where direct replica contacts alone are insufficient.

Significance. If the simulation results hold under realistic conditions, the work offers a practical extension of CRDTs to more dynamic and partitioned networks, with the new protocols and convergence metrics providing reusable contributions for distributed systems in challenged environments. The simulation-based demonstration of newly possible convergence is a notable strength if the mobility and participation models are adequately justified.

major comments (2)
  1. [Simulation results] Simulation results section: the central claim that relays enable convergence where replicas alone cannot rests on the modeling choice that relays always merge and forward complete states during transient contacts with unlimited buffers and full participation; this is load-bearing and requires either explicit justification or additional experiments relaxing these assumptions (e.g., partial participation or storage limits) to confirm robustness.
  2. [Abstract and evaluation] Abstract and evaluation: quantitative claims of 'significant improvement' and 'newly possible convergence' lack reported details on mobility models, number of runs, error bars, exact convergence metrics, and parameter settings, preventing verification of the evidence strength for the reported gains.
minor comments (2)
  1. [Metrics section] The formal definitions of the new convergence metrics would benefit from explicit equations or pseudocode to improve reproducibility and clarity.
  2. [Introduction] A few sentences in the introduction could more precisely distinguish the proposed relay protocols from prior anti-entropy mechanisms in OppNets.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thorough review and the constructive feedback on our manuscript. We believe the suggested revisions will strengthen the presentation of our results. Below, we provide point-by-point responses to the major comments.

read point-by-point responses

  1. Referee: Simulation results section: the central claim that relays enable convergence where replicas alone cannot rests on the modeling choice that relays always merge and forward complete states during transient contacts with unlimited buffers and full participation; this is load-bearing and requires either explicit justification or additional experiments relaxing these assumptions (e.g., partial participation or storage limits) to confirm robustness.

    Authors: The simulation model does assume that relays perform complete merges and forward full states upon contact, with no buffer limits and full participation, as described in Section 4 of the manuscript. This choice was made to isolate the effect of relay-assisted synchronization in an initial study. We will revise the manuscript to include explicit justification for these assumptions, referencing prior work on relay nodes in delay-tolerant networks that often assume similar ideal forwarding behaviors for baseline analysis. Furthermore, we will conduct and report additional simulation experiments with relaxed assumptions, such as 50% participation rate and buffer sizes limited to 10% of state size, to demonstrate the robustness of the observed benefits. These new results will be added to the evaluation section. revision: yes

  2. Referee: Abstract and evaluation: quantitative claims of 'significant improvement' and 'newly possible convergence' lack reported details on mobility models, number of runs, error bars, exact convergence metrics, and parameter settings, preventing verification of the evidence strength for the reported gains.

    Authors: We agree that additional details are necessary for reproducibility and to substantiate the quantitative claims. In the revised version, we will update the abstract to briefly mention the mobility model (Random Waypoint with specific speed and area parameters), the number of independent runs (50), and the use of error bars representing standard deviation. We will also expand the evaluation section with a table or subsection listing all key parameter settings, the precise definition of the convergence metrics (e.g., time to 90% replica consistency), and statistical analysis from the multiple runs. This will allow readers to better assess the strength of the evidence. revision: yes

Circularity Check

0 steps flagged

No circularity: simulation results from new protocols are independent of inputs

full rationale

The paper defines new synchronization protocols for CRDT replicas and relays in opportunistic networks, then evaluates convergence via simulations under explicit mobility and contact models. No equations, fitted parameters, or derivations are presented that reduce by construction to the inputs; the reported improvements in convergence (including scenarios where replicas alone fail) are empirical outcomes of the simulations rather than tautological restatements. Self-citations, if present, are not load-bearing for the central claims, and the work remains self-contained against external benchmarks such as direct replica-only runs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on standard domain assumptions about opportunistic network contacts and CRDT anti-entropy properties rather than new invented entities or many fitted parameters.

axioms (1)
  • domain assumption Replicas of a CRDT can eventually converge via background anti-entropy when radio contacts occur.
    Invoked in the abstract when discussing dependence of convergence on radio contacts.

pith-pipeline@v0.9.0 · 5724 in / 1080 out tokens · 35161 ms · 2026-05-22T03:59:00.936158+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

26 extracted references · 26 canonical work pages · 2 internal anchors

  1. [1]

    Approaches to Conflict-free Replicated Data Types.ACM Computing Surveys, 57(1):1–36, September 2024.doi:10.1145/3695249

    Paulo Sérgio Almeida. Approaches to Conflict-free Replicated Data Types.ACM Computing Surveys, 57(1):1–36, September 2024.doi:10.1145/3695249

    work page doi:10.1145/3695249 2024

  2. [2]

    Scalable Eventually Consistent Counters over Unreliable Networks

    Paulo Sérgio Almeida and Carlos Baquero. Scalable Eventually Consistent Counters over Unreliable Networks. arXiv 1307.3207, July 2013.doi:10.48550/arXiv.1307.3207

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.1307.3207 2013

  3. [3]

    Evaluating Data Convergence of Collaborative Editors in Opportunistic Networks

    Noha Alsulami, Asma Cherif, and Abdessamad Imine. Evaluating Data Convergence of Collaborative Editors in Opportunistic Networks. In6th International Conference on Information and Communication Technology and Accessibility (ICTA), Muscat, Oman, December 2017. IEEE.doi:10.1109/ICTA.2017.8336061

    work page doi:10.1109/icta.2017.8336061 2017

  4. [4]

    A Survey on Opportunistic Routing in Wireless Communication Networks.IEEE Communications Surveys & Tutorials, 17(4):2214–2241, 2015.doi:10.1109/COMST.2015.2411335

    Nessrine Chakchouk. A Survey on Opportunistic Routing in Wireless Communication Networks.IEEE Communications Surveys & Tutorials, 17(4):2214–2241, 2015.doi:10.1109/COMST.2015.2411335

    work page doi:10.1109/comst.2015.2411335 2015

  5. [5]

    Mavromoustakis

    Radu-Ioan Ciobanu, Radu-Corneliu Marin, Ciprian Dobre, Valentin Cristea, and Constandinos X. Mavromoustakis. ONSIDE: Socially-aware and Interest-based Dissemination in Opportunistic Networks. InIEEE Network Operations and Management Symposium (NOMS), Krakow, Poland, May 2014. IEEE.doi:10.1109/NOMS.2014.6838390

    work page doi:10.1109/noms.2014.6838390 2014

  6. [6]

    Mavromoustakis, and George Mastorakis.Causal and Total Order in Opportunistic Networks, chapter Emerging Innovations in Wireless Networks and Broadband Technologies, pages 221–262

    Mihail Costea, Radu-Ioan Ciobanu, Radu-Corneliu Marin, Ciprian Dobre, Constandinos X. Mavromoustakis, and George Mastorakis.Causal and Total Order in Opportunistic Networks, chapter Emerging Innovations in Wireless Networks and Broadband Technologies, pages 221–262. IGI Global, 2016.doi:10.4018/978-1-4666-9941-0.ch010

    work page doi:10.4018/978-1-4666-9941-0.ch010 2016

  7. [7]

    Mavromoustakis, George Mastorakis, and Fatos Xhafa

    Mihail Costea, Radu-Ioan Ciobanu, Radu-Corneliu Marin, Ciprian Dobre, Constandinos X. Mavromoustakis, George Mastorakis, and Fatos Xhafa. Total Order in Opportunistic Networks.Concurrency and Computation: Practice and Experience, 29(10), 2017.doi:10.1002/cpe.4056

    work page doi:10.1002/cpe.4056 2017

  8. [8]

    Proliferation of Opportunistic Routing: A Systematic Review.IEEE Access, 10:5855–5883, 2022.doi:10.1109/ACCESS.2021.3136927

    Renu Dalal, Manju Khari, John Petearson Anzola, and Vicente García-Díaz. Proliferation of Opportunistic Routing: A Systematic Review.IEEE Access, 10:5855–5883, 2022.doi:10.1109/ACCESS.2021.3136927

    work page doi:10.1109/access.2021.3136927 2022

  9. [9]

    A Delay-Tolerant Network Architecture for Challenged Internets

    Kevin Fall. A Delay-Tolerant Network Architecture for Challenged Internets. InACM Annual Conference of the Special Interest Group on Data Communication (SIGCOMM 2003), pages 27–34, Karlsruhe, Germany, August 2003.doi:10. 1145/863955.863960

    work page arXiv 2003

  10. [10]

    Crawdad ubs/vbn

    Frédéric Guidec, Pascale Launay, and Yves Mahéo. Crawdad ubs/vbn. IEEE Dataport, 2022.doi:10.15783/qr0f-m304. 9https://www-inzu.irisa.fr/demo-oppnet 30

    work page doi:10.15783/qr0f-m304 2022

  11. [11]

    CRDT-based Collaborative Editing in OppNets: a Practical Experiment

    Frédéric Guidec, Yves Mahéo, and Camille Noûs. CRDT-based Collaborative Editing in OppNets: a Practical Experiment. In17th Conference on Mobile Ubiquitous Computing, Systems, Services and Technologies (Ubicomm 2023), pages 13–21, Porto, Portugal, September 2023. IARIA

    work page 2023

  12. [12]

    Supporting conflict-free replicated data types in opportunistic networks

    Frédéric Guidec, Yves Mahéo, and Camille Noûs. Supporting conflict-free replicated data types in opportunistic networks. Peer-to-Peer Networking and Applications, 16:395–419, January 2023.doi:10.1007/s12083-022-01404-6

    work page doi:10.1007/s12083-022-01404-6 2023

  13. [13]

    Dorit S. Hochbaum.Approximation Algorithms for NP-Hard Problems, chapter 3, Approximating Covering and Packing Problems: Set Cover, Vertex Cover, Independent Set And Related Problems, pages 94–143. PWS Publishing Company, 1996

    work page 1996

  14. [14]

    Coordination Model for Real-Time Collaborative Editors

    Abdessamad Imine. Coordination Model for Real-Time Collaborative Editors. InCoordination Models and Language (COORDINATION 2009), volume 5521 ofLNCS, pages 225–246, Lisbon, Portugal, June 2009. Springer.doi:10.1007/ 978-3-642-02053-7_12

    work page 2009

  15. [15]

    On CRDTs in Byzantine Environments

    Florian Jacob, Saskia Bayreuther, and Hannes Hartenstein. On CRDTs in Byzantine Environments. InSicherheit 2022, pages 113–122, Karlsruhe, Germany, April 2022. Gesellschaft für Informatik.doi:10.18420/sicherheit2022_07

    work page doi:10.18420/sicherheit2022_07 2022

  16. [16]

    Shared Content Editing in Opportunistic Networks

    Teemu Kärkkäinen and Jörg Ott. Shared Content Editing in Opportunistic Networks. In9th ACM MobiCom Workshop on Challenged Networks (CHANTS’14), pages 61–64. ACM, 2014.doi:10.1145/2645672.2645685

    work page doi:10.1145/2645672.2645685 2014

  17. [17]

    Crawdad kth/walkers

    Sylvia Todorova Kouyoumdjieva, Ólafur Ragnar Helgason, and Gunnar Karlsson. Crawdad kth/walkers. IEEE Dataport, 2022.doi:10.15783/C7Z30C

    work page doi:10.15783/c7z30c 2022

  18. [18]

    Probabilistic Routing in Intermittently Connected Networks

    Anders Lindgren, Avri Doria, and Olov Schelen. Probabilistic Routing in Intermittently Connected Networks. In1st International Workshop on Service Assurance with Partial and Intermittent Resources (SAPIR 2004), volume 3126 ofLNCS, pages 239–254, Fortaleza, Brazil, August 2004. Springer.doi:10.1007/978-3-540-27767-5_24

    work page doi:10.1007/978-3-540-27767-5_24 2004

  19. [19]

    Modeling Opportunistic Communication with Churn.Computer Communications, 96:123–135, 2016.doi:10.1016/j.comcom.2016.04.018

    Ljubica Pajevic and Gunnar Karlsson. Modeling Opportunistic Communication with Churn.Computer Communications, 96:123–135, 2016.doi:10.1016/j.comcom.2016.04.018

    work page doi:10.1016/j.comcom.2016.04.018 2016

  20. [20]

    Conflict-free Replicated Data Types: An Overview

    Nuno Preguiça. Conflict-free Replicated Data Types: an Overview. arXiv 1806.10254, June 2018.doi:10.48550/arXiv. 1806.10254

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv 2018

  21. [21]

    On the Levy-walk Nature of Human Mobility.IEEE/ACM Transactions on Networking, 19(3):630–643, June 2011.doi:10.1109/TNET.2011.2120618

    Injong Rhee, Minsu Shin, Seongik Hong, Kyunghan Lee, Seong Joon Kim, and Song Chong. On the Levy-walk Nature of Human Mobility.IEEE/ACM Transactions on Networking, 19(3):630–643, June 2011.doi:10.1109/TNET.2011.2120618

    work page doi:10.1109/tnet.2011.2120618 2011

  22. [22]

    Robin and Victor M

    Charles Edward A. Robin and Victor M. Romero. DTNDocs: A delay tolerant peer-to-peer collaborative editing system. In32nd International Conference on Information Networking (ICOIN), pages 92–97, Chiang Mai, Thailand, January 2018. doi:10.1109/ICOIN.2018.8343092

    work page doi:10.1109/icoin.2018.8343092 2018

  23. [23]

    IBR-DTN: A lightweight, modular and highly portable Bundle Protocol implementation.Electronic Communications of the EASST, 37:1–11, January 2011

    Sebastian Schildt, Johannes Morgenroth, Wolf-Bastian Pöttner, and Lars Wolf. IBR-DTN: A lightweight, modular and highly portable Bundle Protocol implementation.Electronic Communications of the EASST, 37:1–11, January 2011

    work page 2011

  24. [24]

    A Comprehensive Study of Convergent and Commutative Replicated Data Types

    Marc Shapiro, Nuno Preguiça, Carlos Baquero, and Marek Zawirski. A Comprehensive Study of Convergent and Commutative Replicated Data Types. Technical Report 7506, INRIA, January 2011

    work page 2011

  25. [25]

    Epidemic Routing for Partially Connected Ad Hoc Networks

    Amin Vahdat and David Becker. Epidemic Routing for Partially Connected Ad Hoc Networks. Technical Report CS-200006, Duke University, Durham, USA, April 2000

    work page 2000

  26. [26]

    Logoot: A Scalable Optimistic Replication Algorithm for Collaborative Editing on P2P Networks

    Stephane Weiss, Pascal Urso, and Pascal Molli. Logoot: A Scalable Optimistic Replication Algorithm for Collaborative Editing on P2P Networks. In29th IEEE International Conference on Distributed Computing Systems (ICDCS’09), pages 404–412, Montreal, Canada, June 2009. IEEE.doi:10.1109/ICDCS.2009.75. 31 Appendix A Enhanced synchronization protocol NOTA: In ...

    work page doi:10.1109/icdcs.2009.75 2009