| JP4097008 | Electronic bulletin board page creation method and server device |
| WO/1998/006033 | EMBEDDED WEB SERVER |
| JP2002140433 | PICTURE RETRIEVING SYSTEM AND ITS METHOD |
FRANKE JOERN (DE)
| WO2003073198A2 | 2003-09-04 | |||
| WO2003007107A2 | 2003-01-23 |
TORBEN WEIS ET AL: "Federating Websites with the Google Wave Protocol", IEEE INTERNET COMPUTING, IEEE SERVICE CENTER, NEW YORK, NY, US, vol. 15, no. 3, 1 May 2011 (2011-05-01), pages 51 - 58, XP011354797, ISSN: 1089-7801, DOI: 10.1109/MIC.2011.28
ANTHONY BAXTER, JOCHEN BEKMANN, DANIEL BERLIN, SOREN LASSEN, SAM THOROGOOD: "Google Wave Federation Protocol Over XMPP", 21 July 2009 (2009-07-21), XP002687582, Retrieved from the Internet
WIKIPEDIA: "Operational Transformation", 18 May 2010 (2010-05-18), XP002687583, Retrieved from the Internet
MARC SHAPIRO, NUNO PREGUICA, CARLOS BAQUEERO, MAREK ZAWIRSKI: "Conflict-free Replicated Data Types", 31 December 2011 (2011-12-31), XP002687584, Retrieved from the Internet
| C l a i m s 1. Method for performing a distributed web application session, in particular a collaborative web browsing session, wherein a session has at least two participants (1 ) initiating via their browsers events that cause changes of a web document (2), and wherein each participant (1 ) reports changes to the browsers of the respective other participants (1 ) of said session and to a master coordinator (3), c h a r a c t e r i z e d i n that said master coordinator (3) performs the steps of analyzing changes it receives from participants (1 ) of said session, detecting among said received changes concurrent changes, which are conflicting, and instructing the participants (1 ) of said session to not apply detected conflicting changes. 2. Method according to claim 1 , wherein a vector clock or a matrix clock is attached to each change of said web document (2). 3. Method according to claim 2, wherein concurrent changes are identified by comparing said vector clocks or said matrix clocks. 4. Method according to claim 2 or 3, wherein participants (1 ) of said session apply received changes in the order defined by said vector clocks or said matrix clocks. 5. Method according to any of claims 1 to 4, wherein participants (1 ), in case of receiving concurrent changes, apply only one of them and wait for said master coordinator's (3) instructions. 6. Method according to any of claims 1 to 5, wherein said master coordinator (3), in case of insertion and/or deletion of a child node, detects conflicting changes by checking consistency with all parent nodes up to the root node. 7. Method according to any of claims 1 to 6, wherein all elements in the DOM tree of said web document (2) have different IDs. 8. Method according to any of claims 1 to 7, wherein said master coordinator (3), in order to detect conflicting changes, determines whether changes are dependent or independent by comparing the respective parent nodes. 9. Method according to any of claims 1 to 8, wherein said master coordinator (3), in case of detecting concurrent changes that are conflicting, selects a particular of said conflicting changes and instructs participants (1 ) of said session to apply only said particular change and to not apply other changes of said detected conflicting changes. 10. Method according to any of claims 1 to 9, wherein said master coordinator (3) maintains a list of changes. 1 1. Method according to any of claims 1 to 10, wherein participants (1 ) of said session whose response time for reporting changes to other participants (1) or to said master coordinator (3) exceeds a predefined threshold are disconnected from said session. 12. Method according to any of claims 1 to 1 1 , wherein the browsers of the participants (1) of said session synchronize each other and/or synchronize with said master coordinator (3) on a regular basis. 13. Method according to any of claims 1 to 12, wherein two or more master coordinators (3) are provided with each master coordinator (3) being responsible for a particular part of said web document (2). 14. System for performing a distributed web application session, in particular a collaborative web browsing session, comprising at least two participants (1) being configured to participate in a session by initiating via their browsers events that cause changes of a web document (2), and a master coordinator (3), wherein each participant (1) is configured to report changes to the browsers of the respective other participants (1) of said session and to said master coordinator (3), c h a r a c t e r i z e d i n that said master coordinator (3) comprises a module for analyzing changes it receives from participants (1) of said session and for detecting among said received changes concurrent changes, which are conflicting, and communication means for instructing the participants (1) of said session to not apply detected conflicting changes. |
APPLICATION EVENTS
The present invention relates to a method for performing a distributed web application session, in particular a collaborative web browsing session, wherein a session has at least two participants initiating via their browsers events that cause changes of a web document, and wherein each participant reports changes to the browsers of the respective other participants of said session and to a master coordinator.
Furthermore, the present invention relates to a system for performing a distributed web application session, in particular a collaborative web browsing session, comprising at least two participants being configured to participate in a session by initiating via their browsers events that cause changes of a web document, and a master coordinator, wherein each participant is configured to report changes to the browsers of the respective other participants of said session and to said master coordinator.
Distributed web applications, like for instance collaborative web browsing, have become a popular subject in recent years. During a collaborative web browsing session, different participants should have the same view on the web content displayed. For example, an insurance clerk helps a customer to fill out a form on a web page. The clerk should be able to see the customers view on the web site and vice versa. They both use their browser. This is particularly challenging for dynamic web sites programmed in web scripting languages, such as java script. Different interactions that one participant has made with the web site need to be reproduced in the browser of each participant, so that they have the same view on the web site. Current state of the art propagates events or changes made to the web page that occur when interacting with a web sites to all participants and these events/changes are replayed in the browser of the participant, so that eventually the same view on the web site can be reached. The state of the art uses a master coordinator for ordering and propagating all changes to avoid conflicts. This means the master coordinator is a significant bottleneck. Another related problem is the one of DOM-tree consistency. DOM (Document Object Model), as defined by the World Wide Web Consortium, is a cross-platform and language-independent convention for representing and interacting with objects in HTML, XHTML and XML documents. In the following example, a web page is assumed to consist of the buttons "Clear List", "Add Item" and "Remove Item" (e.g. a shopping card). Furthermore, it is assumed that there is a list consisting of three items: "Item 1 ", "Item 2", "Item 3". The simplified HTML code of this example is as follows: <html>
<head>
</head>
<body>
<button id="btn1 " onClick="deleteList()">Clear list</button>
<button id="btn2" onClick="addltem()">Add ltem</button>
<button id="btn3" onClick="deleteltem()">Delete item</button> <ul id="list1 ">
<li id="list1 item1 ">ltem 1 </li>
<li id="list1 item2">ltem 2</li>
<li id="list1 item3">ltem 3</li>
</ul>
</body>
</html> Now, two participants are assumed to co-browse the webpage. This means that as soon as something on the webpage changes (e.g. adding new list items), this is propagated to the other participant of the co-browsing session.
In connection with the following table it is described what the two participants of the above exemplary scenario see and what actions they perform over a period of 4 time intervals. Changes, which the participants make to the document, are highlighted using a black frame around the change. Time Participant 1 : Particip. 1 : Participant 2: Particip. 2:
View on webpage Actions View on Web Page Actions
0 <html> <html>
<head> <head>
</head> </head>
<body> <body>
<button id="btn1 " <button onClick="deletel_ist()">Cle id="btn1 "
ar list</button> onClick="deletel_ist()"
<button id="btn2" >Clear list</button>
onClick="addltem()">Add <button
ltem</button> id="btn2"
<button id="btn3" onClick="addltem()">
onClick="deleteltem()">D Add ltem</button> elete item</button> <button
<ul id="list1 "> id="btn3"
<li onClick="deleteltem()"
id="list1 iteml ">ltem 1 </li> >Delete item</button>
<li <ul id="list1 ">
id="list1 item2">ltem 2</li> <li
<li id="list1 iteml ">ltem 1 </li>
id="list1 item3">ltem 3</li> <li
</ul> id="list1 item2">ltem 2</li>
</body> <li
</html> id="list1 item3">ltem 3</li>
</ul>
</body>
</html>
1 <html> deleteListO <html> addltemQ
<head> <head>
</head> </head>
<body> <body>
<button id="btn1 " <button onClick="deletel_ist()">Cle id="btn1 "
ar list</button> onClick="deleteList()"
<button id="btn2" >Clear list</button>
onClick="addltem()">Add <button
ltem</button> id="btn2"
<button id="btn3" onClick="addltem()">
onClick="deleteltem()">D Add ltem</button> elete item</button> <button
<ul id="list1 "> id="btn3"
<li onClick="deleteltem()"
id="list1 iteml ">ltem 1 </li> >Delete item</button>
<li <ul id="list1 ">
id="list1 item2">ltem 2</li> <li
<li id="list1 iteml ">ltem 1 </li>
id="list1 item3">ltem 3</li> <li
</ul> id="list1 item2">ltem 2</li>
</body> <li Based on the latest item in the list, one can make two observations:
(1 ) Both participants see a slightly different html document.
(2) The html document of participant 1 is syntactically incorrect. It contains a list item, item4, but not a list.
Clearly, such situations shall be avoided since (1 ) both participants have a different view on the web document, and (2) the document can get inconsistent, which may lead to malfunctioning websites.
With regard to the inconsistency problem it should be noted that it does not make any difference if one uses, e.g., a mechanism for ordering the events or having one master from which all other participants receive updates or one master performing all actions to the DOM tree and distributing them to the other participants. This can still lead to an inconsistent document or an error (e.g. raising a click event of an element which has been deleted). Furthermore, letting one master perform and propagate all actions to a DOM tree is inefficient and can lead to a bad user experience. To name such prior art solution, reference is made to the Google Docs/Google Wave System (http://www.waveprotocol.org/protocol/draft-protocol-specs/d raft- protocol-spec), which is based on an optimistic replication scheme and requires a coordinator for ordering and propagating all changes. This is due to the operational transformation approach being used. The operational transformation approach has also the disadvantage that it cannot guarantee to leave the DOM tree structure intact without introducing more complexity, which makes the approach error-prone.
Generally, prior art solutions can be viewed from two angles: Collaborative Web Browsing and Distributed Computer Supported Collaborative Work. Collaborative Web Browsing
Collaborative web-browsing has been an active research area over the past years due to the restriction caused by the browser environment. Basically there are two types of approaches:
According to a first approach browser events are propagated to other participants' browsers, where they are replayed. More specifically, once an event occurs in a participant's browser, it is send to a coordinator, which sorts the events and propagates them in the same order to the browsers of all participants where the events are replayed. This method is rather light-weight, but has the trade-off that consistency of the respective web document, e.g. HTML, cannot be ensured.
According to a second approach changes executed by one participant are propagated to the browsers of the other participants, who apply them to the web document. More specifically, once a change to a web document occurs it is propagated to a coordinator, which orders the changes and propagates them to the other users. Unfortunately, this method does not consider concurrent changes to a web document. According to a solution that combines the above first and second approaches, events are propagated to a coordinator, which executes them in its browser and changes to the document caused by the events are send in the same order to the other browsers, where they are applied. However, this solution can still lead to inconsistent documents when concurrent events occur or it may even produce errors in the browser when replaying events on not-existing web page elements. Consequently, the browsing experience for a user may be very poor, because there is a time gap between the event (clicking on something) and receiving the results from the network. Distributed Computer Supported Collaborative Work (CSCW).
Synchronization of the work of different participating users has been part of the domain CSCW. The most prominent example there is collaborative editing of text in real-time, e.g. operational transformation (see for reference http://en.wikipedia.org/wiki/Operational_transformation) or Conflict-Free replicated data types (see for reference http://hal.inria.fr/inria-00609399/en/). Other examples may include collaboratively drawing.
Although many sophisticated approaches exist, they are only suitable for unstructured content. These approaches ensure the same state of the text at all participants, but it may contain text that has never been entered by any of the participants due to the conflict handling mechanism. However, a web page, e.g. a HTML document, is structured via tags. Using the aforementioned algorithms, tags can be destroyed when handling a conflict (e.g. <ul> may become <ulb/). This means the web page cannot be correctly rendered in the browser.
Taking the above into consideration, it is an object of the present invention to improve and further develop a method and a system of the initially described type for performing a distributed web application session in such a way that inconsistencies are avoided as far as possible, while guaranteeing at the same time a high user experience.
In accordance with the invention, the aforementioned object is accomplished by a method comprising the features of claim 1 . According to this claim, such a method is characterized in that said master coordinator performs the steps of analyzing changes it receives from participants of said session, detecting among said received changes concurrent changes, which are conflicting, and instructing the participants of said session to not apply detected conflicting changes. Furthermore, the above object is accomplished by a system comprising the features of claim 14. According to this claim, such a system is characterized in that said master coordinator comprises a module for analyzing changes it receives from participants of said session and for detecting among said received changes concurrent changes, which are conflicting, and communication means for instructing the participants of said session to not apply detected conflicting changes.
According to the invention it has first been recognized that avoiding conflicts by always treating an entire web document (for instance, each participant sending his complete document state to the other participants and/or to a coordination module) comes along with several disadvantages, the severest among them being high bandwidth costs and potential loss of non-conflicting (i.e. non-concurrent) changes. According to the invention these disadvantages are avoided since in a first step changes performed by individual participants are analyzed and conflicting changes among them are identified, whereupon in a second step only the conflicting changes are further treated. In other words, the master coordinator only propagates decisions on conflicts to all other participants of a session and not all changes, which reduces the bottleneck and the burden on the master coordinator significantly.
By applying the invention participants of a co-browsing session have the same view on a collaboratively viewed web page. Moreover, the collaboration is improved due to less confusion since every participant has the same information and a consistent web page with an acceptable user experience.
The present invention covers the entire spectrum of web pages, particularly the emerging trend towards more sophisticated web pages that allow dynamic changes, such as shopping sites or business intelligence reports. Apart from collaborative web browsing, the present invention can be suitably applied in co- shopping applications or in connection with interactive Web TV, to name just two further applications. As will be appreciated by those skilled in the art many more application scenarios can be envisioned. According to a preferred embodiment the process of detecting concurrent changes may be performed by using vector clocks (sometimes also denoted clock-vectors), which constitute a framework for generating a partial ordering of events in distributed systems. Since those skilled in the art are sufficiently familiar with the mechanism of vector clocks, details can be omitted here. However, detailed aspects of vector clocks can be found in F. Mattern: "Virtual time and global states of distributed systems", in "Parallel and Distributed Algorithms", 1989, which is incorporated herein by way of reference. It is to be understood that any other mechanisms that preserve the causal order of changes can be used as well. For instance, it may be provided that a matrix clock, instead of a vector clock, is attached to every change of a web document that is submitted to the other participants as well as to the master coordinator. Basically, matrix clocks are a generalization of the notion of vector clocks. A matrix clock maintains a vector of the vector clocks for each participant's browser. Every time a message is exchanged (e.g. a change of the web page), the sending participant's browser increases its own clock and sends his clock together with the change as well as the state of clocks he knows from the other participants' browser, when receiving their changes and attached vector clocks, to the other participants' browser and the master coordinator.
By applying any of the above mechanism, the master coordinator, who receives all changes, may identify concurrent changes by comparing the vector clocks (or the matrix clocks, alternatively) it received from a participant each time something is sent to the master coordinator. Pairwise comparison of vector clocks attached to the changes sent by each participants, can show that if Vector V1 of a Change 1 and Vector V2 of a Change 2 are
• Not concurrent, if Vl(x i )≤V2(y i )Vi and Vl≠V2 with x, is the i-th element of V1 and y i is the i-th elment of V2
• Not concurrent, V2(x i )≤ Vl(_y ; )v and Vl≠V2 with x i is the i-th element of V1 and y i is the i-th elment of V2
• Otherwise they are concurrent, i.e. (Vl < V2) & (V2 < VI)
This works similarly for matrix clocks.
According to an embodiment, browser participants that receive changes may apply them in the order defined by the vector/matrix clocks. In case of receiving concurrent changes, they may apply only one of them and then wait for the master coordinators decision. In this regard is important to note that browsers know if a non-concurrent change is missing by deriving this information from the vector/matrix clock attached to the change. Regarding an efficient detection of conflicts among concurrent changes, it is important to note that basically a conflict occurs when one tries to insert a child node (within the DOM tree of a web document) into a parent node which has been concurrently deleted or when one tries to modify concurrently the same child node. Taking this into consideration, according to a preferred embodiment the master coordinator may, in case of changes related to the insertion and/or deletion of a child node, detect conflicting changes by checking consistency with all parent nodes up to the root node. For instance, referring to the introductory example explained in connection with the above table, this means that the master coordinator would have to check the following nodes: <html>,<body>,<ul id="list1">,<li id="list1 item4">. Advantageously, in order to avoid problems with respect to failing identification, all elements in the DOM tree of a web document have assigned different IDs. Alternatively or additionally, the master coordinator, in order to detect conflicting changes, may determine whether changes are dependent or independent by comparing the respective parent nodes. For example, upon comparing a change "1 " (Delete "<html><body><ul id="list1 ">) and a change "2" (Insert <html><body><ul id="list1 "> <li id="list1 item4">), one can see that change "1 " is a subset of change "2". Assuming that both changes happen concurrently, the master coordinator we identified them as conflicting changes.
In the following the handling of conflicting changes will be described. Handling means that some changes are made to the documents of the participants that they have a converging view. Advantageously, in order not to confuse the participants, conflicting changes are highlighted to them. In one embodiment the master coordinator, in case of detecting concurrent changes that are conflicting, will select a particular of the conflicting changes and instruct participants to apply only a particular change and to not apply other changes of the detected conflicting changes. Decisions on conflict are made eventually, i.e. there might be an inconsistent state at the participants for a short time before reaching a consistent state. In a preferred embodiment the master coordinator maintains a list of changes, which assists master coordinator in detecting conflicting changes. The list may be garbage collected at one point in time, so that it does not grow exponentially. Theoretically, it can take infinite time until every concurrent change is received. From a practical point, it is suggested to disconnect participants with an inadequate response time, i.e. in case their response time for reporting changes to other participants or to the master coordinator exceeds a predefined threshold. Those participants may be blacklisted to force them to rejoin the session when they have a more reliable network connection.
According to a preferred embodiment it is provided that the browsers of the participants of a session synchronize each other on a regular basis. Such synchronization is favorable in order to rule out incomplete propagation of changes (e.g. some browsers receive changes and others not) and to detect missing changes. They may also regularly synchronize with the master coordinator to detect missing decisions. Although both measures cause more traffic, the reliability of the system is significantly increased. Instead of the deployment of a single master coordinator, in certain applications scenarios it may be favorable to have several master coordinators, each one responsible for its own part of the respective web document. The different parts of different master coordinators should not overlap. Having several master coordinators can increase the performance and reduce further bottlenecks.
There are several ways how to design and further develop the teaching of the present invention in an advantageous way. To this end it is to be referred to the patent claims subordinate to patent claim 1 on the one hand and to the following explanation of preferred embodiments of the invention by way of example, illustrated by the figure on the other hand. In connection with the explanation of the preferred embodiments of the invention by the aid of the figure, generally preferred embodiments and further developments of the teaching will we explained. In the drawing Fig. 1 is a schematic view illustrating a collaborative web browsing scenario according to a first embodiment of the present invention, and is a diagram illustrating the steps being performed by participants of a collaborative web browsing session according to a second embodiment of the present invention.
Fig. 1 illustrates - schematically - a collaborative web browsing scenario with a total of n browser participants 1 that participate in a web browsing session, in which they access a particular web document 2. For the purpose of clarity, only three participants 1 are depicted in Fig. 1.
Changes of the web document 2 caused by events that are performed by the participants 1 in the co-browsing session are propagated to all other participants 1 .
Again for the purpose of clarity, in Fig. 1 change propagation is indicated only with respect to participants that are neighboring participants in the context of Fig. 1 .
However, it is to be understood that each participant 1 transmits changes to all other participants 1 of the session. Thus, they have eventually the same view on the web page 2 as intended by collaborative web browsing. It is noted that only the changed parts of the web document 2 are submitted to others and not the whole document.
A master coordinator 3 is provided to which participants 1 also propagate their changes. After a change to the web document 2 has been made and has been reported to the master coordinator 3, the following procedure applies:
In the first step, the master coordinator 3 detects concurrent changes, which are conflicting. The second step is about handling conflicting changes. Generally, according to the present invention the master coordinator 3 decides just on conflicting changes. Therefore, it is not a bottleneck, because it does not have to propagate all changes, but just decisions on conflicting changes. Detecting concurrent changes which are conflicting is performed by using a mechanism that preserves the causal order of changes, for instance a vector clock or a matrix clock approach. For instance, to every change of the web page 2 a vector clock is submitted to the other participants 1 and to the master coordinator 3. The master coordinator 3 receives all changes and can identify concurrent changes by comparing vector clocks.
As a next step the master coordinator 3 has to identify among these changes those changes that are conflicting. A conflict occurs, for instance, in case a child node is inserted into a parent node which has been concurrently deleted, or when the same child node is concurrently modified. Therefore, the master coordinator 3 either checks all parent nodes up to the root node involved in a change, or it checks whether changes are dependent or independent. Once concurrent changes that are conflicting have been detected, these changes will be handled as follows:
Basically, the challenge is that conflicting changes do not arrive necessarily at the same time. A na ' ive solution would imply that the master coordinator 3 waits a period of time for all changes to arrive, however, this waiting period is unpredictable and may lead to problems if a conflicting change arrives after waiting period.
Therefore, according to an embodiment of the present invention, upon arrival of a received change, the master coordinator 3 checks if it is concurrent conflicting with other changes, as already explained above. If this is not the case, the master coordinator 3 will not perform any further action. However, in case a change is concurrent conflicting with already propagated changes, the master coordinator 3 informs the other participants 1 , which one of the changes which are conflicting should not be applied. The participants 1 then apply the decision of the master coordinator. This means that participants 1 are informed about unexpected changes in the web document 2 (from their perspective) so that they are not confused and that no exceptions are raised in the browser systems or an inconsistent document is created. As an example of the above procedure, it is assumed that the master coordinator 3 receives from a first participant 1 "Delete "<html><body><ul id="list1">". From a second participant 1 the master coordinator 3 may receive "Insert <html><body><ul id="list1 "> <li id="list1 item4">". In this case the master coordinator 3 should detect that both changes are concurrently conflicting. Therefore, the master coordinator 3 submits to the participants 1 of the respective session that this change should not be applied or removed from the web document 2. The effect of this is that the list is deleted at all participants' 1 browsers. It is noted that if the of the changes would have arrived in different order, then all participants 1 would have a list with four items. Nevertheless, the importance is that they all have the same view, which is ensured by the decision of the master coordinator 3. Fig. 2 is a diagram that schematically illustrates the steps being performed by participants of a collaborative web browsing session according to another embodiment of the present invention. The basic assumptions underlying the illustrated scenario are as follows: One participant 1 - browser participant 1A - initiates an event, denoted X, that changes the web document subject to the co-browsing session. Browser participant 1A determines the change, denoted C, to the web document affected by event X and propagates the change C to the other participants 1 of the session, which are depicted in Fig. 2 as a composite browser participant being denoted 1 B. In the illustrated embodiment, browser participant 1A transmits the event X and a clock vector V together with change C. The same information is propagated to master coordinator 3.
Generally, when changes are propagated to the browsers of the other participants 1 B and the master coordinator 3, the browsers of the other participants 1 B apply these changes directly. Due to the implemented vector clock approach, the master coordinator 3 does not need to perform an ordering of changes, because this can be figured out by the participants 1 themselves, e.g. by deriving the respective information from the vector clock attached to the changes. The master coordinator 3 just decides which changes can be applied and which not. To this end, master coordinator 3 analyzes changes received from participants 1 to find out, in a first step, whether changes are concurrent. In a next step, changes that are concurrent are further analyzed to find out whether they are also conflicting. If so, master coordinator 3 performs a conflict resolution. The respective conflict resolution decision, denoted D, is propagated to the browsers of all participants 1 of a session, which then implement the decision.
Many modifications and other embodiments of the invention set forth herein will come to mind the one skilled in the art to which the invention pertains having the benefit of the teachings presented in the foregoing description and the associated drawings. Therefore, it is to be understood that the invention is not to be limited to the specific embodiments disclosed and that modifications and other embodiments are intended to be included within the scope of the appended claims. Although specific terms are employed herein, they are used in a generic and descriptive sense only and not for purposes of limitation.