Algorithm and software implementation of real-time collaborative editing of graphical schemes using Socket.IO library

Alpatov Aleksey Nikolaevich ORCID: 0000-0001-8624-1662 PhD in Technical Science Ph.D. of Engineering Sciences, Docent, Department of Instrumental and Application Software, Federal State Budget Educational Institution of Higher Education «MIREA — Russian Technological University» 78 Vernadsky Avenue, office G-225, Moscow region, 119454, Russia alpatov@mirea.ru

Yurov Il'ya Igorevich ORCID: 0009-0003-7121-4321 Master student, Department of Instrumental and Application Software, Federal State Budget Educational Institution of Higher Education «MIREA — Russian Technological University» 109383, Russia, Moscow region, Moscow, Polbina str., 35k2, 912 frit_027@mail.ru

Introduction

The HTTP protocol appeared at the end of the 20th century and during this time became the predominant data transfer technology used in the development of client-server applications in a web environment ^[1]. The HTTP protocol is based on the principle of "request-response", when the client sends the desired request, for example, GET or POST, and the server, depending on the type of request, performs the necessary actions and returns the necessary data to the client. To implement an algorithm for co-editing graphical schemes in real time, the HTTP protocol reveals significant disadvantages: the lack of bidirectional and full-duplex communication between system components ^[2]. As a result, the process of exchanging mouse cursor coordinates between the server and clients when drawing lines in the browser can cause delays and put additional load on the server.

The WebSocket protocol lacks the indicated disadvantages. The technology allows the web server and the browser to exchange data over the same connection simultaneously in both directions ^[3]. The server can send a message at any time to all clients who have previously established a connection with it. Similarly, any client can send the necessary data to the server over the same connection ^[4].

But when using the WebSocket protocol without auxiliary libraries, the implementation of an algorithm for co-editing graphical diagrams in real time will require the development of additional procedures to ensure the smooth and stable operation of system components. As part of this work, a solution to this problem will be proposed through the use of a JavaScript library Socket.IO , which adds event management, automatic reconnection upon disconnection, multiplexing and other functions ^[5].

Real-time collaborative editing process model

Let's say there are two users, A and B, who work on the same graphical scheme in different processes. Let D(t) represent the current state of the document at time t in the process of co-editing the graphic scheme. Let's assume that each user makes changes to a document independently of other users, and all changes are synchronized in real time.

Then the process of joint editing can be described by the following formula:

where D ₀ is the initial state of the document before the start of editing, ?D _i(t) are the changes made by the ith user at time t, n is the number of users involved in editing.

Thus, the current state of the document D(t) is the sum of the initial state of the document and all the changes made by each user in real time. This approach reflects the dynamics of the process of joint editing of a graphic scheme in web applications and takes into account the contribution of each participant to the formation of the final state of the document.

Various conflicts may arise during the joint editing of documents online (conflict of insertion, deletion, formatting, moving, etc.) ^[6]. Let's look at the process of data conflicts in a web application for collaborative document editing. Let's assume that each user who edits a graphical diagram has his own local set of data about the state of the document. Let D _A(t) and D _B(t) represent the current state of the document for user A and user B at time t. Then a conflict can be defined as follows: a conflict occurs if users A and B have made changes to the same node or connection of the graphic scheme during time period t — the time interval during which changes can be considered conflicting.

In other words, both users start editing the document at time t ₀. User A has made changes to the document, resulting in a change in its state from D(t ₀) to D _A(t ₁) at time t ₁, or D _A(t ₁) = D(t ₀) + ?D _A(t ₁). User B has also made changes to the document, which causes its state to change from D(t ₀) to D _B(t ₂) at time t ₂ or D _B(t ₁) = D(t ₀) + ?D _B(t ₂). Now if t ₁ < t ₂, then there is a conflict, since both users made changes to the document at different times.

The formula for determining edit time conflicts can be written as follows:

where n is a node or link, (n, t) represents the change made by the user to node or link n at time t.

The conflict detection formula for any number of users n can be written as follows:

where n is a node or connection.

If the same changes are detected for users A and B in the same node or connection during the interval t, then this is considered an editing conflict.

