Hoai Le Nguyen
email: hoai-le.nguyen@inria.fr

Claudia-Lavinia Ignat

Time-position characterization of conflicts: a case study of collaborative editing

Keywords: Collaborative editing, Collaboration patterns, Conflicts, ShareLaTeX

Collaborative editing (CE) became increasingly common, often compulsory in academia and industry where people work in teams and are distributed across space and time. We aim to study collaborative editing behavior in terms of collaboration patterns users adopt and in terms of a characterisation of conflicts, i.e. edits from different users that occur close in time and position in the document. The process of a CE can be split into several editing 'sessions' which are performed by a single author ('single-authored session' ) or several authors ('co-authored session' ). This fragmentation process requires a pre-defined 'maximum time gap' between sessions which is not yet well defined in previous studies. In this study, we analysed CE logs of 108 collaboratively edited documents. We show how to establish a suitable 'maximum time gap' to split CE activities into sessions by evaluating the distribution of the time distance between two adjacent sessions. We studied editing activities inside each 'co-author session' in order to define potential conflicts in terms of time and position dimensions before they occur in the document. We also analysed how many of these potential conflicts become real conflicts. Findings show that potential conflicting cases are few. However, they are more likely to become real conflicts.

Introduction

Today, modern word processors such as Google Docs [START_REF] Googledocs | Create and share your work online[END_REF], ShareLaTeX [START_REF] Sharelatex | Online LaTex editor[END_REF], Etherpad [7] are popular with many useful features to support collaborative editing (CE) such as adding comments, in-line communication (chat), revision histories and editing logs. The question 'How people write together' [START_REF] Posner | How people write together (groupware)[END_REF][START_REF] Olson | How people write together now: Beginning the investigation with advanced undergraduates in a project course[END_REF] captured the attention of CSCW researchers. Birnholtz et al [START_REF] Birnholtz | Tracking changes in collaborative writing: Edits, visibility and group maintenance[END_REF] reveal that edits and comments in CE often carry social meaning i.e. they can have emotional and relational impact. The authors also pointed out that communication can be used to explain potentially conflicting behaviors and avoid negative relational effect. Their follow up research [START_REF] Birnholtz | Write here, write now!: An experimental study of group maintenance in collaborative writing[END_REF] presented an experimental study of group maintenance in collaborative editing using Google Docs. This is the first research that considered to analyse editing logs. The study was separated into an asynchronous phase followed by a synchronous phase. In the asynchronous phase two users separately edited a document on a specific topic and then shared it with the assigned partner who provided feedback and revised the document. The synchronous phase required that the two users edit a shared document summarizing their opinions expressed in their previously written documents. However, the study was controlled by separating the writing activity into asynchronous and synchronous and has not given users the freedom to choose and alternate the writing style. Moreover, the study focused uniquely on the relationship between communication, editing and collaborators social relationships and did not study the editing process of users.

Follow up research studied how people collaboratively edit documents by analysing collaborative editing logs. Sun et al [17] presented an analysis of collaboration logs over two years of all Google employees using Google Docs suite. They found that collaboration editing has grown rapidly up to 53% during the period they examined and 'concurrent editing is sticky' with 76% of the employees who participated in a 'concurrent session' repeating the activity in the following month. In [START_REF] Ignat | Studying the effect of delay on group performance in collaborative editing[END_REF][START_REF] Ignat | How Do User Groups Cope with Delay in Real-Time Collaborative Note Taking[END_REF] authors studied the effect of delay on the error rate, redundancy and quality of collaboratively produced documents by analyzing logs of real-time collaborative editing tasks using Etherpad. Olson et al [START_REF] Olson | How people write together now: Beginning the investigation with advanced undergraduates in a project course[END_REF] examined the traces of collaborative writing behavior of advanced undergraduates in a project course using Google Docs. They found that 95% of documents have some simultaneous work (i.e have at least one 'co-authored session'). The study assesses the quality of the collaboratively edited documents and analyses different aspects of CE using the taxonomy of CE [START_REF] Posner | How people write together (groupware)[END_REF][START_REF] Lowry | Building a taxonomy and nomenclature of collaborative writing to improve interdisciplinary research and practice[END_REF]. D'Angelo et al [START_REF] D'angelo | Spacetime characterization of real-time collaborative editing[END_REF] analysed the histories of a large collection of documents edited in Etherpad[7] to study how people are writing in the wild and found that simultaneous editing happens very rarely.

Conflict is a common phenomenon in collaboration between groups of people, and conflict management is a key concern in designing collaborative applications [START_REF] Easterbrook | A survey of empirical studies of conflict[END_REF]. In collaborative editing conflicts occur when users concurrently write in the same part of the document. As stated in [START_REF] Dourish | Consistency guarantees: Exploiting application semantics for consistency management in a collaboration toolkit[END_REF], syntactic conflicts occur at the system infrastructure level, while semantic conflicts are inconsistencies from the perspective of the application domain. Generally, merging algorithms underlying the application solve the syntactic inconsistency problems in collaborative text editing, but they do not enforce semantic consistency. In [START_REF] Nguyen | An analysis of merge conflicts and resolutions in git-based open source projects[END_REF] authors studied conflicts in asynchronous collaboration over open source software projects that used Git.

We aim to study collaborative editing behavior in terms of patterns of collaboration users adopt such as alternating synchronous and asynchronous collaboration and measuring and comparing user performances during the different collaboration modes. We also aim to study a characterisation of conflicts in terms of time and position in the document.

The process of collaborative editing can be split into several sessions, including single-authored sessions and co-authored sessions. The previous studies did not well define a suitable 'interval' or 'maximum time gap' which is used for this fragmentation process. Moreover, they haven't provided a detailed analysis of editing activities inside these sessions. We particularly aim to analyse collaborative edits inside co-author sessions and study how users manage 'potential conflict' cases when they edit together in a close period of time and in close parts of the document. For this purpose we define a characterisation of collaborative editing by means of time-position windows. Our research questions are listed below:

1. How to choose a suitable 'maximum time gap' to split editing activities into sessions? 2. What is the time-position characterization of editing sessions, namely for 'co-authored sessions' ? 3. Inside 'co-authored sessions', how often 'potential conflicts' happen within some time-position extension (condition)?

The rest of the paper is organized as follows. In section 2, we present related approaches which are based on an analysis of the traces of collaborative editing. In section 3, we describe the measurements of our study. We then discuss about our results and conclusion of this study.

Related work

Sun et al [17] published an in-house study that analysed the logs of activity for all Google employees from 2011 to 2013. They found that on that period, the percentage of new employees who collaborate on Google Docs per month has risen from 70% to 90%. To estimate the percentage of documents which had concurrent editing, they used a 15 minutes interval to split documents into intervals and consider edits by different users in the same 15 minutes intervals as concurrent edits. The choice of 15 minutes intervals is arbitrary. And this approach has edge cases in which two users edit the same document within 15 minutes but they are split into two adjacent intervals and are not counted as concurrent edits. Authors proposed a more accurate approach which is looking for a sequence of edits by different users with the maximum gap of 15 minutes. However this proposed mechanism was not applied.

Olson et al [START_REF] Olson | How people write together now: Beginning the investigation with advanced undergraduates in a project course[END_REF] collected and analysed 96 Google Docs documents written by 32 teams of undergraduate students from the Project Management class in three successive years (2011, 2012 and 2013) at University of California, Irvine. They found that 95% of the documents exhibited some simultaneous work. In fact, they used the approach of [17] with the 7 minutes gap. To determine the 7 minutes gap, they examined all documents with 15 minutes gap and found that 90% of them were 7 minutes or less. In more details, a document consists of many sessions. Each session combines a series of slices. Each slice which aggregates a series of keystrokes is generated after a certain of pause or a certain amount of edits. If a session was edited by more than one editor, they consider it as a simultaneous session. The others are considered as solo-authored sessions.

Both studies above focus only on time-dimension of collaborative editing. If two authors edit a document within 7 or 15 minutes gaps, they are considered as having a simultaneous writing session either they can edit in adjacent positions or far different positions. The choices of 7 or 15 minutes gaps are still arbitrary. In another study, Larsen et al [START_REF] Larsen-Ledet | Territorial functioning in collaborative writing[END_REF] use a mixed methods involving interviews and analysis of the traces of collaborative editing documents (using Google Docs) to outline the role of 'territorial functioning' in CE. On their analysis, they take into account the position-dimension of edits to visualize the 'editing territories' of different authors over the time. However, for the time-dimension, they use the same technique as previous studies of Sun et al [17] and Wang et al [START_REF] Wang | Docuviz: Visualizing collaborative writing[END_REF] which is based on the 15 minutes time gap.

