Yves Mahéo
email: yves.maheo@univ-ubs.fr

Frédéric Guidec
email: frederic.guidec@univ-ubs.fr

Camille Noûs
email: camille.nous@cogitamus.fr

CRDT-based Collaborative Editing in OppNets: a Practical Experiment

Keywords: Opportunistic networking, Experiment, CRDT, Collaborative editing

Developing distributed applications for opportunistic networks (OppNets) has mainly relied on the message passing paradigm so far. Yet the sharing of distributed data is an alternative worth considering, and Conflict-Free Replicated Datatypes (CRDTs) are interesting candidates for this purpose. A CRDT is a distributed data type that supports optimistic replication, and whose global consistency can be maintained based solely on occasional synchronizations of replicas. In an OppNet, these synchronizations can be driven by the contacts between mobile devices, without any need for network-wide routing. CRDTs can thus serve as interesting software building blocks to develop distributed applications for OppNets. In this paper, we demonstrate the feasibility of using CRDTs in OppNets by presenting an experiment conducted in real conditions, involving a collaborative editing application in which communication relies exclusively on opportunistic contacts between laptops. The software elements used in the experiment consist mainly of a CRDT-based text editor, and a communication module that supports the synchronization between laptops, so as to ensure the eventual consistency of the shared document. Experimentation results are detailed, that confirm the viability and usability of this approach.

I. INTRODUCTION

Opportunistic networks (OppNets) are infrastructure-less networks composed of mobile devices that communicate via direct device-to-device radio transmissions. Due to the sparse or irregular distribution of the devices, such networks are often partitioned, and do not provide permanent end-to-end connectivity. Yet, network-wide communication is made possible following the store, carry and forward principle: when a contact occurs between two devices, the opportunity to exchange messages can be seized. Received information can be stored locally, so that, the device that carries it can forward it later to another mobile device at the occasion of new contact. Developing applications for OppNets is challenging because of the inherent asynchronism of the communications, with potential large delays needed for reaching certain devices, from one to the next, according to their movements.

A number of use cases have been envisaged for opportunistic networks, namely when traditional network infrastructure is not available (e.g., communication for disaster relief or in remote areas) or when it is not desirable to use this infrastructure (e.g., for data offloading, or to avoid censorship).

To support such use cases, the research activity over the last two decades has primarily focused on message routing or dissemination in an OppNet, assuming that network-wide message passing is a de facto requirement of any distributed application, and assuming somehow that a message-oriented API is the best API for developers.

Yet, just like the High Performance Computing community uses alternatively the message-passing paradigm (typically via the Message Passing Interface [START_REF]Message Passing Interface Forum[END_REF]), or the shared-memory paradigm, via OpenMP [START_REF]The OpenMP API specification for parallel programming[END_REF] for example), depending on application needs, the developers of distributed applications for OppNets should not be bound to rely on a message-passing API, but they should also be offered the means to work with shared data structures.

A promising class of distributed shared data structures, called Conflict-Free Replicated Datatypes (CRDTs), has appeared recently, stemming from research on distributed databases and peer-to-peer networks [START_REF] Preguiça | Conflict-free Replicated Data Types: an Overview[END_REF]. CRDTs are distributed data types (counters, sets, maps, etc.) that support optimistic replication: replicas can be updated locally without any coordination, and synchronized asynchronously. CRDT replicas may temporarily diverge, but information is exchanged asynchronously between them thanks to a synchronization algorithm running in the background. This algorithm guarantees that all replicas eventually reach the same final state, provided the synchronization graph is connected, that is, provided the history of successive synchronizations is such that any update is eventually taken into account by every replica.

In the literature, the papers dealing with CRDTs in Opp-Nets present simulation results [START_REF] Guidec | Supporting conflict-free replicated data types in opportunistic networks[END_REF][5] [START_REF] Robin | DTNDocs: A delay tolerant peer-topeer collaborative editing system[END_REF][7] [START_REF] Alsulami | Collaborative Editing over Opportunistic Networks: State of the Art and Challenges[END_REF]. The question whether CRDTs can be of practical use in a real OppNet setting is thus as yet unanswered. The objective of this paper is to contribute to answer this question. It describes the different elements of the setting and the results of a real-world experiment carried out in order to assess the possibility to write a document collaboratively, by relying on the implementation of a CRDT deployed in an OppNet. To our knowledge, it is the first time that the use of a real application involving CRDTs in an OppNet is reported. The choice of collaborative editing as a case study is motivated by the fact that it is a demanding distributed application, for respecting the causality of editing operations is not trivial in an OppNet. Besides, several tested off-the-shelf software elements designed for peer-to-peer wired networks can be reused or adapted for OppNets, which makes it easier to develop a robust solution.