Let

— this is a set of changes made by the user U _i at time t, where k _i is the number of changes.

For each change ? _i,j(t), we define its compatibility with the current state of the document as C _i,j = f(? _i,j(t), D(t)). Then the conflict of compatibility of changes (two changes are incompatible) is determined by

Then, for each pair of conflicting changes, you can apply a conflict resolution function of the form

where ? _i,j,k,l(t) is the result of resolving the conflict between changes ? _i,j(t) and ? _k,l(t) at time t, ? _i,j(t) and ? _k,l(t) are changes that conflict with each other, D(t) represents the current state of the document at time t.

The g function is used to resolve the conflict between these two changes. It accepts two conflicting changes ? _i,j(t) and ? _k,l(t) as well as the current state of the document D(t) and returns the resolved change. Her task is to determine which of these changes should be applied to the document. The g function can be implemented using various conflict resolution algorithms and strategies and depending on the nature of the conflict. For example, if the changes ? _i,j(t) and ? _k,l(t) are not mutually exclusive, the function g can combine them into one change. Practically, this can be used to resolve a situation where one change inserts text and another change adds formatting to that text, they can be combined into a single change that inserts text with formatting. So ? ₁(t) represents a change that inserts Text ₁ into position Pos ₁, and ? ₂(t) represents a change that adds Format ₂ formatting to this text. Then the function g will take the following form:

where ? _merged(t) is a combined change that inserts Text ₁ using Format ₂ formatting at position Pos ₁.

An algorithm for co-editing graphical diagrams in real time

The implementation of the algorithm should begin with writing the backend of the application. A server with the right port can be created in various ways, but in this study the minimalistic Express framework was used ^[7]. After that, initialize the io instance using the Server class provided by the library Socket.IO by passing a previously created server object to its constructor ^[8]. After receiving the WebSocket server, you need to add event listeners and handlers for them. In this algorithm, the server waits for two events: connection and draw. When the first event occurs, the server generates a color event and transmits a random HEX color code for the user's graphic lines to the newly connected client. When the draw event occurs, the server sends the received coordinates of the mouse cursor movement point of a particular user to all other clients of the system over the same connection. Figure 1 shows the code of the described part of the algorithm with an instance of io.

Figure 1. The server part of the algorithm with an io instance

In the client part of the algorithm, first of all, initialize the socket instance and subscribe it to two events: color and draw. In the handler of the first event, the strokeStyle variable will store the color received from the server. In turn, in the draw handler, the client will receive the coordinates of the mouse cursor of another user from the server and build a graphic line on his screen using them using the special drawLine() function. It is worth noting that the line itself is displayed using standard JavaScript tools, namely the Canvas API tool ^[9].

 Then you need to initialize the necessary variables with initial values, get the canvas element from the HTML code of the page and bind three events to it: mousedown (the user clicked the mouse on the graphic area), mousemove (the user moves the mouse with the button held down) and mouseup (the user lowered the mouse button) ^[10]. Each of these events has its own handler. When the mousedown event occurs, the algorithm saves the initial coordinates of the startX and startY mouse cursor to the previously created mouse object and sets the isDraw variable to true. At the mousemove event, if the isDraw value is true, the following endX and endY coordinates of the mouse cursor are saved, after which all data is sent to the server via the web socket connection of the draw event and a graphical line of the current user is built.

Then, the endX and endY values are written to the properties of the mouse startX and startY object, respectively. Figure 2 shows the mousemove event handler code.

Figure 2. mousemove event handler code

When the last mouseup event occurs, the isDraw variable is set to false.

After starting the server locally, you can test the algorithm by drawing a few simple geometric shapes in three different browsers. The result is shown in Figure 3.

Figure 3. The result of the algorithm

Conclusion

We can conclude that using the Socket library.IO it is possible to implement applications for joint editing of graphic schemes in real time based on the described algorithm. The method proposed in this paper has shown its stability and ease of implementation. It is worth noting that this algorithm is awaiting improvements if, for example, it is necessary to draw smooth graphic shapes with one mouse movement, which will require additional future research. Nevertheless, the resulting algorithm is a convenient basis for more complex programs.