D'Angelo et al [START_REF] D'angelo | Spacetime characterization of real-time collaborative editing[END_REF] presented a study on how Etherpad, a real-time collaborative editing tool, is used in the wild. They analysed the histories of a large collection of documents (about 14000 pads) in both time and position dimensions. Edits are independently classified as collaborative or not in time, position and time-position. An edit is considered as collaborative in time dimension if it is close enough in time to an edit applied by a different author. In this study, they used the time windows which are 5, 10 and 60 seconds to determine if an edit is close enough or not. And similarly, they used the position window of 10, 80, 400 and 800 characters. For two-dimensional analysis (time-position), all pairs of time/position windows were used. Results show that about half of the pads were edited by a single author. Asynchronous collaboration in which users edit in close positions of the document but in different times happens often. Simultaneous editing in which users edit in close positions within the same time window happens very rarely. Note that they used the proportion of time, position and time-position collaborative edits over the total edits of the documents for their inferences.

While [17] and [START_REF] Olson | How people write together now: Beginning the investigation with advanced undergraduates in a project course[END_REF] focus on finding if a document has some simultaneous sessions or not, [START_REF] D'angelo | Spacetime characterization of real-time collaborative editing[END_REF] focuses on finding the quantity of simultaneous edits of shared editing documents. It presents a more detailed quantitative analysis of collaborative editing than the two previous works. However it lacks the overview of how people work together. For example, people can use 'divide and conquer' strategy in which editors work in different parts (positions) of the document [START_REF] Wang | Docuviz: Visualizing collaborative writing[END_REF]. Then it's obviously that the document presents only time collaborative edits results on their analysis. Beside, the 5 seconds or 10 seconds time window is too short to have multiple editing activities. People can stop to discuss or to read the work of the others during several minutes before continue to write. Moreover, when people are free to collaborate, they do not edit simultaneously all the time. There are several sessions that they work asynchronously [START_REF] Olson | How people write together now: Beginning the investigation with advanced undergraduates in a project course[END_REF].

Time and position characterisation

We analysed [START_REF] Sharelatex | Online LaTex editor[END_REF] logs which were collected from a ShareLaTeX server used inside an engineering school and anonymized for privacy purpose. Groups of three or four students were assigned a writing task and required to use a shared Share-LaTeX document for their collaborative writing. All editing activities inside the shared document were recorded by ShareLaTeX server from the beginning until the end of the assignment, i.e. from 20-September-2017 to 20-November-2017. Students could collaboratively edit the shared documents while being collocated during their classes or remotely from home. However, users were free to use other coordination tools to coordinate their work. We have not analysed their coordination efforts during the task.

In ShareLaTeX, there are two types of edits which are 'Insertion' and 'Deletion'. They are recorded with the following information: the timestamp when they happen, the position in the document where they happen, the user-id who performs the edit, the action-type which determines the type of edit, i.e. an 'Insertion' or a 'Deletion' and the content which is inserted or deleted. The content of an edit can be a single character or a long string. In addition, a copy-paste action is considered as an 'Insertion'. A modification action is considered as a 'Deletion' of the old content followed by an 'Insertion' of the new content.

We retrieved 1748 documents from the logs. However, 856 documents were created for testing purpose (i.e they were created and edited by a single user and have none or only one edit action). In the rest 892 documents, only 108 of them were edited by more than one author. As we are focusing on collaborative editing, our analysis was performed on these 108 documents. Table 1 presents the overview of our data in which 'No. of authors' and 'No. of edits' are the number of editors and the number of recorded editing activities of each documents. The 'Amount of edit' is the sum of all content edits lengths . A document can be presented in time-position view (two dimensional view). Figure 1 presents a sample document which is segmented into three writing sessions by time dimension. These sessions are classified into single-author-session (SAS) and co-author-session (CAS) depending on the number of editors of each session. In this sample we have one SAS and two CASs. Note that in a CAS, two or more editors can edit in the same position or in different positions. For a time dimension analysis we defined 'internal time distance' (or internal-distance) which is the time distance between two adjacent edits in the same session and 'external time distance' (or external-distance) which is the time distance between two adjacent sessions in a document.

Time dimension

We first borrow the proposed approach of [17] to analyse the 'time dimension' of our data. Instead of using only an 'arbitrary maximum time gaps', we try to examine the data with different 'maximum time gaps' : 15 minutes, 7 minutes, 5 minutes, 2 minutes, 1 minute and 30 seconds. Furthermore, after dividing a document into sessions and classifying the sessions into SASs and CASs, we analysed the differences between CASs and SASs such as: the internal-distance which is the distance between two edits in the same session, the average time which is the average length of sessions, the average number of edits of sessions.

Table 2 presents all the results of our analysis in time dimension. Doc having CAS(s) shows the number of documents that have at least one co-author session. The proportion of Doc having CAS(s) over all analysed (108) documents is 77.77% with 15 minutes time gap and downs to 69.44% with 30 seconds time gap. In comparison to [START_REF] Olson | How people write together now: Beginning the investigation with advanced undergraduates in a project course[END_REF] which showed that 95% of documents exhibited some 'simultaneous work' with 7 minutes time gap, our data set shows that 75.92% of documents have collaborative sessions. Also with this time gap, our analysis shows that the average length of co-author sessions is 2369 seconds (39.5 minutes) and the longest co-author session is 8639 seconds (144 minutes) while they are 9.2 minutes (average) and 74 minutes (longest) in [START_REF] Olson | How people write together now: Beginning the investigation with advanced undergraduates in a project course[END_REF].

No. of CASs per Doc is the average number of CASs in each document after a segmentation of the document with the given time gaps. We also displayed the proportion of CASs over all sessions (CASs and SASs). The smaller time gaps given, the more CASs are generated. However, it reduces the proportion of CASs over the total sessions. In another way, the number of CASs increases slower than the number of SASs when the time gap decreases. Internal-distance presents the average internal distance between two edits in the same session (SASs or CASs). For more details, we calculated the confidence interval with 99% of significance (CI 99%) for the internal distance variable. We found that the internal distance of SASs is longer than the internal distance of CASs. In another way, the distance between two edits in single-author sessions is longer than the one in co-authors sessions.

Session length shows the average length in seconds of each session, i.e. how long each session lasts. No. of edits is the average number of edits in each session. We found that (with 99% of significance) the average length of CASs is longer than the average length of SASs and also that CASs have larger number of edits than SASs in average. In order to compare No. of edits for CASs and SASs, we normalized No. of edits of CASs as it includes edits from all collaborators while No. of edits of SASs includes only edits of a single editor. Normalized No. of edits of each document is calculated by dividing original No. of edits to the number of collaborators. Having more edits with shorter distance between edits and longer collaborating time, it significantly gives us a quantitative view that the co-authors sessions are more productive in terms of the quantity of contributions to the documents than the single-author sessions.

As the maximum internal-distance is limited by the time gap, it's obviously that the internal-distance presented in Table 2 must be shorter than the given time gap. However, the result shows that the average internal-distance is much shorter than expected. For a better understanding, we calculated the confidence interval of internal-distance for each documents with 90% significance. Both SASs and CASs were included in this analysis. Figure 2 presents the results of 420s (7 minutes) time gap in which all the confidence intervals do not reach out 80 seconds and the general average internal-distance of all documents is 6.5 second presented by the red line. We can see that the 7 minutes time gap is not a suitable time gap for our corpus. The suitable time gap should be shorter than 7 minutes.

In addition, we measured the external-distances of 30 seconds time gap and calculated their distribution in different intervals which are created from potential time gaps: [30s,60s) , [60s,120s), [120s,180s), [180s,240s), [240s,300s), [300s,420s), [420s,900s), [900s,). In which the left square bracket '[' denotes 'equal or longer than', the right round bracket ')' denotes 'shorter than' and the last interval denotes the external-distances which are 'equal or longer than 900 seconds'. Our suggestion is that if an interval covers more external-distances than others, it has much 'potential' to become a suitable time gap than others. Figure 3 shows the distribution of external-distances in each document. In average, externaldistances represent 39.73 %, 24.58%, 8.98%, 4.37%, 2.53%, 3.03%, 3.98% and 12.80% respectively for the given intervals. This means that if we increase the time gap from 30 seconds to 60 seconds, 39.73% of sessions will become part of other sessions because external-distances can not be shorter than 60 seconds. If we use 120 seconds time gap instead of 30 seconds time gap, 64,31 % (39.73% +24.58%) of sessions will be merged into other sessions and so on. From the above results, we can say that the [30s, 60s) and [60s,120s) intervals have much potential to contain the suitable time gap as it covers much more externaldistances(64,31%) than others. Moreover, we found that the range of externaldistances is very wide, from 30 seconds to 87 hours ( 3.6 days). This wide range is due to the fact that collected logs represent the students writing task over a period of two months with an allocated time slot in their schedule of two hours per week, but students could continue the writing outside the allocated time slot.