Figure 1 illustrates the kind of OppNet we consider: the contributors to the shared document use their laptops over a few days to edit the shared document collaboratively. Laptops A contributor may be isolated while editing the document (e.g., at home), in which case no transmission is possible between his/her laptop and those of other contributors. When several contributors are close to one another (e.g., in adjacent rooms at work), their laptops can synchronize by exchanging messages via direct wireless connections. When a user is on the move, his/her laptop is assumed to be switched off.

The remainder of this paper is organized as follows. Section II introduces the concept of CRDT and details the problem of their synchronization, in particular in OppNets. Section III quickly browses the works related to distributed applications targeting OppNets, and in particular on collaborative applications like text editing. In Section IV, we present the different software elements that support the text editing experiment we have set up. The results of this experiment are detailed in Section V. Section VI concludes the paper.

II. OVERVIEW OF CRDTS

When a data structure must be replicated in a distributed system, there are different ways to maintain the consistency of the replicas of this data structure. Some systems maintain strong consistency at any time by constraining concurrent updates of replicas, or preventing them altogether. Other systems implement optimistic replication, allowing replicas to diverge temporarily, while ensuring that they will eventually reach a common state (eventual consistency).

Conflict-free Replicated Data Types (CRDTs) support optimistic replication: any replica can be updated locally, at any time, without any coordination with the other replicas. Synchronization occurs in the background, usually periodically and between randomly selected pairs of replicas, by exchanging information about past updates. If the synchronization graph is connected (i.e., the consequence of each update is eventually taken into account by each replica), all replicas eventually reach the same state.

Concurrent updates and concurrency semantics

The implementation of traditional data types (counters, registers, sets, maps, lists, graphs, etc.) as CRDTs has already been addressed in the literature [3][9]. For each CRDT, the updates it can support are identified, and a concurrency semantics is defined. Note that several alternative concurrency semantics can often be defined for the same abstract data type, as shown below.

In order to illustrate how a CRDT can be used as a shared data structure, let us consider a basic example. A Set CRDT implements a shared set, and it can typically support updates add() and rmv(). Since these updates cannot commute when they are applied to the same element, a concurrency semantics must be defined to resolve conflicts between concurrent add(x) and rmv(x) updates. Figure 2 shows an example where a Set CRDT (initially empty) is replicated in two replicas R1 and R2. Element a is first added locally to the set in replica R1, while element b is added locally in replica R2. The state is thus temporarily different in R1 and R2, but a synchronization occurs between them, after which they agree that the state of the set is now {a, b}. Note that reconciling state {a} (from R1) with state {b} (from R2) is not an issue, because although add(a) and add(b) occurred concurrently in R1 and R2, they apply to distinct elements a and b.

After the first synchronization, element a is removed and then added again in R1, while it is only removed in R2. The state is thus different again in R1 and R2, and this time the last add(a) on R1 and rmv(a) on R2 conflict, as they occurred concurrently and apply to the same element a. If both replicas synchronize again, the final state depends on the concurrency semantics chosen for this shared set. A possible option is to give add(a) priority over rmv(a), so that the final state is {a, b} in both replicas. Another option is to give rmv(a) priority over add(a), so the final state is {b}. A Set CRDT that gives add() priority over rmv() is called an Add-wins set in the literature, and the opposite is called a Remove-wins set [START_REF] Preguiça | Conflict-free Replicated Data Types: an Overview[END_REF].

Synchronization of replicas

In the simple example shown in Figure 2, only two replicas are considered, so synchronization is only required between these two replicas. In a system that involves a large number of replicas, synchronization must be addressed with caution in order to guarantee that all replicas eventually converge, while maintaining the cost of synchronization at a reasonable level.

Several methods of synchronization have been considered in the literature, each method requiring a specific implementation of CRDTs. In an operation-based CRDT, whenever an operation (update) is applied to a replica, a description of this operation is embedded in a message, which is sent to all other replicas. This approach tends to produce a large number of small messages (each message carrying information about a single update). Besides it requires a system that supports reliable network-wide broadcast, and even causal broadcast if the updates do not commute [START_REF] Preguiça | Conflict-free Replicated Data Types: an Overview[END_REF].