Summarizing the time-dimension analysis, we found that collaborative editing is usually separated into many editing sessions including single-author sessions and co-author sessions. The time distance between sessions has a very wide range (up to 87 hours in our case study). To split a document into sessions, a suitable time gap needs to be determined. And finally, editors have more editing activities in co-authors sessions than in single-author sessions, i.e. having more contributions when working collaboratively.

Time-position analysis

The analysis on time dimension gives us an overview of how collaborative editing happens over the time. It determines co-authors sessions in which the authors write closely together in time. However, it lacks the information about whether or not they write 'closely' in the same part of a document or 'separately' in different parts of it. A more detailed analysis in both time-position dimensions gives us a better understanding about how they write collaboratively.

As we can see in Figure 1, edits inside a session can be grouped into different 'clusters' depending on their time-position distances. In order to explain our time-position analysis we illustrate in Figure 4 the time-position view of the document with id 59e8f8d98e96ef7e2dc01eb2 from our data corpus. The figure illustrates the notions of session and cluster. A session begins with a vertical blue line and ends with a vertical red line. A cluster is presented as a rectangle filled with light-blue color. Edits are presented as orange and green dots depending on which authors they belong to (called orange author and green author). This document contains about 2500 characters (including white-spaces, empty lines) and was edited in total 6000 seconds by 2246 edit actions (including deletion, insertion). In the first 60 minutes, it was edited by the orange author only. Those edits are split into four single-author sessions, the longest time distance between them being about 16 minutes. In the next 25 minutes, the figure illustrates a co-authors session in which the document was edited collaboratively by two authors (the orange author and the green author). And in the last time slot, the figure illustrates a single-author session of the orange author. In this session, the orange author had edited in three different positions of the document with position-distance larger than 400 characters. Note that in Figure 4, for the simple presentation, we use large size windows of the form [time-gap, position-gap] = [300seconds, 400 characters] in order to reduce the number of sessions and clusters.

Edits in a single-author session can be re-edited by another author in another session. However, these two sessions are separated in time so that if conflicts happen, they are asynchronous conflicts. In this analysis, we focus on the cases that two or more authors edit closely together in both time and position. Having a closer look in the co-author session in Figure 4 which contains two clusters of edits, we can see that these two clusters have edits of both authors. In the bottom right cluster, there is a clear border between edits of two authors. In the top left cluster, besides three borders separating edits of different authors, there are several cases in which one author edited between two continuous edits of another author. We are interested in a characterization of conflicts in these cases where all involved edits are very close together in both time-position dimensions. We examined two cases in which conflicts potentially happen. The first case called border case refers to the switch-point between two adjacent editing-areas which belong to two different authors. Those editing-areas can contain one or more continuous edits. The second case called insertion case refers to the case in which one author tries to edit between two continuous edits of another author,i.e. one author tries to insert one or more edits into an editing-area of another author. In both cases, if the time-position distance between those continuous edits is small, conflicts have high potential to happen. Figure 5 presents the illustration of border case and insertion case. On the left side of Figure 5, X, Y and X' are three continuous edits (in time order) of two different authors in which [X, Y] form a border case. This border case can become a potential border conflict case if its time-position distance defined by the red rectangle is small. And if the adjacent edit X' happens between the positions of X and Y, it should be classified as a border conflict. A formal description of border conflict is presented in Definition 3.

On the right side of Figure 5

, [X 1 , Y 1 , Y 2 , Y 3 , X 2 , X
] is a sequence of edits in time order. It means that Y 1 , Y 2 , Y 3 happen between X 1 and X 2 and X happens right after X 2 . However, in position dimension, the order is different, which is

[Y 1 , X 1 , Y 2 , X , X 2 , Y 3]. Focusing on [X 1 , Y 2 , X 2
], we can see that they satisfy both time order and position order. In another way, Author-2 had inserted an edit into the time-position window formed by two continuous edits of Author-1. In the Figure 5, this time-position window is presented by the red rectangle created by X 1 and X 2 . If this window is small and the adjacent edit X' happens between the position of X 1 and X 2 ,we consider this case as an insertion conflict. A formal description of insertion conflict is presented in Definition 4. Definition 1. A sequence of edits [X 1 , X 2 , .., X n ] is a sequence of edits in time order with time-gap t if ∀i ∈ [1, n) : time(X i+1 ) > time(X i ) and time-distance(X i , X i+1 ) < t Definition 2. A sequence of edits [X 1 , X 2 , .., X n ] is a sequence of edits in position order with position-gap p if ∀i ∈ [1, n) : position(X i+1 ) > position(X i ) and position-distance(X i , X i+1 ) < p Definition 3. X is an edit of Author-1, Y is an edit of Author-2 and X' is an edit belonging to one of them. If [X, Y, X ] is a sequence of edits in time order with time-gap t and [X, X , Y ] is a sequence of edits in position order with position p, [X,Y] then form a border conflict within time-position window [t,p]. Definition 4. X 1 , X 2 are edits of Author-1, Y 1 , Y 2 , ...Y k are edits of Author-2 and X' is an edit belonging to one of them. (Y i ) + , i ∈ [1, k] is a sub-sequence of edits of Author-2 which has at least one edit. If [X 1 , Y 1 , Y 2 , ...Y k , X 2 , X ] is a sequence of edits in time order with time-gap t and ∃(Y i ) + so that [X 1 , (Y i ) + , X 2 ] or [ X 2 , (Y i ) + , X 1 ] form a sequence of edits in position order with position p, [X 1 , (Y i ) + , X 2 ] or [X 2 , (Y i ) + , X 1 ) then form an insertion conflict within time-position window [t,p].

We use a [30s, 10c] time-position window to run our experiments. As we explained in Section 3.1, the documents are separated into sessions using a 30 seconds time-gap. After that, all co-authors-sessions are checked for border cases and insertion cases. If these border cases and insertion cases satisfy the selected time-position window which is [30s, 10c], they become potential border conflicts and potential insertion conflicts. And if one of the involved authors edits right after in the potential-conflict-area, we consider that potential conflict as a conflict. The reason that we choose the [30s, 10c] time-position window is that it can allow three or more editing actions and can cover the position distance of two or three words. Table 3 characterizes conflicts for the [30s, 10c] time-position window.

The results in Table 3 show the high proportion of potential-conflicts that become conflicts: from 77.53% to 91.51% for border conflict and from 88.96% to 100% for insertion conflict with significance of CI99%. However, these two types of conflict happen very rarely. It is less than 9.66% for border conflict and less than 5.04% for insertion conflict. The case of potential border conflict that is not a border conflict corresponds to the case that the time-position window (the border) of two continuous edits of two authors is larger than the time-position window that we use to determine border conflict. And in the case of potential insertion conflict that is not an insertion conflict, two authors are editing in two different areas which are large enough in position. which people edit closely) are very likely to become conflicts: 77.53% to 91.51% of 'border cases' and 88.96% to 100% for 'insertion cases' result in 'conflict'. From above results, we suggest that collaborative editing tools (ShareLaTeX in this case) should consider to have an awareness mechanism for these two types of 'potential conflicts'.

Fig. 1 .

 1 Fig. 1. A document with two authors in time-position view

Fig. 2 .

 2 Fig. 2. Time gap = 420s, Average internal-distance with confidence interval CI90

Fig. 3 .

 3 Fig. 3. Time gap = 30s, External-distances distribution

Fig. 4 .

 4 Fig. 4. A real document(id=59e8f8d98e96ef7e2dc01eb2) presented in time-position view

Fig. 5 .

 5 Fig. 5. Illustration of Border case and Insertion case

Table 1 .

 1 Overview of the data: 108 documents

		Min Max Average Std
	No. of authors	2	4	2.69 0.87
	No. of edits	53 38,329	8,000 10,583
	Amount of edit 245 272,935	47,133 56,866