In a state-based CRDT, each replica must synchronize periodically with other replicas by sending them its entire state. On each receiver the state of the sender is merged with the local state, using a function that deterministically computes the join (least upper bound) of both states. A major advantage of this approach is that is does not require that each update be transmitted to all replicas, so no broadcast is required. A periodic synchronization of each replica with a few other replicas is sufficient to ensure the eventual convergence of all replicas, as long as the synchronization graph is connected.

add(a) add(a) rmv(a) rmv(a) ∅ ∅ { a } { b } { b } { a, b } { a, b } { a, b } or { b } { a, b } or { b } { a, b } replica R1 replica R2 add(b) { b } Sync Sync

CRDTs in OppNets

In the literature, it is commonly assumed that CRDTs are to be deployed in Internet-based peer-to-peer networks. Network-wide message routing or broadcast are thus presumed to be available. In such conditions, each replica can either 1) send each update to all other replicas (in an operationbased CRDT), or 2) select randomly any other replica and synchronize with this replica (in a state-based or delta-statebased CRDT).

In an OppNet, two mobile devices can only communicate as long as they are neighbors. Implementing operationbased CRDTs, which involves sending each update to all other devices, is therefore not trivial as it requires at least epidemic delay-tolerant dissemination. As for state-based and delta-state-based CRDTs, they should rely on contact-driven synchronization, each device synchronizing with its neighbors rather than with randomly selected peers.

Synchronization algorithms for operation-based, statebased, and delta-state-based CRDTs in OppNets have been proposed and evaluated based on simulation scenarios in [START_REF] Guidec | Supporting conflict-free replicated data types in opportunistic networks[END_REF]. The results show that although all synchronization methods ensure the eventual consistency of CRDTs, delta-state-based synchronization clearly outperforms the two other modes of synchronization. Operation-based synchronization is easy to implement on top of an opportunistic communication layer that supports reliable causal broadcast. However, it requires the network-wide dissemination of many small messages (one for each update applied to a replica). This can yield a significant communication overhead in an OppNet, as well as storage issues since each message must be maintained in a local cache on each device. State-based and delta-state-based synchro-nization can be implemented without any multi-hop routing or network-wide dissemination, using only synchronization between neighbors. The cost of state-based synchronization is significant, though, as it requires exchanging entire states between neighbor devices. Delta-state-based synchronization gets the best of both other methods, as the amount of data transfers required to ensure the synchronization of replicas is kept at a minimum, and as there is no need for message routing or message broadcast.

The work presented in [START_REF] Guidec | Supporting conflict-free replicated data types in opportunistic networks[END_REF] has shown that CRDTs can be deployed in an OppNet, and converge as expected in such an environment ; but the given results have been obtained by running simulations. Whether distributed applications based on CRDTs can be of practical use in a real OppNet setting is still to be demonstrated. The purpose of this paper is to contribute to this task.

III. RELATED WORK

Running distributed applications in OppNets has been considered in many papers over the last two decades, but, again, most of these papers only present simulation results. Rare are the papers that present communication systems and applications that have been fully implemented, and tested in real conditions. Among these exceptions are [START_REF] Lindgren | Networking in the Land of Northern Lights: Two Years of Experiences from DTN System Deployments[END_REF] and [START_REF] Baumgärtner | An Experimental Evaluation of Delay-Tolerant Networking with Serval[END_REF], which present DTN systems aiming at providing Internet-like services in very sparsely populated areas, or in disaster-relief scenarios. Distributed applications for content sharing (files, music, news, software components, etc.) in OppNets have likewise been presented in [START_REF] Tennent | Three applications for mobile epidemic algorithms[END_REF] [START_REF] Chen | What a juke! A collaborative music sharing system[END_REF][17] [START_REF] Guidec | Opportunistic Software Deployment in Disconnected Mobile Ad Hoc Networks[END_REF].

In the abovementioned applications, the content shared over the network is considered as immutable. In contrast, collaborative editing (or, more generally, collaborative work) requires to share content that can change over time.

Although Web-based solutions such as wikis, Google Docs, Etherpad, etc. have been available for a long time now, these solutions usually rely on a client-server architecture, with central servers whose role is to store shared documents and ensure that concurrent editing of the same document does not yield inconsistencies.

Recognizing that any solution involving servers is hardly applicable in OppNets, an early solution for shared content editing in such networks has been proposed in [START_REF] Kärkkäinen | Shared Content Editing in Opportunistic Networks[END_REF]. In this proposal, a revision control mechanisms is used to merge contributions whenever possible, but user intervention is still required to solve conflicting contributions. In [START_REF] Costea | Total Order in Opportunistic Networks[END_REF] the problem of ensuring total order in OppNets is considered, as a means to support a variant of the Logoot [START_REF] Weiss | Logoot: A Scalable Optimistic Replication Algorithm for Collaborative Editing on P2P Networks[END_REF] replication algorithm in such networks. A similar approach is presented in [START_REF] Robin | DTNDocs: A delay tolerant peer-topeer collaborative editing system[END_REF], using IBR-DTN [START_REF] Doering | IBR-DTN: an efficient implementation for embedded systems[END_REF] for opportunistic communication, and a modified LogootSplit [START_REF] André | Supporting adaptable granularity of changes for massive-scale collaborative editing[END_REF] algorithm for ensuring consistency in shared content editing. An approach based on OT (Operational Transformation) is considered in [START_REF] Alsulami | Collaborative Editing over Opportunistic Networks: State of the Art and Challenges[END_REF], and the convergence of an OT-based collaborative editing framework in opportunistic networking scenarios is investigated. Unfortunately, all these papers only present simulation results, and in most cases it is unlikely that a fully-functional collaborative editing solution exists beyond the simulation code.

In the remainder of this paper we describe the implementation of such a fully-functional solution, and demonstrate that it is viable for actual collaborative editing in opportunistic networking conditions.

IV. DESIGN AND IMPLEMENTATION

The key feature of our experiment is the use of a Conflict-Free Replicated Datatype to guarantee the consistency of the different contributions to the shared document. In our experimental setup, several software elements have been assembled to allow CRDT-based collaborative editing, forming two main layers (see Figure 3). The upper layer runs in a Web browser. It is thus a Web application that combines the editor itself with the implementation of the CRDT that will ensure the consistency of the shared document. The lower layer enables the opportunistic communication between the contributors' laptops, thus allowing the synchronization of the different replicas of the CRDT. The two layers interact via a websocket. In addition, a Web server is deployed locally to supply the code and data of the Web application. Note that the fact that our editing application is based on Web technologies is not a fundamental requirement. It rather results from the choice of an available, extensible and efficient CRDT-based editor.

Opportunistic communication

The main functions of the opportunistic communication layer we developed are, on the one hand, to ensure neighbor detection (i.e., to detect laptops located within the radio range), and on the other hand to establish a bidirectional communication channel between each pair of neighbors.

Neighbor detection is trivially based on the periodic broadcasting, by each laptop, of HELLO messages that contain the identity of the emitting device (typically the hostname), its IP address, and the TCP port number it listens to. This broadcast is only performed at one hop (i.e., without any routing), so that each host can only detect its 1-hop neighbors. HELLO messages are embedded in UDP datagrams, and addressed to a predefined multicast group. When a laptop receives a HELLO message from a new neighbor with a lower identity (in lexicographic order), it opens a TCP session (with TLS encryption) with this new neighbor. This session will then serve as a bidirectional channel between the two neighbors, as long as they remain in radio contact. When a contact is lost between two neighbors, it can be reestablished later if they meet again.

CRDT-based editor

We chose the Quill text editor [START_REF]Yjs -A CRDT framework with a powerful abstraction of shared data[END_REF] as the editing software. This editor is written in HTML/CSS/Javascript. It can be associated with Yjs [START_REF][END_REF], through the quill-yjs binding module, so that the edited text is maintained internally as a CRDT. Yjs is a Javascript implementation of several types of CRDTs (array, map, text, etc.). It is mainly oriented to linear data structures like text [START_REF] Nicolaescu | Near Real-Time Peer-to-Peer Shared Editing on Extensible Data Types[END_REF]. Figure 4 illustrates the manipulation of a piece of text through the use of the Yjs Javascript library, as could be done by the Quill editor (in this figure, and also in Figures 5 and6, the functions provided by Yjs are in boldface type).

One of the most interesting characteristics of Yjs is its efficient way of encoding a text CRDT as a double chained list of inserted items (sequences of characters identified by Lamport timestamps) accompanied with a set of deletions (simple set of items), which confers a high efficiency for human-produced text manipulation.