Table 2 .

 2 Documents segmentation by different maximum time gaps

				Time gaps
		15mn	7mn	5mn	2mn	1mn	30s
	Doc having CASs	84/108	82/108	80/108	77/108	76/108	75/108
	Proportion	77.77%	75.92%	74.07%	71.30%	70.00%	69.44%
	No. of CASs per doc
	Average	2.3	2.9	3.4	5.8	9.4	14.1
	Proportion	28.4%	24.4%	22.7%	17.5%	13.9%	10.7%
	Internal-distance
	SASs (Average)	9.61s	6.77s	5.89s	4.04s	2.87s	2.01s
	SASs (CI 99%)	[6.56-12.68] [5.74-7.80] [5.19-6.61] [3.73-4.35] [2.74-3.00] [1.97-2.07]
	CASs (Average)	4.25s	4.19s	4.15s	2.55s	1.78s	1.24s
	CASs (CI 99%)	[2.89-5.62] [2.69-5.70] [2.71-5.59] [1.97-3.14] [1.54-2.02] [1.13-1.35]
	Session length
	SASs (Average)	972s	647s	507s	226s	109s	51s
	CASs (Average)	3,314s	2,369s	1,953s	878s	350s	155s
	No. of edits
	SASs (Average)	213	170	146	94	60	39
	CASs (Average)	2,140	1,841	1,629	961	470	255
	CASs (Normalized)	893	787	704	429	214	118

Acknowledgement

We would like to thank Gérald Oster and Quentin Laporte-Chabasse for their valuable help for the collection of the ShareLaTeX logs.

Border conflict

Insertion conflict Beside the time-position window [30s, 10c], we also used a smaller window of [10s, 5c] and a larger window of [60s, 20c] to examine the border conflict and the insertion conflict. Results are presented in Table 4 and Table 5 respectively. We can see that the potential border conflict is affected by the time-position window more than the potential insertion conflict. The potential border conflict decreases from 5.7% to 3.07% with a smaller window and increases to 9.94% with a larger window. The potential insertion conflict has less effects by the size of time-position window. Furthermore, the smaller time-position window decreases the proportion of border conflict over potential border conflict while the larger window increases it. For the insertion conflict, the result is reversed. It means that the smaller the time-position window is, the more likely the potential insertion conflicts become real insertion conflicts.

Border conflict

Insertion conflict As an implication for design for our study we recommend that awareness mechanisms [START_REF] Dourish | Awareness and coordination in shared workspaces[END_REF] could be proposed for users when potential conflicts of both types border conflicts and insertion conflicts are detected. Users can get notified by means of a 'heat map' that visualizes the recency of editing activities [START_REF] Larsen-Ledet | Territorial functioning in collaborative writing[END_REF] when they write closely in time and position with other users, i.e. when the potential border conflicts and potential insertion conflicts occur.

Conclusion

In this paper we studied collaborative editing behavior in terms of collaboration patterns users adopt and in terms of a characterisation of conflicts, i.e. edits from different users that occur close in time and position in the document. By examining different 'maximum time gaps' from 30 seconds to 15 minutes we found that the time distance between sessions (i.e 'external-distance' ) has a very wide range (up to 87 hours in our case study). By evaluating the distribution of 'external-distance' of a very small time gap, we can determinate a suitable 'maximum time gap' to split editing activities into single-author sessions and coauthor sessions. We found that users are more productive in co-author sessions than in single-author sessions.