Yjs itself is network agnostic: some extra code is required to ensure the synchronization of replicas. This code must be included in a Yjs provider. The providers distributed with Yjs are not suited to opportunistic networking, as they target Internet-based contexts (by using typically WebRTC or centralized servers). We therefore developed our own Yjs provider, called opp-provider, which supports delta-state-based synchronization. This task was facilitated by two features of Yjs: updates and state vectors. An update encodes a series of changes in a document that can serve to modify another document. Updates are commutative, associative, and idempotent. These properties are essential to ensure the eventual convergence of all replicas, whatever the order in which updates are applied to each replica. A state vector characterizes the state of advancement of all replicas, as perceived by one replica. It is essentially a set of Lamport timestamps that captures the causal context. Updates and state vectors are provided to the programmer as opaque structures encoded in a compressed binary format. The opp-provider is notified of editing events (issued by the Yjs module) and neighbor discovery events (issued by the underlying opportunistic communication layer). When a contributor edits the text (by inserting or deleting a character), the opp-provider immediately broadcasts the corresponding update to all current neighbor laptops (if any). The receiving neighbors can then apply this update on their own replica (see Figure 5). From a contributor's perspective, collaborative editing operates in real time between his/her laptop and neighbor laptops. The updates exchanged between these laptops are embedded in small messages, as each update only pertains to the last operation performed on the sender.

In contrast, when two laptops get into radio contact (and become neighbors), their local states must be synchronized, which usually requires exchanging larger messages. The two new neighbors first exchange state vectors, and then exchange only what the other laptop needs to reach a common state (see Figure 6).

V. EXPERIMENT

Experimental conditions

In order to assess whether collaborative editing based on opportunistic communication can be of practical use, we decided to use this approach to write the latest deliverable of a project our research team is involved in. This project involves six permanent staff members, which all agreed to participate in this experiment. These six participants are not always collocated, though. For example, they all have teaching duties, which do not always occur in the same campus or in the same buildings. Besides, most team members work at home part of the time, so they meet only occasionally. As a general rule, two meetings are organized every week, though, vector = Y.encodeStateVector(ydoc) send(vector, neighbor)

• On the reception of a state vector v delta = Y.encodeStateAsUpdate(ydoc, v) send(delta, neighbor)

• On the reception of a delta d Y.applyUpdate(ydoc, d)

• On the reception of a state vector v sv = v vector = Y.encodeStateVector(ydoc) send(vector, neighbor) on Tuesday and Friday afternoons, but not all team members attend every meeting.

The appropriate software was installed on each participant's laptop (running Linux), and this laptop was configured so as to support opportunistic communication. More specifically:

• A secondary Wi-Fi interface (small form factor USB dongle) was added to each laptop, and this interface was configured so as to operate continuously in Wi-Fi ad hoc mode. The primary builtin Wi-Fi interface of each laptop therefore remained available for daily activities such as Web browsing, Email, etc. The secondary interface was meant to be used only for opportunistic communication, that is, in that case, for collaborative editing. • The opportunistic communication layer (cf. Figure 3) was installed on each laptop, configured to use the secondary interface (with self-assigned IPv6 addresses), and run in the background as a systemd service. • The desktop settings on each laptop were configured so that the Web browser opened as soon as the user logged in, and the browser itself was configured so that the Quill/Yjs page was loaded automatically. The participants were asked to keep the browser running as much as possible, and to maintain a window or tab on Quill/Yjs in this browser (note that this did not prevent them to browse other Web sites). The motivation was to ensure that Yjs would keep running in the background, thus ensuring automatically the synchronization between the laptops used in this experiment. • Each laptop was configured so as to log interesting events, such as the laptop being switched on or off, the discovery of a new neighbor, etc. Overall, each laptop was configured so that his/her owner could keep using it as usual (browsing the Web, sending and receiving Email, etc.), while collaborative editing was

Results

The whole experiment lasted 9 days, including one weekend (from Monday to the next Tuesday). Figure 7 shows the timelines of each laptop's activity during that period. Each laptop is identified by the initials of its owner's name. In this figure, each horizontal yellow segment corresponds to a period during which the corresponding laptop was up and running. Purple segments mark periods when editing activity was observed on this laptop (i.e., the user was actually editing the shared document). The thin vertical blue lines indicate the beginning of a pairwise radio contact between two laptops, that is, an opportunity for these laptops to synchronize their copies of the shared document.

Figure 8 shows details about the activity observed on a specific day (Wednesday) during the experiment.

Figure 9 shows the evolution of the number of active laptops at any time during the experiment (blue), as well as the number of pairwise connections between these laptops (red). It can be observed that although several laptops were sometimes running at the same time, this does not imply that all these laptops were connected over the wireless ad hoc channel. For I andII. They concern the editing events and the transfers of synchronization messages, and the radio contacts and inter-contacts between laptops.

The shared document produced during this experiment is 102 651-character long (36 pages, in plain text). The numbers of ins, del, cut, and paste events triggered to produce this document are detailed in Table I. Overall, 109 synchronizations occurred between pairs of laptops upon radio contact, which is consistent with the number of contacts observed (see Table II). Each of these synchronizations involved the exchange of state vectors and delta states between two laptops, as shown in Figure 10. The state vectors (at most 700 bytes) were of course far smaller than the deltas transferred upon contacts.

While laptops were in contact, 102 561 transfers of updates were observed. These transfers of updates are actually transfers of deltas pertaining to the last operation applied on the sender, but we distinguish updates from deltas here because updates are significantly smaller. Figure 11 shows the evolution of the size of the messages carrying these updates over time. A large majority of these messages were indeed quite small (about 130 bytes), for they concerned only the insertion or the removal of a single character. Occasionally, larger messages were observed (up to 700 bytes), when a user pasted a piece of text in the shared document. Note that no attempt was made to compress the data transmitted in the messages in this early version of our editing system.

Figure 12 shows the evolution of the size of the shared document on each laptop. It can be observed that this size sometimes trailed behind significantly on some laptops (see for example laptops FL and LT on Friday), as some participants worked far from any other participant, thus preventing their laptop to synchronize with other laptops. The weekly meetings on Tuesday and Friday afternoons allowed most laptops to fully synchronize, although some participants did not attend all meetings and therefore relied on unplanned contacts to get the latest contributions of every other participant. For example, the shared document was finalized (as planned) during the last Tuesday meeting, even though one of the participants did not attend this meeting. A contact with this participant's laptop occurred shortly after this meeting, which allowed this laptop to get the final version of the document.

Outcome of this experiment

The experiment described earlier only involved six participants over a few days. With this small-scale experiment our prime motivation was to verify that collaborative editing based on opportunistic communication is indeed doable and practical. It turns out that editing a shared document in such conditions is actually a near-real-time experience, with synchronizations depending on unpredicted collocation between contributors. At the end of the experimentation period, the participants confirmed that while working on this deliverable they did not perceive opportunistic synchronization as an inconvenience.

Of course opportunistic synchronization requires that all updates eventually reach all replicas. More specifically, the synchronization graph must be connected, which is actually a major requirement for any distributed application involving CRDTs [START_REF] Preguiça | Conflict-free Replicated Data Types: an Overview[END_REF]. This experiment shows that this requirement can easily be met in a real-life scenario.

Scalability

Scalability is usually a typical concern in distributed applications. Yet, the question whether an experiment similar to that described above could have been performed with hundreds of participants hardly makes sense, since editing a shared document with so many contributors would probably not be practical anyway.

Yjs can however support other kinds of CRDTs (namely arrays or maps), which can serve as building blocks for a large variety of data structures. The software system used in our experiment could therefore be used to support large-scale CRDT-based collaborative applications. In order to determine if this software system would scale up, we ran additional experiments in emulation mode. In these experiments, the LEPTON platform [START_REF] Sánchez-Carmona | Filling in the missing link between simulation and application in opportunistic networking[END_REF] was used to simulate the mobility and opportunistic contacts of a large number of virtual nodes. For each of these virtual nodes, instead of running Quill/Yjs in a Web browser, we used node.js and replaced the real editor Quill by a dummy editor we developed in order to mimic the editing events a real user would generate over time.

With this architecture we ran scenarios involving up to 200 virtual nodes editing the same shared document concurrently, and did not observe any adverse effect on the eventual convergence of all copies of the shared document.

VI. CONCLUSION

In this paper, we have described the experimental setup and the results of a real-life experiment involving a group of researchers that collaboratively edited a document over nine days, relying exclusively on opportunistic communication