In a more detailed analysis of the co-authors-sessions, we use a [30 seconds, 10 characters] time-position window to examine the cases in which two authors edit closely together in both time and position. We focus on two cases which potentially result in conflict: 'border case' and 'insertion case'. 'Border case' refers the cases in which two different authors edit in the border of two close editing areas that belong to them. And 'insertion cases' refers to the cases in which one author does some edits between two continuous edits of another author. The results show that these two cases happen rarely: up to 5.04% for 'insertion cases' and up to 9.66% for 'border cases'. It means that people rarely edit closely in both time and position. However, these cases (i.e. the case in


Weihai Yu
email: weihai.yu@uit.no

Claudia-Lavinia Ignat

Conflict-Free Replicated Relations for Multi-Synchronous Database Management at Edge

Keywords: CRDT, relational database, eventual consistency, integrity constraints

In a cloud-edge environment, edge devices may not always be connected to the network. Still, applications may need to access the data on edge devices even when they are not connected. With support for multi-synchronous access, data on an edge device are kept synchronous with the data in the cloud as long as the device is online. When the device is offline, the application can still access the data on the device, asynchronously with concurrent data updates either in the cloud or on other edge devices. Conflict-free Replicated Data Types (CRDTs) emerged as a technology for multi-synchronous data access. CRDTs guarantee that when all sites have applied the same set of updates, the replicated data converge. However, CRDTs have not been successfully applied to relational databases (RDBs) for multi-synchronous access. In this paper, we present Conflict-free Replicated Relations (CRRs) that apply CRDTs to RDBs for support of multi-synchronous data access. With CRR, existing RDB applications, with very little modification, can be enhanced with multi-synchronous access. We also present a prototype implementation of CRR with some preliminary performance results.

I. INTRODUCTION

The cloud technology makes data globally shareable and accessible, as long as the end-user's device is connected to the network. When the user's device is not connected, the data become inaccessible.

There are scenarios where the users may want to access their data even when their devices are off-line. The researchers may want to access their research data when they are at field work without any network facility. The project managers and engineers may want to access project data when they are under extreme conditions such as inside a tunnel or in the ocean. People may want to use their personal applications during flight, in a foreign country or during mountain hiking.

In a cloud-edge environment, the cloud consists of servers with powerful computation and reliable data storage capacities. The edge consists of the devices outside the operation domain of the cloud. The above-mentioned scenarios suggest multisynchronous access of data on edge devices. That is, there are two modes of accessing data on edge devices: asynchronous mode-the user can always access (read and write) the data on the device, even when the device is off-line, and synchronous mode-the data on the device is kept synchronous with the data stored in the cloud, as long as the device is online.

One of the main challenges of multi-synchronous data access is the limitation of a networked system stated in the CAP theorem [START_REF] Fox | Harvest, yield and scalable tolerant systems[END_REF][START_REF] Gilbert | Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services[END_REF]: it is impossible to simultaneously ensure all three desirable properties, namely (C) consistency equivalent to a single up-to-date copy of data, (A) availability of the data for update and (P) tolerance to network partition.

CRDTs, or Conflict-free Replicated Data Types, emerged to address the CAP challenges [START_REF] Shapiro | Conflict-free replicated data types[END_REF]. With CRDT, a site updates its local replica without coordination with other sites. The states of replicas converge when they have applied the same set of updates (referred to as strong eventual consistency in [START_REF] Shapiro | Conflict-free replicated data types[END_REF]). CRDTs have been adopted in the construction of distributed key-value stores [START_REF] Brown | Riak DT map: a composable, convergent replicated dictionary[END_REF], collaborative editors [START_REF] Oster | Data consistency for P2P collaborative editing[END_REF]- [START_REF] Nicolas | MUTE: A peer-to-peer web-based real-time collaborative editor[END_REF] and localfirst software [START_REF] Kleppmann | A conflict-free replicated JSON datatype[END_REF][START_REF] Kleppmann | Local-first software: you own your data, in spite of the cloud[END_REF]. All these bear the similar goal as multisynchronous data access. There has also been active research on CRDT-based transaction processing [START_REF] Li | Making geo-replicated systems fast as possible, consistent when necessary[END_REF] mainly to achieve low latency for geo-replicated data stores.

Despite the above success stories, CRDTs have not been applied to multi-synchronous access of data stored in relational databases (RDBs). To support multi-synchronous data access, the application typically has to be implemented using specific key-value stores built with CRDTs. These key-value stores do not support some important RDB features, including advanced queries and integrity constraints. Consequently, the large number of existing applications that use RDBs have to be re-implemented for multi-synchronous access.

In this paper, we propose Conflict-Free Replicated Relation (CRR) for multi-synchronous access to RDB data. Our contributions include:

• A set CRDT for RDBs. One of the hurdles for adopting CRDTs to RDBs is that there is no appropriate set CRDT for RDBs (Section III-A). We present CLSet CRDT (causal-length set) that is particularly suitable for RDBs (Section III-C). • An augmentation of existing RDB schema with CRR in a two-layer system (Section IV). With CRR, we are able to enhance existing RDB applications with very little modification.

• Automatic handling of integrity violations at merge (Section V). • A prototype implementation (Section VI). The implementation is independent of the underlying database management system (DBMS). This allows different devices of the same application to deploy different DBMSs. This is particularly useful in a cloud-edge environment that is inherently heterogeneous. We also report some initial performance result of the prototype. The paper is organized as follows. Section II gives an overview of CRR, together with the system model our work applies to. Section III reviews the background of CRDT and presents the CLSet CRDT that is an underlying CRDT of CRR. Section IV describes CRR in detail. Section VI presents an implementation of CRR and some preliminary performance results. Section VII discusses related work. Section VIII concludes.

II. OVERVIEW OF CRR

The RDB supporting CRR consists of two layers: an Application Relation (AR) layer and a Conflict-free Replicated Relation (CRR) layer (see Figure 1). The AR layer presents the same RDB schema and API as a conventional RDB system. Application programs interact with the database at the AR layer. The CRR layer supports conflict-free replication of relations.

The AR-layer database schema has an augmented CRR schema ˜ . A site maintains both an instance of and an instance ˜ of ˜ . A query q on is performed directly on . A request for update u on is translated into ũ and performed on the augmented relation instance ˜ . The update is later propagated to remote sites through an anti-entropy protocol. Every update in ˜ , either as the execution of a local update ũ( ˜ ) or as the merge with a remote update ũ( ˜ ), refreshes .

CRR has the property that when both sites and have applied the same set of updates, the relation instances at the two sites are equivalent, i.e. = and ˜ = ˜ .

The two-layered system also maintains the integrity constraints defined at the AR layer. Any violation of integrity constraint is caught at the AR layer. A local update of ˜ and refresh of are wrapped in an atomic transaction: a violation would cause the rollback of the transaction. A merge at ˜ and a refresh at is also wrapped in a transaction: a failed merge would cause some compensation updates.

An application developer does not need to care about how the CRR layer works. Little change is needed for an existing RDB application to function with CRR support.

We use different CRDTs for CRRs. Since a relation instance is a set of tuples or rows, we use a set CRDT for relation instances. We design a new set CRDT (Section III), as none of existing set CRDTs are suitable for CRRs (Section III-A). A row consists of a number of attributes. Each of the attributes can be individually updated. We use the LWW (last-write wins) register CRDT [START_REF] Shapiro | A comprehensive study of convergent and commutative replicated data types[END_REF][START_REF] Johnson | The maintamance of duplicated databases[END_REF] for attributes in general cases. Since LWW registers may lose some concurrent updates, we use the counter CRDT [START_REF] Shapiro | Conflict-free replicated data types[END_REF] for numeric attributes with additive updates.

System Model

A distributed system consists of sites with globally unique identifiers. Sites do not share memory. They maintain durable states. Sites may crash, but will eventually recover to the durable state at the time of the last crash.

A site can send messages to any other site in the system through an asynchronous and unreliable network. There is no upper bound on message delay. The network may discard, reorder or duplicate messages, but it cannot corrupt messages. Through re-sending, messages will eventually be delivered. The implication is that there can be network partitions, but disconnected sites will eventually get connected.

III. A SET CRDT FOR CRRS

In this section, we first present a background of CRDTs. As a relation instance is a set of tuples, CRR needs an appropriate set CRDT as a building block. We present limitations of existing set CRDTs for RDBs. We then describe a new set CRDT that addresses the limitations.

A. CRDT Background

A CRDT is a data abstraction specifically designed for data replicated at different sites. A site queries and updates its local replica without coordination with other sites. The data is always available for update, but the data states at different sites may diverge. From time to time, the sites send their updates asynchronously to other sites with an anti-entropy protocol. To apply the updates made at the other sites, a site merges the received updates with its local replica. A CRDT has the property that when all sites have applied the same set of updates, the replicas converge.

There are two families of CRDT approaches, namely operation-based and state-based [START_REF] Shapiro | Conflict-free replicated data types[END_REF]. Our work is based on state-based CRDTs, where a message for updates consists of the data state of a replica in its entirety. A site applies the updates by merging its local state with the state in the received message. The possible states of a state-based CRDT must form a join-semilattice [START_REF] Garg | Introduction to Lattice Theory with Computer Science Applications[END_REF], which implies convergence. Briefly, the states form a join-semilattice if they are partially ordered with and a join of any two states (that gives the least upper bound of the two states) always exists. State updates must be inflationary. That is, the new state supersedes the old one in . The merge of two states is the result of a join. Figure 2 (left) shows GSet, a state-based CRDT for growonly sets (or add-only set [START_REF] Shapiro | Conflict-free replicated data types[END_REF]), where is a set of possible elements, def = ⊆, def = ∪, insert is a mutator (update operation) and in is a query. Obviously, an update through insert( , ) is an inflation, because ⊆ { } ∪ . Figure 2 (right) shows GSet( ) GSet is an example of an anonymous CRDT, since its operations are not specific to the sites that perform the operations. Two concurrent executions of the same mutation, such as insert({}, ), fulfill the same purpose.

def = P ( ) insert( , ) def = { } ∪ insert ( , ) def = { } if ∉ {} otherwise def = ∪ in( , ) def = ∈ { , , } { , } { , } { , } { } { } { } {}
Using state-based CRDTs, as originally presented [START_REF] Shapiro | Conflict-free replicated data types[END_REF], is costly in practice, because states in their entirety are sent as messages. Delta-state CRDTs address this issue by only sending join-irreducible states [START_REF] Almeida | Delta state replicated data types[END_REF][START_REF] Enes | Efficient Synchronization of State-based CRDTs[END_REF]. Basically, join-irreducible states are elementary states: every state in the join-semilattice can be represented as a join of some join-irreducible state(s). In Figure 2, insert is a delta-mutator that returns joinirreducible states which are singleton sets (boxed in the Hasse diagram).

Since a relation instance is a set of tuples, the basic building block of CRR is a set CRDT, or specifically, a delta-state set CRDT.

A CRDT for general-purpose sets with both insertion and deletion updates can be designed as a causal CRDT [START_REF] Almeida | Delta state replicated data types[END_REF] such as ORSet (observed-remove set [START_REF] Shapiro | A comprehensive study of convergent and commutative replicated data types[END_REF][START_REF] Bieniusa | A optimized conflict-free replicated set[END_REF][START_REF] Meiklejohn | Lasp: a language for distributed, coordination-free programming[END_REF]). Basically, every element is associated with at least a causal context as meta data. A causal context is a set of event identifiers (typically a pair of a site identifier and a site-specific sequence number). An insertion or deletion is achieved with inflation of the associated causal context. Using causal contexts, we are able to tell explicitly which insertions of an element have been later deleted. However, maintaining causal contexts for every element can be costly, even though it is possible to compress causal contexts into vector states, for instance under causal consistency. Causal CRDTs are not suitable for RDBs, which generally do not allow multi-valued attributes such as causal contexts.

In the following, we present a new set CRDT, based on the abstraction of causal length. It is a specialization of our earlier work on generic undo support for state-based CRDTs [START_REF] Yu | A generic undo support for state-based CRDTs[END_REF].

B. Causal length

The key issue that a general-purpose set CRDT must address is how to identify the causality between the different insertion and deletion updates. We achieve this with the abstraction of causal length, which is based on two observations. First, the insertions and deletions of a given element occur in turns, one causally dependent on the other. A deletion is an

Site

Site Site

{} 0 {} 0 {} 0 1 : insert( 0 , ) { } 1 1 : insert( 0 , ) { } 1 { } 2 { } 1 2 : delete( 2 , ) {} 3 2 : delete( 1 , ) {} 2 {} 3 {} 4 2 : delete( 1 , ) {} 2 3 : insert( 4 , ) { } 5 { } 6 {} 3 { } 4 4 : delete( 4 , ) {} 5
Fig. 3. A scenario of concurrent set updates inverse of the last insertion it sees. Similarly, an insertion is an inversion of the last deletion it sees (or none, if the element has never been inserted).

Second, two concurrent executions of the same mutation of an anonymous CRDT (Section III-A) fulfill the same purpose and therefore are regarded as the same update. Seeing one means seeing both (such as the concurrent insertions of the same element in GSet). Two concurrent inverses of the same update are also regarded as the same one.

Figure 3 shows a scenario where three sites , and concurrently insert and delete element . When sites and concurrently insert for the first time, with updates 1 and 1 , they achieve the same effect. Seeing either one of the updates is the same as seeing both. Consequently, states 1 , 2 , 1 and 1 are equivalent as far as the insertion of is concerned.

Following the same logic, the concurrent deletions on these equivalent states (with respect to the first insertion of ) are also regarded as achieving the same effect. Seeing one of them is the same as seeing all. Therefore, states 3 , 2 , 3 , 4 , 2 and 3 are equivalent with regard to the deletion of . Now we present the states of element as the equivalence classes of the updates, as shown in the second column of Table I. The concurrent updates that see equivalent states and achieve the same effect are in the same equivalence classes. The columns and ˜ in Table I correspond to the states of a tuple (as an element of a set) in relation instances in the AR and CRR layers (Section II).

When a site makes a new local update, it adds to its state a new equivalence class that contains only the new update. For example, when site inserts element at state 0 with update 1 , it adds a new equivalence class { 1 } and the new state 1 becomes {{ 1 }}. When site then deletes the element with update 2 , it adds a new equivalence class { 2 } and the new

{ { 1 , 1 }, { 2 , 2 , 2 }, { 3 }, { 4 } } { , 4 } { } state 2 becomes {{ 1 }, { 2 }}.
The merge of two states is handled as the union of the equivalence classes. For example, when states 1 and 2 merge, the new state 3

becomes {{ 1 } ∪ { 1 }, { 2 }} = {{ 1 , 1 }, { 2 }}.
Now, observe that whether element is in the set is determined by the number of equivalence classes, rather than the specific updates contained in the equivalence classes. For example, as there is one equivalence class in state 1 , the element is in the set. As there are two equivalence classes in states 2 , 3 and 4 , the element is not in the set.

Due to the last observation, we can represent the states of an element with a single number, the number of equivalence classes. We call that number the causal length of the element. An element is in the set when its causal length is an odd number. The element is not in the set when its causal length is an even number. As shown in Table I, a CRR-layer relation ˜ augments an AR-later relation with causal lengths.

C. CLSet CRDT

Figure 4 shows the CLSet CRDT. The states are a partial function : ↩→ N, meaning that when is not in the domain of , ( ) = 0 (0 is the bottom element of N, i.e. ⊥ N = 0). Using partial function conveniently simplifies the specification of insert, and in. Without explicit initialization, the causal length of any unknown element is 0. In the figure, insert and delete are the delta-counterparts of insert and delete respectively.

An element is in the set when its causal length is an odd number. A local insertion has effect only when the element is not in the set. Similarly, a local deletion has effect only when the element is actually in the set. A local insertion or deletion

CLSet( ) def = ↩→ N insert( , ) def = { ↦ → ( ) + 1} if even ( ) if odd ( ) insert ( , ) def = { ↦ → ( ) + 1} if even ( ) {} if odd ( ) delete( , ) def = if even ( ) { ↦ → ( ) + 1} if odd ( ) delete ( , ) def = {} if even ( ) { ↦ → ( ) + 1} if odd ( ) ( ) ( ) def = max ( ), ( ) in( , ) def = odd ( ) Fig. 4. CLSet CRDT
simply increments the causal length of the element by one. For every element in and/or , the new causal length of after merging and is the maximum of the causal lengths of in and .

IV. CONFLICT-FREE REPLICATED RELATIONS In this section we describe the design of the CRR layer. We focus particularly on the handling of updates.

Without loss of generality, we represent the schema of an application-layer relation with ( , ), where is the relation name, is the primary key and is a non-key attribute. For a relation instance of ( , ), we use ( ) for the projection . We also use ( ) for the row identified with key , and ( , ) for row ( ) whose attribute has value .

A. Augmentation and caching

In a two-layer system as highlighted in Section II, we augment an AR-layer relation schema ( , ) to a CRR-layer schema ˜ ( , , , ) where is the update timestamps of attribute and is the causal lengths of rows. Basically, ˜ ( , ) implements a CLSet CRDT (Section III-C) where the rows identified by keys are elements, and ˜ ( , , ) implements the LWW-register CRDT [START_REF] Shapiro | A comprehensive study of convergent and commutative replicated data types[END_REF][START_REF] Johnson | The maintamance of duplicated databases[END_REF] where an attribute of each row is a register.

We use hybrid logical clock [START_REF] Kulkarni | Logical physical clocks[END_REF] for timestamps, which is UTC time compatible and for two events 1 and 2 with clocks

1 and 2 , 1 < 2 if 1 happens before 2 .
For a relation instance ˜ of an augmented schema ˜ , the relation instance of the AR-layer schema is a cache of ˜ .

For a relation operation op on , we use op as the corresponding operation on ˜ . For example, we use ∈ on ˜ to detect whether a row exists in . That is ˜ ( ) ∈ ˜ ⇔ ( ) ∈ .

According to CLSet (Figure 4), we define ∈ and ∉ as

˜ ( ) ∈ ˜ def = ˜ ( ) ∈ ˜ ∧ odd ( ˜ ( )) ˜ ( ) ∉ ˜ def = ˜ ( ) ∉ ˜ ∨ even ( ˜ ( ))
For an update operation u , , on , we first perform ũ( ˜ , , , , ) on ˜ . This results in the new instance ˜ and row ˜ ( ) = ( , , , ). We then refresh the cache as the following:

• Insert ( , ) into if ˜ ( ) ∈ ˜ and ( ) ∉ . • Delete ( ) from if ˜ ( ) ∉ ˜ and ( ) ∈ . • Update ( ) with ( , ) if ˜ ( ) ∈ ˜ , ( ) ∈ and
( ) ≠ . All AR-layer queries are performed on the cached instance without any involvement of the CRR layer. The following subsections describe how the CRR layer handles the different update operations.

B. Update operations

The CRR layer handles a local row insertion as below:

insert ˜ , ( , ) def =              insert ˜ , ( , , now, 1) if ˜ ( ) ∉ ˜ update ˜ , , ( , now, ( ˜ ( )) + 1) if ˜ ( ) ∈ ˜ ∧ ˜ ( ) ∉ ˜ skip otherwise
A row insertion attempts to achieve two effects: to insert row ( ) into and to assign value to attribute of ( ). If ( ) has never been inserted, we simply insert ( , , now, 1) into ˜ . If ( ) has been inserted but later deleted, we re-inserted it with the causal length incremented by 1. Otherwise, there is already a row ( ) in , thus we do nothing.

There could be an alternative handling in the last case. Instead of doing nothing, we could update the value of attribute with . We choose to do nothing, because this behavior is in line with the SQL convention.

The CRR layer handles a local row deletion as below:

delete( ˜ , ) def = update ˜ , , (-, ( ˜ ( )) + 1) if ˜ ( ) ∈ ˜ skip otherwise
If there is a row ( ) in , we increment the causal length by 1. We do nothing otherwise. In the expression, we use the "-" sign for the irrelevant attributes.

The CRR layer handles a local attribute update as below:

update( ˜ , , ) def = update ˜ , , ( , now, ( ˜ ( ))) if ˜ ( ) ∈ ˜ skip otherwise
If there is a row ( ) in , we update the attribute and set a new timestamp. We do nothing otherwise.

When the CRR layer handles one of the above update operations and results in a new row ˜ ( ) in ˜ (either inserted or updated), the relation instance with a single row { ˜ ( )} is a join-irreducible state in the possible instances of schema ˜ . The CRR layer later sends { ˜ ( )} to the remote sites in the anti-entropy protocol.

A site merges a received join-irreducible state {( , , , )} with its current state ˜ using a join:

˜ {( , , , )} def =              insert ˜ , ( , , , ) if ˜ ( ) ∉ ˜ update ˜ , , ( , max( ( ˜ ), ), if ( ˜ ) < max( ( ˜ ), )) ∨ ( ˜ ) < skip otherwise
If there is no ˜ ( ) in ˜ , we insert the received row into ˜ . If the received row has either a longer causal length or a newer timestamp, we update ˜ with the received row. Otherwise, we keep ˜ unchanged. Notice that a newer update on a row that is concurrently deleted is still updated. The update is therefore not lost. The row will have the latest updated attribute value when the row deletion is later undone.

It is easy to verify that a new relation instance, resulted either from one of the local updates or from a merge with a received state, is always an inflation of the current relation instance regarding causal lengths and timestamps.

C. Counters

The general handling of attribute updates described earlier in Section IV-B is based on the LWW-register CRDT. This is not ideal, because the effect of some concurrent updates may get lost. For some numeric attributes, we can use the counter CRDT [START_REF] Shapiro | Conflict-free replicated data types[END_REF] to handle updates as increments and decrements.

We make a special (meta) relation Ct for counter CRDTs at the CRR layer: Ct(Rel, Attr, Key, Sid, Icr, Dcr), where (Rel, Attr, Key, Sid) is a candidate key of Ct.

The attribute Rel is for relation names, Attr for names of numeric attributes and Key for primary key values. For an ARlayer relation ( , ), and respectively the CRR-layer relation ˜ ( , , , ), where is a primary key and is a numeric attribute, ( , , ) of refers to the numeric value ( ) (and ˜ ( ) ). The attribute Sid is for site identifiers. Our system model requires that sites are uniquely identified (Section II). The counter CRDT is named (as opposed to anonymous, described in Section III-A), meaning that a site can only update its specific part of the data structure.

The attributes Icr and Dcr are for the increment and decrement of numeric attributes from their initial values, set by given sites.

We set the initial value of a numeric attribute to: the default value, if the attribute is defined with a default value; the lower bound, if there is an integrity constraint that specifies a lower bound of the attribute; 0 otherwise.

If the initial value of the numeric attribute of an AR-layer relation ( , ) is 0 , we can calculate the current value of ( ) as 0 + sum(Icr) -sum(Dcr), as an aggregation on the rows identified by ( , , ) in the current instance of Ct.

We can translate a local update of a numeric attribute into an increment or decrement operation. If the current value of the attribute is and the new updated value is , the update is an increment ofif > , or a decrement ofif < . Site with the current instance handles a local increment or decrement operation as below: ( ,,,,( ,0)) otherwise dec ( ˜ , , , ,,,,( ,+ ) if ct( , , , , , ) ∈ ct insert ct, ( , , , , (0, )) otherwise If it is the first time the site updates the attribute, we insert a new row into Ct. Otherwise, we set the new increment or decrement value accordingly. Note that > 0 and the updates in Ct are always inflationary. The relation consisting of a single row of the update is a join-irreducible state in the possible instance of Ct and is later sent to remote sites.

inc ( ˜ , , , ) def = update ct, , , , , ( + , ) if ct( , , , , , ) ∈ ct insert ct,
) def = update ct,
A site with the current Ct instance ct merges a received join-irreducible state with a join: ,( ,,,,,))