Figure 1 .

 1 Figure 1. Illustration of collaborative editing in an opportunistic network

Figure 2 .

 2 Figure 2. Example of a run involving a Set CRDT replicated in two replicas R1 and R2

Figure 3 .

 3 Figure 3. Software elements deployed on each laptop (the elements we have developed are named in boldface)

Figure 4 .

 4 Figure 4. Example of the use of a text CRDT via the Javascript Yjs module

Figure 7 .Figure 8 .

 78 Figure 7. Details of each laptop's activity during the experiment

Figure 9 .

 9 Figure 9. Number of active laptops (blue) and number of pairwise connections between laptops (red)

  The main drawback of state-based CRDTs is that shipping entire states between replicas can be costly. Delta-state CRDTs reduce this cost by passing only partial information (a delta) about the

sender's state (typically, only what is required to allow the target receiver to update its own local state) [10][11][12]. In order to determine what is required by another replica, the sender must first receive a digest of this replica's state, and compare this digest with its own local state. The digest of a state can typically take the form of a state vector.

  Figure 5. Synchronization performed on a set of neighbors when a contributor modifies the text (the code on the top runs on the laptop where the text is modified)

	// Capture the modification event and // broadcast the update to the neighbors
	ydoc.on('update', (upd) => { broadcast(upd) }
	// Receive the update and // apply it to the document
	• On the reception of update upd Y.applyUpdate(ydoc, upd)

  Figure 6. Delta-state-based synchronization applied when two neighboring laptops enter in contact (the code on the top is executed by the neighbor with the larger identity)

	• On the reception of a delta d Y.applyUpdate(ydoc,d) delta = Y.encodeStateAsUpdate(ydoc, sv) send(delta, neighbor)

document simultaneously would probably be useless).

We believe this work paves the way for the deployment and use of distributed collaborative applications in situations where opportunistic communication would be the primary and possibly only option, in remote areas or in a disaster-relief situation for example.

The analysis of the log files produced during the experiment confirmed the opportunistic nature of the network formed by the laptops, and the ability of the CRDT-based editing system to maintain the consistency of the replicas stored on each laptop. This small-scale experiment was conducted in an academic setting, avoiding deliberately -and somehow artificially-to rely on the Internet for collaborative editing. It confirms that actual collaborative work in opportunistic networking conditions is indeed viable. Moreover, the mobility of the nodes and the users' behavior are not fundamentally different from those found in other application domains, which let us think that the usefulness of the approach is quite general. Besides, a simulation run involving the same CRDT-based editing system with 200 virtual contributors shows that scalability is not an issue (although having that many contributors edit the same


Gagandeep Singh

Preface

This volume contains the proceedings of the 29th edition of the International Static Analysis Symposium, SAS 2022, held during December 5-7, 2022, in Auckland, New Zealand. The conference was a co-located event of SPLASH, the ACM SIGPLAN conference on Systems, Programming, Languages, and Applications: Software for Humanity. Travel restrictions as a result of the COVID-19 pandemic forced us to organize the conference in a hybrid form.

Static analysis is widely recognized as a fundamental tool for program verification, bug detection, compiler optimization, program understanding, and software maintenance. The series of Static Analysis Symposia has served as the primary venue for the presentation of theoretical, practical, and application advances in the area. Previous symposia were held in Chicago, Porto, Freiburg, New York, Edinburgh, Saint-Malo, Munich, Seattle, Deauville, Venice, Perpignan, Los Angeles, Valencia, Kongens Lyngby, Seoul, London, Verona, San Diego, Madrid, Paris, Santa Barbara, Venice, Pisa, Paris, Aachen, Glasgow, and Namur.

SAS 2022 called for papers on topics including, but not limited to, abstract interpretation, automated deduction, data flow analysis, debugging techniques, deductive methods, emerging applications, model checking, data science, program optimizations and transformations, program synthesis, program verification, machine learning and verification, security analysis, tool environments and architectures, theoretical frameworks, type checking, and distributed or networked systems. Besides the regular papers, the authors were encouraged to submit short submissions in the NEAT category to discuss experiences with static analysis tools, industrial reports, and case studies, along with tool papers, brief announcements of work in progress, well-motivated discussions of new questions or new areas, etc. Authors were encouraged to submit artifacts accompanying their papers to strengthen evaluations and the reproducibility of results.

The conference employed a double-blind reviewing process with an author response period, supported on EasyChair. This year, SAS had 48 submitted papers (43 regular and five NEAT). Of these, five were desk rejected due to not being in scope for SAS. The Program Committee used a two-round review process, where each remaining submission received at least three first-round reviews, which the authors could then respond to. The author response period was followed by a two-week Program Committee discussion where consensus was reached on the papers to be accepted, after a thorough assessment of the relevance and the quality of the work. Overall, 18 papers were accepted for publication (16 regular and two NEAT) and appear in this volume. The submitted papers were authored by researchers around the world: Canada, China, France, Germany, India, Israel, Italy, Singapore, the UK, the USA, and several other countries.

We view the artifacts as being equally important for the success and development of static analysis as the written papers. It is important for researchers to be able to independently reproduce experiments, which is greatly facilitated by having the original artifacts available. Marc Chevalier, the artifact committee chair, set up the artifact committee. In line with SAS 2021, the authors could submit either the Docker or Virtual Machine images as artifacts. A public archival repository for the artifacts is available on Zenodo, hosted at https://zenodo.org/communities/sas-2022. The artifacts have badges awarded at three levels: Validated (correct functionality), Extensible (with source code), and Available (on the Zenodo repository). The artwork for the badges is by Arpita Biswas (Harvard University) and Suvam Mukherjee (Microsoft). SAS 2022 had 16 valid artifact submissions, of which one was desk rejected as the authors did not submit a valid artifact. The review process for the artifacts was similar to those for the papers. Each artifact was evaluated by three members of the artifact evaluation committee, and eight out of 15 valid artifacts were accepted.

In addition to the contributed papers, SAS 2022 also featured three invited talks by distinguished researchers: Suguman Bansal (Georgia Tech, USA), Bernhard Scholz (University of Sydney, Australia), and Nengkun Yu (University of Technology Sydney, Australia). The Program Committee also selected the recipient of the Radhia Cousot Young Researcher Best Paper Award, given to a paper with a significant contribution from a student. This award was instituted in memory of Radhia Cousot, for her fundamental contributions to static analysis and having been one of the main promoters and organizers of the SAS series of conferences.

The SAS program would not have been possible without the efforts of many people. We thank them all. The members of the Program Committee, the artifact evaluation committee, and the external reviewers worked tirelessly to select a strong program, offering constructive and helpful feedback to the authors in their reviews. The organizing committee of SPLASH 2022, chaired by Alex Potanin (Australian National University, Australia), and the hybridization committee, chaired by Jonathan Aldrich (CMU, USA) and Youyou Kong (Tokyo Institute of Technology, Japan), were tremendously helpful in navigating the conference through these difficult times. The SAS steering committee provided much-needed support and advice. Finally, we thank Springer for their support of this event as well as for publishing these proceedings.

October 2022

Caterina Urban Gagandeep Singh vi Preface

Organization Program Committee Chairs Gagandeep Singh VMware Research and UIUC, USA Caterina Urban Inria and ENS|PSL, France Steering Committee Bor-Yuh Evan Chang University of Colorado Boulder, USA Patrick Cousot New York University, USA Cezara Dragoi Inria and ENS|PSL and Informal Systems, France Kedar Namjoshi Nokia Bell Labs, USA David Pichardie Meta, France Andreas Podelski University of Freiburg, Germany Francesco Ranzato University of Padua, Italy Mihaela Sighireanu ENS Paris-Saclay, France Program Committee Sebastien Bardin CEA-List, France Liqian Chen National University of Defense Technology, China Patrick Cousot New York University, USA Arlen Cox IDA and CCS, USA Dana Drachsler Cohen Technion, Israel Jerome Feret Inria and ENS|PSL, France Pietro Ferrara Ca' Foscari University of Venice, Italy Roberto Giacobazzi University of Verona, Italy Kihong Heo KAIST, South Korea Paddy Krishnan Oracle Labs, Australia Isabella Mastroeni University of Verona, Italy Antoine Miné Sorbonne Université, France Raphaël Monat Sorbonne Université, France David Monniaux CNRS and VERIMAG, France Jorge A. Navas SRI International, USA Francesco Ranzato University of Padua, Italy Daniel Schoepe Amazon, UK Mihaela Sighireanu ENS Paris-Saclay, France Manu Sridharan University of California, Riverside, USA Benno Stein Meta, USA Laura Titolo National Institute of Aerospace, USA

Artifact Evaluation Chair