ct {( , , , , , )} def =              insert(ct
if ct( , , , ) ∉ ct update ct, , , , , if ( , , , , , ) ∈ ct (max( , ), max( , )) ∧ ( < ∨ < ) skip otherwise

If the site has not seen any update from site , we insert the received row into ct. If it has applied some update from and the received update makes an inflation, we update the corresponding row for site . Otherwise, it has already applied a later update from and we keep ct unchanged.

Notice that turning an update into an increment or decrement might not always be an appropriate way to handle an update. For example, two sites may concurrently update the temperature measurement from 11 • to 15 • . Increasing the value twice leads to a wrong value 19 • . In such situations, it is more appropriate to handle updates as a LWW-register.

V. INTEGRITY CONSTRAINTS Applications define integrity constraints at AR layer. A DBMS detects violations of integrity constraints when we refresh the cached AR-layer relations.

We perform updates on a CRR-layer instance ˜ and the corresponding refresh of an AR-layer instance in a single atomic transaction. A violation of any integrity constraint causes the entire transaction to be rolled back. Therefore a local update that violates any integrity constraint has no effect on either ˜ or .

When a site detects a violation at merge, it may perform an undo on an offending update. We first describe how to perform an undo. Then, we present certain rules to decide which updates to undo. The purpose of making such decisions is to avoid undesirable effects. In more general cases not described below, we simply undo the incoming updates that cause constraint violations, although this may result in unnecessary undo of too many updates.

A. Undoing an update

For delta-state CRDTs, a site sends join-irreducible states as remote updates. In our case, a remote update is a single row (or more strictly, a relation instance containing the row).

To undo a row insertion or deletion, we simply increment the causal length by one.

To undo an attribute update augmented with the LWWregister CRDT, we set the attribute with the old value, using the current clock value as the timestamp. In order to be able to generate the undo update, the message of an attribute update also includes the old value of the attribute.

We handle undo of counter updates with more care, because counter updates are not idempotent and multiple sites may perform the same inverse operation concurrently. As a result, the same increment (or decrement) might be mistakenly reversed multiple times.

To address this problem, we create a new (meta) relation for counter undo: CtU(Rel, Attr, Key, Sid, ).

Similar to relation Ct (Section IV-C), attributes Rel and Attr are for the names of the relations and the counter attributes, and attributes Key and Sid are for key values and sites that originated the update.

is the timestamp of the original counter update. A row ( , , , , ) in CtU uniquely identifies a counter update.

A message for a counter update contains the timestamp and the delta of the update, in addition to the join-irreducible state of the update. The timestamp helps us uniquely identify the update. The delta helps us generate the inverse update.

Relation CtU works as a GSet (Figure 2). When a site undoes a counter update, it inserts a row identifying the update into CtU. When a site receives an undo message, it performs the undo only when the row of the update is not in CtU.

B. Uniqueness

An application may set a uniqueness constraint on an attribute (or a set of attributes). For instance, the email address of a registered user must be unique. Two concurrent updates may violate a uniqueness constraint, though none of them violates the constraint locally.

When we detect the violation of a uniqueness constraint at the time of merge, we decide a winning update and undo the losing one. Following the common sequential cases, an earlier update wins. That is, the update with a smaller timestamp wins.

As violations of uniqueness constraints occur only for row insertions and attribute updates (as LWW-registers), the only possible undo operations are row deletions and attribute updates (as LWW-registers).

C. Reference integrity

A reference-integrity constraint may be violated due to concurrent updates of a reference and the referenced row. Suppose relation 1 ( 1 , ) has a foreign key referencing to 2 ( 2 , ). Assume two sites 1 and 2 have rows 2 1 ( 2 ) and 2 2 ( 2 ) respectively. Site 1 inserts 1 1 ( 1 , 2 ) and site 2 concurrently deletes 2 2 ( 2 ). The sites will fail to merge the concurrent remote updates, because they violate the referenceintegrity constraint.

Obviously, both sites undoing the incoming remote update is undesirable. We choose to undo the updates that add references. The updates are likely row insertions. One reason of this choice is that handling uniqueness violations often leads to row deletions (Section V-B). If a row deletion as undo for a uniqueness violation conflicts with an update that adds a reference, undoing the row deletion will violate the uniqueness constraint again, resulting in an endless cycle of undo updates.

Notice that two seemingly concurrent updates may not be truly concurrent. One site might have already indirectly seen the effect of the remote update, reflected as a longer causal length. Two updates are truly concurrent only when the referenced rows at the two sites have the same causal length at the time of the concurrent updates. When the two updates are not truly concurrent, a merge of an incoming update at one of the sites would have no effect. In the above example, the merge of the deletion at site 2 has no effect if

( ˜ 2 1 ( 2 )) > ( ˜ 2 2 ( 2 )).

D. Numeric constraints

An application may set numeric constraints, such as a lower bound of the balance of a bank account. A set of concurrent updates may together violate a numeric constraint, though the individual local updates do not.

When the merge of an incoming update fails due to a violation of a numeric constraint, we undo the latest update (or updates) of the numeric attribute. This, however, may undo too many updates than necessary. We have not yet investigated how to avoid undoing too many updates that violate a numeric constraint.

VI. IMPLEMENTATION

We have implemented a CRR prototype, Crecto, on top of Ecto 1 , a data mapping library for Elixir 2 .

For every application-defined database table, we generate a CRR-augmented table. We also generate two additional tables in Crecto, Ct for counters (Section IV-C) and CtU for counter undo (Section V-A).

For every table, Ecto automatically generates a primary-key attribute which defaults to an auto-increment integer. Instead, we enforce the primary keys to be UUIDs to avoid collision of key values generated at different sites.

In the CRR-augmented tables, every attribute has an associated timestamp for the last update. We implemented the hybrid logic clock [START_REF] Kulkarni | Logical physical clocks[END_REF] as timestamps.

1 https://github/elixir-ecto/ecto 2 https://elixir-lang.org

In Ecto, applications interact with databases through a single Repo module. This allows us to localize our implementation efforts to a Crecto.Repo module on top of the Ecto.Repo module.

Since queries do not involve any CRR-layer relations, Crecto.Repo forwards all queries unchanged to Ecto.Repo.

A local update includes first update(s) of CRR-layer relation(s) and then a refresh of the cached relation at AR layer. All these are wrapped in a single atomic transaction. Any constraint violation is caught at cache refreshment, which causes the transaction to be rolled back.

A site keeps outgoing messages in a queue. When the site is online, it sends the messages in the queue to remote sites. The queue is stored in a file so that it survives system crashes.

A merge of an incoming update includes also first update(s) of CRR-layer relation(s) and then a refresh of the cached relation at AR layer. These are also wrapped in an atomic transaction. Again, any constraint violation is caught at cache refreshment, which causes the transaction to be rolled back. When this happens, we undo an offending update (Section V). If we undo the incoming update, we generate an undo update, insert an entry in CtU if the update is a counter increment or decrement, and send the generated undo update to remote sites. If we undo an update that has already been performed locally, we re-merge the incoming update after the undo of the already performed update.

For an incoming remote update, we can generate the undo update using the additional information attached in the message (Section V-A). For an already performed row insertion or deletion, we can generate the undo update with an incremental of the causal length. For an already performed attribute update, we can generate the undo update in one of two ways. We can use the messages stored in the queue. Or we can simply wait. An undo update will eventually arrive, because this update will violate the same constraint at a remote site.

Performance

To study the performance of CRR, we implemented an advertisement-counter application [START_REF] Meiklejohn | Lasp: a language for distributed, coordination-free programming[END_REF][START_REF] Meiklejohn | Practical evaluation of the lasp programming model at large scale: an experience report[END_REF] in Crecto. Advertisements are displayed on edge devices (such as mobile phones) according to some vendor contract, even when the devices are not online. The local counters of displayed advertisements are merged upstream in the cloud when the devices are online. An advertisement is disabled when it has reached a certain level of impression (total displayed number).

We are mainly interested in the latency of database updates, which is primarily dependent on disk IOs. Table II shows the latency measured at a Lenovo ThinkPad T540p laptop, configured with an Intel quad-core i7-4710MQ CPU, 16 GiB Ram, 512 GiB SSD, running Linux 5.4. The Crecto prototype is implemented on Ecto 3.2 in Elixir 1.9.4 OTP 22, deployed with PostgreSQL3 12.1.

To understand the extra overhead of multi-synchronous support, we measured the latency of the updates of the application implemented in both Ecto and Crecto. Table II only gives an approximate indication, since the latency depends on the load of the system as well as the sizes of the tables. For example, the measured latency of counter updates actually varied from 1.1ms to 3.8ms to get an average of 2.8ms. Notice also that whether an update is wrapped in a transaction also makes a difference. We thus include the measured latency of Ecto updates that are either included (In-tx) or not included (Notx) in transactions.

We expected that the latency of the updates in Crecto would be 2-3 times higher than that of the corresponding updates in Ecto, since handling an update request involves two or three updates in the two layers. The measured latency is less than that. One explanation is that several updates may share some common data-mapping overhead.

VII. RELATED WORK

CRDTs for multi-synchronous data access

One important feature of local-first software [START_REF] Kleppmann | Local-first software: you own your data, in spite of the cloud[END_REF] is multisynchronous data access. In particular, data should be first stored on user devices and be always immediately accessible. Current prototypes of local-first software reported in [START_REF] Kleppmann | Local-first software: you own your data, in spite of the cloud[END_REF] are implemented using JSON CRDTs [START_REF] Kleppmann | A conflict-free replicated JSON datatype[END_REF]. There is no support for RDB features such as SQL-like queries and integrity constraints.

The work presented in [START_REF] Mealha | Data replication on the cloud/edge[END_REF] aims at low latency of data access at edge. It uses hybrid logical clock [START_REF] Kulkarni | Logical physical clocks[END_REF] to detect concurrent operations and operational transformation [START_REF] Ellis | Concurrency control in groupware systems[END_REF] to resolve conflicts. In particular, it resolves conflicting attribute updates as LWW-registers. It requires a central server in the cloud to disseminate operations and the data model is restricted to the MangoDB4 model.

Lasp [START_REF] Meiklejohn | Lasp: a language for distributed, coordination-free programming[END_REF][START_REF] Meiklejohn | Practical evaluation of the lasp programming model at large scale: an experience report[END_REF] is a programming model for large-scale distributed programming. One of its key features is to allow local copies of replicated state to change during periods without network connectivity. It is based on the ORSet CRDT [START_REF] Shapiro | A comprehensive study of convergent and commutative replicated data types[END_REF] and provides functional programming primitives such as map, filter, product and union.

CRDTs for geo-replicated data stores

Researchers have applied CRDTs to achieve low latency for data access in geo-replicated databases. Unlike multisynchronous access, such systems require all or a quorum of the replicas to be available.

RedBlue consistency [START_REF] Li | Making geo-replicated systems fast as possible, consistent when necessary[END_REF] allows eventual consistency for blue operations and guarantees strong consistency for red operations. In particular, it applies CRDTs for blue operations and globally serializes red operations. [START_REF] Balegas | Extending eventually consistent cloud databases for enforcing numeric invariants[END_REF] presents an approach to support global boundary constraints for counter CRDTs. For a bounded counter, the "rights" to increment and decrement the counter value are allocated to the replicas. A replica can only update the counter using its allocated right. It can "borrow" rights from other replicas when its allocated right is insufficient. This approach requires that replicas with sufficient rights be available in order to successfully perform an update.

Our work does not support global transactions [START_REF] Li | Making geo-replicated systems fast as possible, consistent when necessary[END_REF] or global boundary constraints [START_REF] Balegas | Extending eventually consistent cloud databases for enforcing numeric invariants[END_REF]. It is known [START_REF] Bailis | Coordination avoidance in database systems[END_REF] that it is impossible to support certain global constraints without synchronization and coordination among different sites. We repair asynchronously temporary violation of global constraints through undo. Support of undo for row insertion and deletion in CRR is straightforward, as CLSet (Section III-C) is a specialization of a generic undo support for CRDTs [START_REF] Yu | A generic undo support for state-based CRDTs[END_REF].

AntidoteSQL [START_REF] Lopes | Antidote SQL: relaxed when possible, strict when necessary[END_REF] provides a SQL interface to a georeplicated key-value store that adopts CRDT approaches including those reported in [START_REF] Li | Making geo-replicated systems fast as possible, consistent when necessary[END_REF][START_REF] Balegas | Extending eventually consistent cloud databases for enforcing numeric invariants[END_REF]. An application can declare certain rules for resolving conflicting updates. Similar to our work, an application can choose between LWW-register and counter CRDTs for conflicting attribute updates. In Anti-doteSQL, a deleted record is associated with a "deleted" flag, hence excluding the possibility for the record to be inserted back again. As AntidoteSQL is built on a key-value store, it does not benefit from the maturity of the RDB industry.

Set CRDTs

The CLSet CRDT (Section III) is based on our earlier work on undo support for state-based CRDTs [START_REF] Yu | A generic undo support for state-based CRDTs[END_REF]. Obviously, deletion (insertion) of an element can be regarded as an undo of a previous insertion (deletion) of the element.

As discussed in Section III-A, there exist CRDTs for general-purpose sets ( [START_REF] Shapiro | A comprehensive study of convergent and commutative replicated data types[END_REF][START_REF] Almeida | Delta state replicated data types[END_REF][START_REF] Bieniusa | A optimized conflict-free replicated set[END_REF][START_REF] Meiklejohn | Lasp: a language for distributed, coordination-free programming[END_REF]). The meta data of existing set CRDTs associated with each element are much larger than a single number (causal length) in our CLSet CRDT. In [START_REF] Yu | A low-cost set CRDT based on causal lengths[END_REF], we compare CLSet with existing set CRDTs in more detail.

VIII. CONCLUSION

We presented a two-layer system for multi-synchronous access to relational databases in a cloud-edge environment. The underlying CRR layer uses CRDTs to allow immediate data access at edge and to guarantee data convergence when the edge devices are online. It also resolves violations of integrity constraints at merge by undoing offending updates. A key enabling contribution is a new set CRDT based on causal lengths. Applications access databases through the AR layer with little or no concern of the underlying mechanism. We implemented a prototype on top of a data mapping library that is independent of any specific DBMS. Therefore servers in the cloud and edge devices can deploy different DBMSs.

Fig. 1 .

 1 Fig. 1. A two-layer relational database system

Fig. 2 .

 2 Fig. 2. GSet CRDT and Hasse diagram of states

https://www.postgresql.org

https://www.mangodb.com

IX. ACKNOWLEDGMENT

The authors would like to thank the members of the COAST team at Inria Nancy-Grand Est/Loria, in particular Victorien Elvinger, for inspiring discussions.