INSTANT SYNCHRONIZATION OF STATESIN WEB HYPERTEXT APPLICATIONS
vorgelegt von
Diplom-Informatiker
David Linner
aus Berlin

Von der Fakultät für Elektrotechnik und Informatik
der Technischen Universität Berlin
zur Erlangung des akademischen Grades
Doktor der Ingenieurwissenschaften
Dr. Ing.
genehmigte Dissertation

Promotionsausschuss:
Vorsitzender: Prof. Dr. Odej Kao
Berichter: Prof. Dr. Dr. h.c. Radu Popescu-Zeletin
Berichter: Prof. Dr. Axel Küpper
Berichter: Prof. Dr. Lutz Prechelt
Tag der wissenschaftlichen Aussprache: 27.01.2012

Berlin, 2012

D 83

Instant Synchronization of States in Web Hypertext Application

2

Instant Synchronization of States in Web Hypertext Applications

Abstract
The World Wide Web (web) has become one of the most relevant platforms for distributed,
networked applications. This includes applications that support direct interactions among users.
This thesis provides an answer to the technological challenges arising from the realization ofreal-time interactions. The real-time interaction is an approximation of the interaction wherein
the moment of a user action and the moment the corresponding effect can be perceived areequal. Considered is the spectrum between interaction as means to achieve a common objective
and interaction as means to achieve individual objectives. For this purpose i) ways to minimize
the time-span between user action and play-out of the corresponding effect are investigated; ii)
the impact of concurrent user actions is addressed with regard to user intentions, especiallywhere user actions refer to application objects (e.g. a document or an auction). The findings are
summarized to a software framework. The software framework shall help to significantly reduce
human resources in the engineering process of interactive applications.
The international technology standards around the Hypertext Markup Language are introduced
as background of this thesis. They define the technological fundament for the solution to befound. Starting from the resource-centered architectural style of the Web, state-of-the-art
methods for accessing the state of a shared data resource are described. The methods are
discussed with regard to their suitability for the realization of collaborative and competitive
real-time interactions. A combination of Operational Transformation and Bucket Synchronization
method are identified as appropriate.
The concept presented here brings both methods together. A communication schema based on
operations and an algorithm for the resolution of conflicts between concurrent operations withrespect to user intentions is created. Additionally, a general-purpose model for the
representation of states for application object is proposed. As base for a validation, the concept
is completely implemented. The validation comprises evaluation and benchmark tests as well asa case study. The evaluation test confirms the correct realization of the concept in theimplementation. The benchmark tests reveal shortcomings of implementation with regard toscalability. The case study confirms that the thesis objective, a less resource intensive software
engineering process, is achieved.

3Instant Synchronization of States in Web Hypertext Application

4

Instant Synchronization of States in Web Hypertext Applications

Zusammenfassung
Das World Wide Web (kurz Web) hat sich als Plattform für verteilte, vernetze Anwendungenetabliert. So auch für Anwendungen, die die direkte Interaktion von Anwendern miteinander
unterstützen. Diese Arbeit beschäftigt sich mit den technologischen Herausforderungen, die ausder Umsetzung von Echtzeitinteraktionen im Web erwachsen. Echtzeitinteraktionen sind eine
Annäherung an Interaktionen, in denen der Moment einer Benutzeraktion und der Moment derWahrnehmbarkeit des Effekts durch andere Anwender übereinstimmen. Betrachtet wird das
Spannungsfeld zwischen Interaktionen die der Erlangung eines gemeinsamen Ziels undInteraktionen die der Erlangung individueller Ziele dienen. So wird zum einen untersucht wie
die Zeit zwischen Benutzeraktion und Wiedergabe des dazugehörigen Effekts so kurz wie
möglich gestaltet werden kann. Zum anderen werden die Auswirkungen der Gleichzeitigkeit von
Aktionen verschiedener Benutzer mit Blick auf deren Absichten behandelt, insbesondere für den
Fall, dass sich die Aktionen auf ein Anwendungsobjekt (z.B. ein Dokument oder eine Auktion)
beziehen. Es entsteht ein Softwarerahmenwerk, das die Realisierung von interaktiven
Anwendungenmit

Echtzeitanspruch

beschleunigt

undEntwicklungs-

undProgrammieraufwände somit deutlich verkürzt.
Als Hintergrund der Arbeit werden die internationalen Technologiestandards um die Hypertext
Markup Language und gängige Praktiken für deren Einsatz vorgestellt. So wird zunächst dertechnologische Rahmen definiert in dem die Lösung zu suchen ist. Ausgehend von dem auf
Ressourcen ausgelegten Architekturstil des Webs werden dann bekannte Methoden aufgezeigt
um auf den Zustand einer gemeinsam genutzten Ressource zuzugreifen. Interaktionen werden
mittels wechselseitigem Lesen und Schreiben auf Ressourcen abgebildet. Entsprechend werden
die aufgezeigten Methoden mit Blick auf ihre Tauglichkeit für die Realisierung von kooperativen
und konkurrierenden Echtzeitinteraktionen diskutiert. Als probate Lösung, die sowohl
Unmittelbarkeit als auch Fairness gewährt, wird eine Kombination aus Operational
Transformation und Bucket Synchronization Verfahren identifiziert.
Im

Konzept

werdenbeide

Verfahren

zusammengeführt.

Es

entstehen

ein

Kommunikationsschema für Benutzeraktionen auf Basis von Operation und ein Algorithmus fürdie Auflösung von Konflikten zwischen gleichzeitigen Operationen unter Berücksichtigung der
Benutzerabsichten. Darauf aufbauend wird ein Model für die Darstellung von Zuständen fürAnwendungsobjekte eingeführt. Als Basis für die Evaluierung wird das Konzept vollständig
implementiert.

Die

Implementierungbildetdie

Grundlage

fürKorrektheit-

undGeschwindigkeitstests. Außerdem wird damit eine Fallstudie durchgeführt. Die ersten Tests
bestätigen

diekorrekte

UmsetzungdesKonzepts

inderImplementierung.

Die

Geschwindigkeitstests zeigen Schwächen in der Skalierbarkeit der Implementierung. Die
Fallstudie bestätigt, dass die Ziele mit Blick auf den Softwareentwicklungsprozess erreicht
wurden.

5Instant Synchronization of States in Web Hypertext Application

6

Instant Synchronization of States in Web Hypertext Applications

Acknowledgements
First of all, I would like to thank my supervisor Prof. Dr. Radu Popescu-Zeletin, who gave me theopportunity to work at both the Technische Universität Berlin (TUB) and the Fraunhofer
Institute for Open Communication Systems (FOKUS) and thus let me experience an environmentthat gave me room for fundamental as well as applied research. I'm grateful for his continual
openness, patience, and guidance during the past years.
I'm deeply thankful to all my colleagues at TUB and FOKUS, and those who worked with me on
the Real-time Web project and the Communication Cockpit project over the last years. Theircomments and criticisms during many fruitful discussions were of tremendous importance andhelp.
I would like to thank all the students who have graduated in the field of real-time interactive
applications on the web. Special thanks go out to Rafael Grote, Niko Pfeifer, and Stanley Schraglfor their veritably outstanding work.
I would not have been able to complete my work without the continuous support,
encouragement, and warmth of my family, Anne and Valerie. I'm grateful for their ability tocheer me up and to refill my strength by simply being there.

7Instant Synchronization of States in Web Hypertext Application

8

Instant Synchronization of States in Web Hypertext Applications

Table of Contents
List of Figures ........................................................................................................................................13
List of Tables..........................................................................................................................................16
List of Algorithms ..................................................................................................................................17
List of Definitions ..................................................................................................................................18
List of Interfaces ....................................................................................................................................19
1

2

Introduction ....................................................................................................................................20
1.1

Motivation and Objective .......................................................................................................20

1.2

Scope ......................................................................................................................................22

1.3

Methodology ..........................................................................................................................23

1.4

Contribution ...........................................................................................................................24

1.5

Outline ....................................................................................................................................25

The Web as a Platform ...................................................................................................................27
2.1

Background ............................................................................................................................27

2.2

Application Models ................................................................................................................28

2.2.1

Traditional Application Model .......................................................................................28

2.2.2

Extensions to the Traditional Application Model ..........................................................30

2.2.3

Modern Application Model ............................................................................................30

2.3

3

4

Low-Latency Bidirectional Communication ..........................................................................35

2.3.1

Frequent Polling .............................................................................................................35

2.3.2

Streaming .......................................................................................................................36

2.3.3

Long Polling ...................................................................................................................37

2.3.4

WebSocket .....................................................................................................................37

Resource-centric Interaction ..........................................................................................................39
3.1

Resource Access Paradigms ...................................................................................................39

3.2

Consistency in Real-time Interactive Applications ................................................................40

3.3

Lockstep Synchronization ......................................................................................................43

3.4

Bucket Synchronization .........................................................................................................44

3.5

Time Warp .............................................................................................................................45

3.6

Trailing State ..........................................................................................................................47

3.7

Operational Transformation ...................................................................................................48

3.8

Differential Synchronization ..................................................................................................52

3.9

Discussion ..............................................................................................................................53

Related Work .................................................................................................................................55

9

Instant Synchronization of States in Web Hypertext Application

4.1

Theoretical Efforts ................................................................................................................. 55

4.2

Middleware and Tools ........................................................................................................... 58

4.3

Software Frameworks ............................................................................................................ 59

4.4

Summary................................................................................................................................ 61

5Instant Synchronization of a Shared State ..................................................................................... 63
5.1

Overview ............................................................................................................................... 63

5.2

State Representation and Synchronization ............................................................................ 64

5.3

Communication Scheme ........................................................................................................ 65

5.3.1

Operation pipelining ...................................................................................................... 66

5.3.2

Latency estimation and fairness .................................................................................... 68

5.4

State Copies Convergence ..................................................................................................... 71

5.4.1

Preservation of Operation Causality .............................................................................. 72

5.4.2

Preservation of Operation Semantic .............................................................................. 74

5.5

Operation Mode Determination ............................................................................................. 80

5.6

Control Algorithm ................................................................................................................. 81

6

Instant State Synchronization System ........................................................................................... 86
6.1

Overview ............................................................................................................................... 86

6.2

Scopes .................................................................................................................................... 87

6.3

Network Interface .................................................................................................................. 88

6.3.1

Session Participation...................................................................................................... 90

6.3.2

State Copies Maintenance ............................................................................................. 92

6.3.3

Scope Subscription and Unsubscription ........................................................................ 94

6.3.4

Summary of Basic Profile.............................................................................................. 95

6.4

Client Interface ...................................................................................................................... 96

6.5

Server Interface ..................................................................................................................... 97

6.6

Surrogate Management Interface........................................................................................... 99

7

Web Object State Model ............................................................................................................. 101
7.1

State Representation ............................................................................................................ 101

7.2

Operations to Modify the State ............................................................................................ 102

7.3

Inclusion Function ............................................................................................................... 107

7.4

Pseudo Random Tie-Breaking Method for the Inclusion Function ..................................... 108

8

The Pulsar System ....................................................................................................................... 110
8.1

Overview ............................................................................................................................. 110

8.2

Network Interfaces .............................................................................................................. 111

10

Instant Synchronization of States in Web Hypertext Applications

8.2.1

Text Interface ...............................................................................................................111

8.2.2

Binary Interface ............................................................................................................112

8.3

8.3.1

Data Structures .............................................................................................................117

8.3.2

Session Management ....................................................................................................117

8.3.3

Custom Configuration ..................................................................................................119

8.3.4

Component Interworking .............................................................................................121

8.4

9Server ...................................................................................................................................116

Client ....................................................................................................................................123

8.4.1

Session Management ....................................................................................................123

8.4.2

RTSYNC Server Adapter .............................................................................................125

8.4.3

Application Programmer Interface ...............................................................................130

Evaluation and Benchmark ..........................................................................................................133
9.1

System Evaluation ................................................................................................................133

9.1.1

Setup of Test Environment ...........................................................................................133

9.1.2

Test Procedure ..............................................................................................................134

9.1.3

Testing Interaction Delay .............................................................................................135

9.1.4

Results of Interaction Delay Test .................................................................................136

9.1.5

Testing Fairness of Conflict Resolution .......................................................................138

9.1.6

Results of Fairness Test................................................................................................138

9.2

System Benchmark ...............................................................................................................140

9.2.1

Setup of Test Environment ...........................................................................................140

9.2.2

Test Procedure ..............................................................................................................141

9.2.3

Testing Performance ....................................................................................................142

9.2.4

Results of Performance Tests .......................................................................................142

10

Case Study ................................................................................................................................146

10.1

Propositions and Methodology.............................................................................................146

10.2

Case: Collaborative Text Editor ...........................................................................................147

10.3

Case: Bomberman ................................................................................................................153

10.4

Findings and Analysis ..........................................................................................................157

11

Conclusion................................................................................................................................159

11.1

Summary and Discussion .....................................................................................................159

11.2

Future Prospects ...................................................................................................................160

References ............................................................................................................................................162
Annex A: Data Schemes of JSON-encoded Messages ........................................................................169

11

Instant Synchronization of States in Web Hypertext Application

Annex B: Field Codes for Binary Messages ....................................................................................... 171
Annex C: Inclusion Function for Rich Text Documents ..................................................................... 172

12

Instant Synchronization of States in Web Hypertext Applications

List of Figures
Figure 1-1: Methodology of this thesis .................................................................................................................. 24
Figure 2-1: Web Architecture .................................................................................................................................... 27
Figure 2-2: Example CGI application ...................................................................................................................... 29
Figure 2-3: Example JS application.......................................................................................................................... 31
Figure 2-4: Yahoo user interface in 1996 ............................................................................................................. 32
Figure 2-5: Yahoo user interface in 2008 ............................................................................................................. 32
Figure 2-6: Example XHR application .................................................................................................................... 34
Figure 2-7: Comet technique frequent polling.................................................................................................... 35
Figure 2-8: Comet technique streaming ................................................................................................................ 36
Figure 2-9: Comet technique long polling ............................................................................................................ 37
Figure 3-1: Basic access models for shared state .............................................................................................. 40
Figure 3-2: Consistency-latency tradeoff .............................................................................................................. 41
Figure 3-3: Processing events in Lockstep Synchronization ........................................................................ 43
Figure 3-4: Processing events in Bucket Synchronization ............................................................................ 44
Figure 3-5: Processing of events in Time Warp mechanism......................................................................... 46
Figure 3-6: Processing of events in Trailing State ............................................................................................. 48
Figure 3-7: Preceding and concurrent operations ............................................................................................ 49
Figure 3-8: Concurrence of multiple operations ............................................................................................... 50
Figure 4-1: State space and transformation paths ............................................................................................ 56
Figure 4-2: Architecture of Wave ............................................................................................................................. 59
Figure 4-3: Architecture of CoWeb .......................................................................................................................... 60
Figure 5-1: State and operations .............................................................................................................................. 65
Figure 5-2: Adapted bucket synchronization ...................................................................................................... 67
Figure 5-3: Pipelining of request and update messages ................................................................................. 68
Figure 5-4: Individually delayed update messages .......................................................................................... 69
Figure 5-5: Taking advantage of delayed request messages ........................................................................ 70
Figure 5-6: Challenges in copies convergence .................................................................................................... 71
Figure 5-7: Example of handling state reference vectors .............................................................................. 73
Figure 5-8: Operation ordering ................................................................................................................................. 75
Figure 6-1: Basic System Overview ......................................................................................................................... 86
Figure 6-2: State and Scopes ...................................................................................................................................... 87
Figure 6-3: Generic message format ....................................................................................................................... 88
Figure 6-4: Fields in message Head ......................................................................................................................... 89
Figure 6-5: Fields of Message Part ........................................................................................................................... 89

13

Instant Synchronization of States in Web Hypertext Application

Figure 6-6: Fields in message Data Unit ................................................................................................................ 89
Figure 6-7: Message flow for session participation .......................................................................................... 90
Figure 6-8: Operation exchange ................................................................................................................................ 92
Figure 6-9: Processing of late messages ................................................................................................................ 93
Figure 6-10: Scope subscription ............................................................................................................................... 94
Figure 6-11: Example of the interplay between network and client interface ...................................... 97
Figure 7-1: Partially ordered tree ......................................................................................................................... 101
Figure 7-2: Example for (re-)setting a path-value relation ........................................................................ 103
Figure 7-3: Unset path-value relation .................................................................................................................. 104
Figure 7-4: Shifting nodes ......................................................................................................................................... 106
Figure 8-1: Pulsar system overview ..................................................................................................................... 110
Figure 8-2: Connection handling in the text-based network interface .................................................. 112
Figure 8-3: RTSYNC message for UDP PDUs ..................................................................................................... 113
Figure 8-4: RTSYNC message head ....................................................................................................................... 113
Figure 8-5: RTSYNC message data units ............................................................................................................. 113
Figure 8-6: RTSYNC message variable-length field coding ......................................................................... 114
Figure 8-7: RTSYNC lost update ............................................................................................................................. 114
Figure 8-8: RTSYNC lost request............................................................................................................................ 115
Figure 8-9: RTSYNC interval length adaptation .............................................................................................. 115
Figure 8-10: RTSYNC TCP breakout ..................................................................................................................... 116
Figure 8-11: Pulsar server overview.................................................................................................................... 116
Figure 8-12: UML class diagram for sata structures in Pulsar server realization ............................. 117
Figure 8-13: UML class diagram for Pulsar server core components .................................................... 118
Figure 8-14: UML class diagram of custom session configuration .......................................................... 119
Figure 8-15: Simplified UML sequence diagram for session initialization ........................................... 121
Figure 8-16: Simplified UML sequence diagram for regular component interworking in Pulsar
server ................................................................................................................................................................................ 122
Figure 8-17: Overview of Pulsar client architecture ..................................................................................... 123
Figure 8-18: UML class diagram of client session management ............................................................... 124
Figure 8-19: UML sequence diagram of client session setup ..................................................................... 125
Figure 8-20: RTSYNC Server Adapter Overview ............................................................................................. 125
Figure 8-21: UML diagram of synchronization endpoint in the RTSYNC server adapter .............. 127
Figure 8-22: Rough UML sequence diagram of RTSYNC client component interaction ................. 128
Figure 8-23: Communication across code contexts, DOM vs. XPCOM .................................................... 129
Figure 9-1: Setup of test environment................................................................................................................. 133
Figure 9-2: Evaluation web application deployed to the testbed (logical setup) .............................. 134

14

Instant Synchronization of States in Web Hypertext Applications

Figure 9-3: Sequence diagram of test procedure ............................................................................................135
Figure 9-4: Measurement results for the synchronization delay with minimum and maximum
deviation ...........................................................................................................................................................................137
Figure 9-5: Measurement results for the interaction delay with minimum and maximum
deviation ...........................................................................................................................................................................137
Figure 9-6: Success rate of a client with delay prone connection.............................................................139
Figure 9-7: Success rate of a client with jitter prone connection .............................................................139
Figure 9-8: Success rate of a client with loss prone connection................................................................140
Figure 9-9: Mean processing time for increasing numbers of clients and a constant number ofoperations per client. ..................................................................................................................................................143
Figure 9-10: Mean receive and send time for increasing numbers of clients and a constantnumber of operations per client. ............................................................................................................................144
Figure 9-11: Mean processing time for increasing numbers of operations per client and constanta number of clients. ......................................................................................................................................................144
Figure 10-1: Screenshot of the application resulting from the case “collaborative text editor” .147
Figure 10-2: Screenshot of the application resulting from the case “Bomberman”..........................154

15

Instant Synchronization of States in Web Hypertext Application

List of Tables
Table 5-1: Examples for state representations ................................................................................................... 64
Table 5-2: Operation allocation for example 1 in operation mode (1) ..................................................... 74
Table 5-3: Operation allocation for example 1 in operation mode (2) ..................................................... 75
Table 5-4: Operation allocation for example 2 in operation mode (1) ..................................................... 76
Table 5-5: Operation allocation for example 2 in operation mode (2) ..................................................... 76
Table 5-6: Exemplary transformation matrix ..................................................................................................... 82
Table 6-1: Message a) - joining a session .............................................................................................................. 90
Table 6-2: Message b) - error on joining a session ............................................................................................ 91
Table 6-3: Message c) - update on joining a session ......................................................................................... 91
Table 6-4: Message d) - leaving a session ............................................................................................................. 92
Table 6-5: Message e) - requesting the application of operations to the lead state ............................ 93
Table 6-6: Message f) - updating a state copy ..................................................................................................... 93
Table 6-7: Message g) – subscribing and unsubscribing a scope ................................................................ 94
Table 6-8: Message f) - initializing a scope ........................................................................................................... 95
Table 6-9: Message types of basic network interface profile ........................................................................ 95
Table 6-10: Data Unit types of basic network interface profile ................................................................... 95
Table 7-1: Case switch for inclusion function on WOS ................................................................................ 108
Table 9-1: Configuration of testbed machines. ................................................................................................ 134
Table 9-2: Configuration of machines in benchmark testbed .................................................................... 140
Table 10-1: Operation types for rich text state model .................................................................................. 151

16

Instant Synchronization of States in Web Hypertext Applications

List of Algorithms
Algorithm 5-1: Transformation of operation lists............................................................................................. 82
Algorithm 5-2: Creation of the transformation matrix ................................................................................... 83
Algorithm 5-3: Creation of operation lists resulting from transformation ............................................ 84
Algorithm 5-4: Updating operations for transformation in the current state ....................................... 84
Algorithm 7-1: Shift function ...................................................................................................................................105
Algorithm 7-2: Initialization of the priority hash array ................................................................................109
Algorithm 10-1: Recursive list transformation for inclusion function that returns an operation
list ........................................................................................................................................................................................152

17

Instant Synchronization of States in Web Hypertext Application

List of Definitions
Definition 3-1: Transformation Property 1 (TP1) ............................................................................................. 50
Definition 3-2: Transformation Property 2 (TP2) ............................................................................................. 51
Definition 5-1: State Reference.................................................................................................................................. 72
Definition 5-2: Operation ............................................................................................................................................. 73
Definition 5-3: Precedence .......................................................................................................................................... 74
Definition 5-4: Concurrence ....................................................................................................................................... 74
Definition 5-5: Competition ........................................................................................................................................ 77
Definition 5-6: Inclusion Transformation ............................................................................................................. 78
Definition 5-7: Context Equivalence ........................................................................................................................ 79
Definition 5-8: Operation Schema ............................................................................................................................ 80
Definition 5-9: System Configuration ..................................................................................................................... 80
Definition 7-1: Web Object State............................................................................................................................ 102
Definition 7-2: Set Path-Value Relation .............................................................................................................. 102
Definition 7-3: Unset Path-Value Relation ......................................................................................................... 103
Definition 7-4: Rewrite Path-Value Relation .................................................................................................... 104
Definition 7-5: Insert and Truncate ...................................................................................................................... 106
Definition 7-6: Unset Multiple Path-Value Relations..................................................................................... 106

18

Instant Synchronization of States in Web Hypertext Applications

List of Interfaces
Interface 8-1: Operation.............................................................................................................................................120
Interface 8-2: Handle to a copy of the resource state ....................................................................................120
Interface 8-3: Inclusion function ............................................................................................................................121
Interface 8-4: Function to analyze relation of two operations ..................................................................121
Interface 8-5: Schema function to check of an operation can be applied instantly...........................121
Interface 8-6: API – global access object .............................................................................................................130
Interface 8-7: API - session controller..................................................................................................................131
Interface 8-8: API - session interface ....................................................................................................................131

19

1 Introduction
The introduction starts with the objectives and scope, and justifies the approach chosen to achieve
the objectives. Finally the structure of this thesis is outlined.

1.1

Motivation and Objective

More than 1.3 billion computing devices worldwide, from smart phone to desktop computer,support the playback of rich, digital content encoded with the family of industry standards
around the Hypertext Markup Language (HTML) [1]. More than 1 trillion unique offers of suchencoded content are counted on Internet hosts [2]; they form the World Wide Web. More than
70% of the offers on the web are applications in the sense that user inputs define the presented
content or the kind of presentation [3]. The web is thus one of the most relevant platforms for
networked and distributed applications today.
The rise of the social web (formerly known as web 2.0 [4]) demonstrates the maturity of the
web as platform for distributed interactive applications, i.e. applications that enable users “to act
on or in close relation with each other” [5]. The objectives of application users define whether aninteraction is competitive or collaborative. If two or more users pursue individual objectives, forexample in an auction, the interaction is competitive. If all users pursue a common objective, as
for instance in a wiki, the interaction is collaborative. Most interactive applications base on
examples in the real world. Challenging, however, is the reproduction of the natural timing ofinteractions, especially when all interacting users should perceive effects of actions at the
moment they originate [6], i.e. a reaction could happen instantly. The approximation of this ideal
is referred to as real-time interaction in the following chapters. This definition is close to the
traditional definition of soft real-time systems as e.g. provided in [7], while deadlines are definedby the limits of human cognition.
For the support of collaborative and competitive real-time interactions in a distributed
application the following requirements are considered crucial in this thesis:a)A user action has to take effect as soon as possible after it is issued.

b)

A user has to be able to perceive an action, i.e. the resulting effect, as soon as possible after
the action is issued.

c)An effect of an action has to be durable, i.e. it must not be rolled back.

d)

For any two users the perceived effect of an action has to be the same.

e)

For any two users the moment an effect becomes perceptible has to be the same. No user
must be able to draw an advantage from an earlier perceptibility.

f)

Any instant reactions of different users to the same action have to take effect at the same
time.

20

Instant Synchronization of States in Web Hypertext Applicationsg)

Any instant user reactions to the same action that have mutually exclusive effects must be
resolved equitably.

While the requirements a)-c) are relevant for both, competing and collaborative interactions, therequirements d)-g) provide a definition of the concept fairness, as utilized in this thesis.
The industry standards for the web imply one architectural style and one communication
pattern for all web applications. The architectural styles require mapping all user actions in an
application to read, write and execute operations on a centralized resource [8]. Accordingly, thecommunication pattern is limited to a request-response scheme terminated at the central
resource. To design a web application that supports the direct interaction of two or more users,
a mutual read-write scheme has to be applied to notify about user actions. As a result, engineersof an application that supports real-time interaction face two major challenges:i)

The mutual reading and writing has to be optimized with regard to the time interval
between a user action and a corresponding effect perceptible by other users.- requirementsa) and b)ii)

The shift between action and effect perception causes concurrent user actions. Concurrent
user actions conflict if the expressed user intentions collide. If user actions address anapplication object, such as a document or a trade, conflicts should be resolved by theapplication with respect to the user objectives. In a collaborative context the intentions
behind two or more user actions can be reconciled. In a competitive context the resolutionof conflicts has to be fair at least. - requirements c) to g)

As requirements and corresponding challenges suggest, considering traditional properties forreliable resource access only, i.e. atomicity, consistency, isolation and durability (ACID), is not
sufficient in the context of real-time interactive applications. Additionally the properties
instantaneity and simultaneity in terms of [9] have to be respected. Collaboration tools, e.g.
collaborative text editing, drawing or co-browsing applications, successfully address the
problem of message concurrency when users interact while pursuing a common objective.
Solutions for handling interactions where users pursue individual objectives are studied in thecontext of multi-player games [10-12]. However, such approaches have not yet reached the web
in a variety comparable to collaboration tools.
The objective of this thesis is to create a software framework that provides a broad base forexperimenting with innovative applications for collaborative and competitive interactions inclose to real-time. The software framework is supposed to relieve software engineers of theburden of realizing solutions for action notification and conflict resolution. A strong fit with thearchitectural style of the web and the application model are intended to lower the expense ofadaption. The software framework shall help to reduce the resources for software engineeringand to minimize the risks in the realization of applications in an algorithmically andtechnologically challenging area.

21

Instant Synchronization of States in Web Hypertext Application

1.2

Scope

The responsiveness of distributed interactive applications, i.e. the action-perception timeinterval introduced above, is influenced on network-level and application-level. Network delays
are mainly caused by the propagation speed of signals on the links, the load on the links and theprocessing of packets at the routers. An optimization of network topology, capacity andequipment has a positive impact on the responsiveness of distributed interactive applications,but is beyond the scope of this thesis. Optimizations on application level aim at i) thecommunication algorithms, ii) the information management, or iii) at the system architecture[13]. The communication algorithms define the meaning of events and the patterns for theexchange of events between hosts. The optimization of algorithms aims at best satisfying theuser interaction model implemented by an application, such as message passing,publish/subscribe or document sharing. The information management addresses the handling ofdata and the utilization of data semantics to optimize the responsiveness of applications. For thisreason data compression is a means of information management as well as dead reckoning.
Dead reckoning is utilized to predict events in a limited space of possibilities. The systemarchitecture describes the components required to realize an application. Optimizations of thesystem architecture mainly focus on reducing the number of network hosts involved in userinteraction and on shortening the physical distances between these hosts. The impact of the
network characteristics is supposed to be reduced. This work addresses communication
algorithms and system architecture for distributed interactive applications on the web.
Information management techniques are not addressed beyond the state of the art.
Apart from numerous combinations like Publish-Subscribe Systems [14, 15], Data Spaces [1618], Blackboards [19] and Remote Procedure Call [20], the two basic means for communication
between two or more sites of a distributed application are the messages and shared resources.
Other methods are either derivations or combinations. Both methods are suitable for therealization of interactive applications. Web applications base on mutually writing to and readingfrom shared resources [8]. The communication method is thus resource-centric. The software
framework presented in this work is intended to respect the technological principles of the web
and complement existing technologies. Message-centric approaches for the realization of userinteractions are thus out of scope and are not considered in detail.
Interactions among users are generally classified as competing or collaborative. The web asapplication platform does not make a difference between these classes, but for real-time
interactive applications they determine the appropriate family of algorithms. In order to retain
the generality of the platform, the solution presented here addresses both classes of userinteractions.

22

Instant Synchronization of States in Web Hypertext Applications

1.3

Methodology

The work conducted in the scope of this thesis comprises eight major steps documented in thefollowing. Figure 1-1 show the dependencies between these steps.
1. Study web as a platform: Classify the role of the web as application platform, research themodels for realizing applications on the web and methods to enable the communication
between multiple sites of a web application with low-latency.
2. Study instant state synchronization techniques: Understand and qualify the range ofalgorithmic solutions for handling shared resources in time critical environments. Identify
appropriate algorithms for mapping collaborative and competitive user interactions tooperations on shared resources.
3. Research instant state synchronization solutions for the web: Identify and analyze current
approaches to realize real-time interaction in web applications, software solutions as well as
theoretical work. Clarify how this thesis distinguishes from related work.
4. Algorithmic and conceptional framework: Design a communication scheme that respects thealgorithmic requirements as well as the characteristics of the application platform web.
Define state access mechanisms, constraints and conflict resolution methods for a genericresource state model.
5. All-purpose resource state model for web applications: Define the basic data structure for astate model applicable in web applications and define primitives to modify this data
structure. Specify a configuration to adapt state model and primitives to the conflict
resolution methods of the algorithmic and conceptional framework.
6. Abstract software system specification: Define how algorithmic and conceptional framework
can be realized in a software system independent from the technological solutions applied forthis realization. Specify a system architecture with components and component interfaces.
7. Implementation: Develop a fine-grained software specification, select technologies for therealization and implement the specification. Evaluate the implementation to verify that thealgorithmic and conceptional framework is implemented correctly. Determine theperformance of the implementation.
8. Empirical Evaluation: Research if the created software system and the underlying algorithms
and concepts actually help to realize a real-time interactive application. Determine if thesoftware engineering process is positively influenced by concepts and software. Provide
feedback for a revision of theoretical and practical work.

23Instant Synchronization of States in Web Hypertext Application

Figure 1-1: Methodology of this thesis

1.4

Contribution

The contribution of this thesis to the current state of research and engineering is threefold:First, a synchronous method for accessing shared resources on the web is specified. The method
is inspired by bucket synchronization and operation pipelining approaches. No comparable
approach has been presented for the architectural and technological landscape of the web by
now. The method enables fair interactions of users, while fair refers to the timing of data
presentation and action processing. In addition to the theoretical work, a binary network
protocol and a text-based network protocol are specified for this method. Both protocols aredesigned to complement current and upcoming technology standards for the web.
Second, a novel client-server operation transformation procedure is introduced. In contrast to
state of the art approaches, the procedure enables clients to continuously originate and receive
operations without the need for sequenced access to the server. The control algorithm builds on
the theory of proven and established algorithms and algorithmic properties. New is the bulkprocessing approach for operation sequences that reduces the overall time required for state
convergence and enables the concurrent client access to the server. Novel is also to determine
the synchronization mode, i.e. pessimistic or optimistic, per operation based on a schema. The
operation transformation method introduced in this thesis is not limited to text. Instead it isapplicable to any state model that bases on a continuous namespace.
Third, a tree-based state model tailored to the needs of web engineers is specified. In contrast tocomparable approaches adjacent nodes can be ordered and unordered in this model. This option
enables a direct mapping between objects utilized in the modern application model of the web24

Instant Synchronization of States in Web Hypertext Applications

and the representation of a shared resource. In addition to the state model, operations for state
modification and a corresponding operation transformation function are provided.

1.5

OutlineThis thesis has eight chapters, a conclusion and an appendix. An overview of the contents isgiven in the following:
The Web as a Platform introduces the architecture and the application model for application on
the World Wide Web. With regard to the instant synchronization of resource states, standards
and techniques are introduced that serve as starting point for the work conducted in this thesis.
Resource-centric Interaction introduces state of the art principles for resource sharing in
distributed systems. Read replication and full replication techniques are identified as relevant in
the context of real-time interaction on the web and all algorithms that originated from that
research area are explained in detail, as well as their advantages and shortcomings.
Related Work introduces related research, community activities and software projects.
Advantages and disadvantages are explained and discussed with regard to the objectives of thiswork.
Instant Synchronization of a Shared State contains the fundamental concept of this thesis. An
operation pipelining approach for the exchange of user events between internet hosts is
described as communication scheme. Based on this communication scheme a genericoperational transformation concept for state convergence is defined.
Instant State Synchronization System (IS3) introduces the specification of an abstract systemarchitecture based on the communication scheme and the state convergence algorithm
introduced in the previous chapter. The specifications address client and server components, aswell as component interfaces.
Web Object State Model introduces a configuration for the generic IS3 that satisfies the needs of
WHAs. In addition to a partially ordered tree as state model, functions are specified for thecustomization of the operational transformation algorithm.
The Pulsar System describes the whole reference implementation for IS3 as a middleware for
web applications. The description includes specifications for the network interfaces, component
implementations, the robot-based customization model and the application programmer
interfaces.
Evaluation and Benchmark: The correct operation of communication scheme and stack
implementation as part of the reference implementation is shown in an evaluation. A benchmark
is documented that analyses the limits of the reference implementation in practical scenarios.
Case Study documents the result of an empirical evaluation. A case study is conducted to verify
the achievement of the thesis objectives by applying Pulsar in the context of software

25

Instant Synchronization of States in Web Hypertext Application

development projects. The first case addresses the realization of a collaborative rich text editor.
The second case describes the realization of an online adaption for the classic console game
Bomberman.
Conclusion summarizes the achievements and discusses whether the objectives were met. Also
this chapter includes a brief overview of future prospects.

26

Instant Synchronization of States in Web Hypertext Applications

2 The Web as a Platform
Although the Web started as a ubiquitous library for rich text content, it is one of the most relevant
application platforms today. This chapter comprises descriptions of traditional and modern
application models. Additionally, methods are presented for realizing low-latency bidirectional
communication based on this application model.

2.1

BackgroundIn the early 1990s Berners-Lee et al. started an internet application technology for the access toremote documents. In April 1993 the Conseil Européen pour la Recherche Nucléaire (CERN)
released the technology specification and its reference implementation for a hypertext
information system. The rapid distribution and the word wide emerging content for thistechnology soon formed a virtual network referred to as the World Wide Web [21]. In theremainder of this work the term web is used as short form for World Wide Web.

Figure 2-1: Web Architecture

The technology developed by Berners-Lee et al. bases on a client-server application pattern.
Documents to be shared are stored on the origin server. A document viewer called user agent
accesses these documents through the internet. Today the term web browser is the morecommon term for the document viewer. Throughout this work both terms are used. User agent
and origin server communicate through the Hypertext Transfer Protocol (HTTP) [22]. HTTP
realizes a request-response communication pattern. Solely the user agent is allowed to start arequest. The origin server can only respond to requests. Request and response message of HTTP
are text-based. The request contains at least the identifier of the document to be viewed. The
response at least contains a status code, a field indicating the length of the content and thecontent itself. A document identifier is encoded as Uniform Resource Locator (URL) [23], aformat which was later generalized as Uniform Resource Identifier (URI)[24]. The URL is not
only an abstract name; rather it has to be resolvable to the physical address of an internet host.
Berners-Lee et al. also developed a platform-independent transport format for document copies,
the Hypertext Markup Language (HTML), which has now reached pre-recommendation status inversion 5 [25]. Document copies in HTML representation are also called web pages throughout
this work. The innovation of HTML is the hyperlink. With hyperlinks the HTML syntax allows
referencing any other document available on an internet host implementing HTTP. The
reference has to be given as URL. When the user selects a hyperlink from a document in the User
Agent, the User Agent has to request the referenced document from its origin server and to show
the contents of the response.

27

Instant Synchronization of States in Web Hypertext Application

The basic architecture of the web is optionally extended with proxies and gateways, as depicted
in Figure 2-1. The gateway is introduced to cache documents in their HTML representation on
behalf of the origin server. Additionally, a gateway can be used to balance the request load
between multiple origin servers serving the same content, or to enforce security constraints. The
intention of the proxy is to cache documents on behalf of the user agent or the local network of
the user agent (e.g. an enterprise network). Additionally, proxies are used to implement content
filters (e.g. black list, white list).
Fielding et al. later generalize the notion ‘document’ as resource and introduce the term
representation for document copies [8]. A representation is thus a context-dependent snapshotof a resource state. Moreover, they introduce with Representational State Transfer (REST) a
formal model for methods to access resources through HTTP and add methods to write anddelete resources. The remainder of this work uses the terminology of Fielding et al.

2.2

Application Models

2.2.1

Traditional Application Model

With the quick growing size of content available on the web, means are required to concretize
requests and to individualize responses. Since the parameters for concretizing a request arecontent-specific, an inflexible extension of HTTP or the user agent is inappropriate. InsteadHTML is extended with so called forms, which represent graphical input elements. A special
submit button contained in each form terminates the user input. Once terminated, the user agent
takes the names and values of form input fields, encodes them as list of name-value pairs
according to [24], attaches this list to a prefix URL and starts a request to the just created URL.
Forms are thus nothing else than hyperlinks with placeholders for user inputs.
As a counterpart to forms, the Common Gateway Interface (CGI) [26] is introduced at the origin
server. CGI takes an HTTP request, in particular the URL, and translates it to the name of aprogram and a list of execution parameters for this program. The program is started while theprogram outputs are captured and forwarded as payload to the HTTP response. Figure 2-2
shows an example of a CGI program that simply adds two numbers. With the help of a form, theuser provides two parameters a and b. The parameters are encoded and attached to the request
URL. The origin server forwards the request to CGI. CGI parses the request and derives a
program name and execution parameters in a customizable way. The program is started withthe parameters and produces HTML encoded content as output. The content is tailored to therequest parameters. Also the CGI program could output HTML that again contains a form. As theexample suggests CGI programs may not only filter a number of static resources according touser parameters, but also generate data on demand. To create a coherent application, with alook and feel like desktop applications, a number of CGI programs can be chained to acontinuation.

28

Instant Synchronization of States in Web Hypertext Applications

Figure 2-2: Example CGI application

HTTP is stateless. To work with the same data in a number of succeeding requests (e.g. of acontinuation), these data have to be looped through from the last response to the next client.
Alternatively the data can be stored at the server temporarily and a reference to these data – aso called session identifier - looped through instead. Although commonly applied, the latter
solution is unacceptable with regard to the REST principles. The loop through of data however,is supported by the cookie, a special protocol feature of HTTP [27]. As alternative to cookies,
request parameters are used to communicate the context of a request.
Modern alternatives for server-site programs do not necessarily build on CGI, but the principleof connecting origin server and programs for the dynamic creation of content is the same. Some
representatives are PHP [28], Java Servlets and Server Pages (JSP) [29], Active Server Pages(ASP) [30], Ruby on Rails (RoR) [31] and the Google Widget Toolkit (GWT) [32]. A
comprehensive survey of recent platforms and frameworks for server-site programs ispresented in [33]. A peculiarity of modern CGI successors is the support for the modularizationof server-site programs according to the Model-View-Controller (MVC) software engineering
pattern. This basically postulates a clearly separation of the data to be presented (Model) fromthe presentation (View) and the application logic for selecting data and presentation dependenton user inputs (Controller). Views are templates (mostly HTML pages with placeholders), which
are only populated with data when the data are requested. Application frameworks like GWT go
a step further and allow software engineers to design a complete web application with a GUI

29

Instant Synchronization of States in Web Hypertext Application

framework for desktop applications, while performing the required mapping to web
technologies themselves.
In the remainder of the document the term web server is used denote the set of static anddynamic resources for one application on the origin server. The term web client is used to denotethe set of representations for all resources in the web server. For example, a CGI program adding
two numbers is part of the web server. The markup created by this program and shipped to theuser agent is part of the web client.
2.2.2

Extensions to the Traditional Application Model

The traditional application model of the web supports the realization of applications which look
similar to simple business applications for standalone computers. In the early days of the web,however, HTML was limited to the presentation of decorated text, images and tables. Graphic
elements (e.g. charts, directory trees), dynamic elements (e.g. video) or interactive elements (e.g.
games) were not supported. For that reason the company Netscape enabled its user agent tounderstand HTML markup for an active object, also called applet. Applets are precompiled
programs with an optional user interface. Comparable to images, they are served by the origin
server and are referenced from a web page by URL. When the user agent renders an active
object in a web page, it requests the program from the origin server, starts the program on theuser host and embeds the user interface of this program with the web page.
Obviously user agent or user host have to be able to execute the program. The Netscape useragent therefore requires the programs to be represented in Java byte code and the user host to
run a Java Virtual Machine (JVM). Support for embedded active objects is found in most useragents today. Successors of the JVM as execution environment are for example Adobe Flash
Player, Adobe Shockwave Player or Microsoft Silverlight runtime environment. The runtime
environments differ not only in the syntax of code they execute, but also in the capabilities they
offer. Flash and Shockwave are tailored to rich, interactive, graphical presentations including
audio and video. Silverlight aims at making the user agent a fully fledged platform for any kind of
application which was formerly found only on standalone computers.
Active objects pose a number of security risks for applications on the web. For example, the code
obtained from a web server can be used to access file system, peripherals and network interfaceof the user host during execution. Another critical point of active objects is their poor
conformance to basic ideas of the web. For example the code used to represent programs isencrypted or the parser code protected by copyrights and patents, which constrains the
openness of contents in active objects and thus the searchability.
2.2.3

Modern Application Model

The introduction of applets reveals a weak point of web pages and the traditional application
model of the web. Interactivity is bought with latency. Each user action that means a progress inthe continuation inherent to a web application requires the user agent to start a request and the30Instant Synchronization of States in Web Hypertext Applications

user to wait for the response. The answer to this weak point is to perform multiple succeeding
steps of the continuation at the client, i.e. to strengthen the role of the user agent in theapplication model [34].
Originally intended to create a connection between applets and the surrounding web page,
Netscape introduced a script programming language called JavaScript (JS), which is today
standardized as ECMA Script [35]. JS code is contained as source in a special markup element ofan HTML page or referenced as source by URL. The user agent interprets the code when it
renders the web page. Modern user agents also compile the code just-in-time and execute it
natively. In this work, the term JS runtime environment denotes the component of a user agent
that either interprets or compiles and natively executes JS code.
a: 1

RendererAdd<body><form>
click<input type="text" name="a"><input type="text" name="b"><input type="button" value="add" onclick="add()"></form></body>

Function: add
JavaScript
RuntimeEnvironment

User Agentb: 10

Result: 11<body>
Result: 11</body>function add() {var a = document.getElementsByName('a')[0].value,b = document.getElementsByName('b')[0].value;
document.getElementsByTagName('body')[0].innerHTML ='Result: ' + (parseInt(a) + parseInt(b));}

GET /calc/add
Content-Length:0
Connection: close

Origin Server

HTTP/1.1 200 OK
Content-Type: text/html
Content-Length: 420
Connection: close<html><body><script type="text/javascript">function add() {var a = document.getElementsByName('a')[0].value,b = document.getElementsByName('b')[0].value;
document.getElementsByTagName('body')[0].innerHTML ='Result: ' + (parseInt(a) + parseInt(b));}</script><form><input type="text" name="a"><input type="text" name="b"><input type="button" value="add" onclick="add()"></form></body></html>

Figure 2-3: Example JS application

The JS runtime environment exposes a number of objects to the JS code as global variables. Oneof them is an object named document. The document object is the root element of the so called
Document Object Model (DOM), today standardized in version 3 [36]. The DOM is a leaf tree
representation of the HTML page that contains the JS code. In this representation each markup
element is a node, while nested markup elements are child nodes. Starting from the document
object, the JS code can access and change each part of the HTML page by object methods andattributes. Changes, e.g. added nodes or modified text contents, are rendered and presented tothe user immediately in the user agent. Code execution is triggered by user events [37] such as
key presses and mouse actions on DOM nodes, or timer events. All JS events are collected in thesame queue. The queue and thus the event callbacks are processed sequentially. All JS function
calls are synchronous. Accordingly, no two functions access the same resource concurrently. The
JS language does not support parallel computing at all. Pseudo-concurrent processing has to be31

Instant Synchronization of States in Web Hypertext Applicationemulated with continuations and timer events. The tandem of DOM event observation and DOM
manipulation is also referred to as DOM Scripting.
The simplified example in Figure 2-3 shows the same use case as Figure 2-2, but is realized withDOM Scripting. An initial request to the origin server is replied with an HTML page containing JS
code in addition to the form. The code includes a function which reads the values of the form
input fields, adds them and writes the result to the DOM while replacing the form. The function
is first triggered when the user raises a click event on the form button. When the event
processing is finished, the DOM is rendered again and the result presented to the user.
DOM Scripting can thus be used to implement a number of successive use cases without request
to the origin server. Practical examples are the validation of form fields, the collection of data inso called wizards, or skimming through large data collections. The exclusive handling ofvalidation and usability use cases at the client reduces the number of requests an origin server
has to process per second. DOM Scripting moreover improves the responsiveness of the userinterface with regard to the user.

Figure 2-4: Yahoo user interface in 1996

Figure 2-5: Yahoo user interface in 2008

In parallel to the development of the modern application model, HTML is complemented withthe meta language Cascading Style Sheets (CSS). CSS defines how the user agent has to renderHTML elements to the screen (e.g. size, position, color, font, etc.). CSS and DOM Scripting
encourage web designers and software engineers to create new, appealing user interfaces forapplication on the web. The rapid evolution of computing hardware ensures that user agents canstill keep up with rendering and JS execution. Figure 2-4 shows the user interface of the webservice Yahoo in 1996. Figure 2-5 shows the same user interface 12 years later. In 1996 theservice bases on the traditional application model. The markup for the whole interface including
images has a size of some 9,000 Bytes. The 2008 version of the interface has a size of 450,000
Bytes, including images, CSS and JS code. Although this version bases on the modern application
model, requests to the origin server are still required, for example if the user wishes to follow a32

Instant Synchronization of States in Web Hypertext Applications

hyperlink. User agents cache contents like images and JS files referenced from a web page. In theworst case however, the presentation of a web page like the one in Figure 2-5 requires the useragent to request approximately ½ MB of data from the origin server. If the interface is broke up
into multiple components, i.e. CSS files, JS files and images files, as many requests to the origin
server are required. Even with a fast internet connection the user will experience the time forloading and rendering a web page as delay.
Modern user interfaces for application on the web are composed of multiple sections, (e.g.
navigation, main content, search, quick links, advertisement, etc.). In most cases a user action
results in the replacement of one section only. Consequently, there is no need to reload andrender the whole page. This observation leads to the introduction and standardization of a new
global JS prototype to the JS runtime environment, the so called XMLHttpRequest (XHR) [38]. An
instance of this prototype is used for one request to the origin server of the requesting JS code.
With XHR the application decides which events (e.g. caused by a user action) result in a new
request to the origin server and also handles the data of the response.
The interface of the XHR prototype includes functions and attributes to send requests, monitor
the request state and obtain response data. The application engineer has to decide whether toutilize XHR in synchronous or asynchronous mode. In the synchronous mode the function forsending the request blocks until the response is received or an error occurrs. In theasynchronous mode an application engineer has to provide a callback function, which is
triggered when the response is received. Sending is non-blocking in asynchronous mode. A
function that starts a request can terminate, the user interface remains responsive. The data of a
response can have any text format. JS runtime environments natively support parsing andprocessing of HTML, XML and JSON format today. JSON, short for JavaScript Object Notation, isthe minimal subset of the JS syntax required for the description of data structures excluding
functions [39].
Figure 2-6 depicts a simplified example for an XHR application. The example again adds two
numbers. The web client is initialized with a request to the calculator application. The HTML
markup in the response contains a JS function. The function is called when the user clicks to theadd button on the screen. First, the function reads the values of two form input fields. Then it
creates and starts an XHR to its origin server in synchronous mode. The web server includes a
CGI program that adds the two numbers. In this case the CGI program only returns the result of
the operation, but no markup. When the response with the result reaches the user agent, thefunction processing is resumed. The function reads the result of the CGI program from the XHR
instance, appends a label to it and adds the resulting text to the DOM. When the function
terminates the JS runtime environment tells the user agent to render the DOM again. The
example is chosen for its simplicity. In practice, requests to the web server are only used toaccess resources unavailable at the user agent, such as databases or special services.

33

Instant Synchronization of States in Web Hypertext Application

Figure 2-6: Example XHR application

The example reveals the movement of MVC design to the web client. Controller, a JS function,
and View, an HTML template, are shipped with the first response from the server. On demand of
the Controller the web server provides the Model via XHR. In principle, one initial request to a
web server is sufficient to initialize the web client for the entire user session, assumed thesession is not affected by external events (e.g. disconnection). All successive requests can behandled by the web client itself through XHRs. This extreme of web application is also called
single page application and marks the state of the art for web application engineering.
DOM Scripting, XHR and CSS do not fully exploit the possibilities offered by active objects such asapplets. The Web Hypertext Application Technology Working Group (WHATWG), the driving force
behind HTML version 5, aims at extending HTML, CSS and the JS runtime environment to close
this gap. The term Web Hypertext Application Technology is chosen to clearly distinguish the34Instant Synchronization of States in Web Hypertext Applications

efforts of the working group from those around the integration of third party technologies withthe web application model, such as Silverlight, Flash or JavaFX [40]. In the remainder of thiswork the WHATWG terminology is adapted to refer to web applications that exclusively utilize
HTML, CSS and JS. Such an application is called Web Hypertext Application (WHA).

2.3

Low-Latency Bidirectional Communication

The key requirement of resource-centric real-time interaction between two or more users is thenotification of changes to resources and consequently their representations with low latency.
WHA clients write to resources via XHR. When the client initiates an XHR, a TCP connection is
opened instantly if needed, and an HTTP request sent. The WHA server can accept the write
access when receiving the request and update the resource. The web application model,
however, provides no standardized means to notify the update to other WHA client thatrequested a representation of the same resource before. Under the name Comet the engineeringcommunity has documented three techniques to work around this drawback, i) frequent polling,ii) streaming, iii) long polling. Based on these efforts, a WHATWG spin-off drives thestandardization of a clean, long-term solution called WebSocket in the context of HTML5.
2.3.1

Frequent Polling

The frequent polling technique requires a WHA client to periodically initiate requests to the
WHA server. If the server has an update notification for the client, this notification is
piggybacked on the response. Ideally the polling interval is chosen short to prevent notifications
from being delayed while waiting in an output queue at the WHA server. However, the more
frequent the WHA client polls for notifications, the more likely are empty responses. As Figure
2-7 illustrates, updates to resources are requested at the server by separate XHRs. The figure
uses trapezoids to represent communication phases. The left flank of each trapezoid symbolized
the beginning of a request, the right flank the end of the corresponding response. Light-grey
trapezoids depict communication on behalf of the WHA server, dark-grey trapezoids
communication on behalf of the WHA client.

Figure 2-7: Comet technique frequent polling

Frequent polling is the most stable Comet technique, but also the least efficient with regard toresource consumption and latency. Each poll to an empty notification queue at the WHA servermeans overheads. Nonetheless, the polling interval has to be short in order not to delay

35

Instant Synchronization of States in Web Hypertext Application

notifications. If alternatives are not applicable, the polling technique can be improved by socalled guestimate patterns¸ i.e. meta information about the probability of new notifications or the
notification frequency.
2.3.2

Streaming

Streaming is the oldest and least reliable technique to deliver notification from WHA server to
WHA client. The technique builds on capabilities of HTTP 1.1 to control the underlying TCP
connection and transmit payload of initially undefined size. Additionally, a special layout
element in HTML is used, the iframe. Like a hyperlink, an iframe references another resource by
URL, but instead of causing the user agent to replace the currently shown representation on auser action, the iframe already contains this representation. Thus, iframes can be used to nest
representations of different resources. If those representations are provided as HTML andoriginate from the same host, the corresponding DOMs are integrated in the DOM of the root
page. To establish a stream the WHA client requests a prepared resource. This request is nothandled with an XHR instance. It is caused indirectly by adding an iframe to the DOM thatreferences the prepared resource. The WHA server responds with HTML, but omits the markup
to indicate the end of the page. Moreover, it tells the user agent to keep the TCP connection alive
and uses a chunked transfer coding on HTTP instead of transmitting the response payload as
block. After receiving the beginning of the response, the user agent remains in the state of
waiting for more data. Figure 2-8 depicts this characteristic with a continuous, shaded area.
updateWHA Client
User Agent

updateupdateidle time

Origin Server
WHA Server

notifynotifynotifynotifyFigure 2-8: Comet technique streaming

When there is a new update notification for the WHA client, the WHA server sends anotherchunk of HTML via the pending connection to the client. The chunk of HTML contains a JS code
segment with a call to a receive function, which was provided on initialization. The receivefunction works as callback function for the WHA client, while the parameters for its invocation
represent the actual data of the update notification from the server. The user agent parses andinterprets this chunk of HTML immediately and keeps the connection open. With every newserver notification the procedure is repeated. To request updates the WHA client uses XHRs.
HTML was not designed with regard to the streaming technique. As a consequence, thetechnique does not work properly in every user agent and may cause irritating side effects. For
example, some user agents do not process received markup or display a load indicator (hourglass as mouse pointer or progress bar) as long as a response is outstanding. Another problem is36

Instant Synchronization of States in Web Hypertext Applications

the monitoring of the connection. If the TCP connection carrying the streamed HTTP response isinterrupted, the user agent renders an error message to the terminating iframe instead of raising
an exception. The development of an error detection mechanism is thus complicated.
2.3.3

Long PollingLong polling is an improvement of frequent polling. The frequent polling technique requires the
WHA client to periodically request update notifications from a respective queue at the WHA
server. The WHA server responds immediately. If the queue is empty, the response is empty.
Like streaming, long polling utilizes the capability of HTTP to suspend a response. Still the WHA
client has to provide the opportunity to deliver a notification by requesting it, but if the queue isempty the WHA server sends a partial response with chunked transfer coding and tells the WHA
client to keep the underlying TCP connection open. The response is suspended until a new
update notification is sent to the WHA client. In contrast to streaming, long polling closes the
response when a notification is delivered. Immediately after the WHA client receives a
notification, it has to start another request to the WHA server. Thus, the WHA server
continuously has the opportunity to deliver notifications, as depicted in Figure 2-9. The requestsof the WHA client to the notification queue as well as the update requests are handled with XHR
instances. Like in frequent polling and streaming, update requests are handled separately.

Figure 2-9: Comet technique long polling

To prevent timeouts on the underlying connection or achieve a better load balance at the origin
server, the WHA server can close a suspended response after a predefined idle time and thus
provoke the WHA client to start a new request. Long polling is more robust than streaming. If
the TCP connection of a suspended response is lost, the corresponding XHR instance terminateswith a proper exception message. The WHA client then has the chance to analyze the cause andrecover the long polling scheme appropriately. Long polling can be seen as a trade-off between
robustness (frequent polling) and efficiency (streaming). Since long polling bases on suspended
responses like streaming, it also shares one of the drawbacks. Some user agents show a load
indicator to the user as long as a response is outstanding, hence, permanently in the case of longpolling.
2.3.4

WebSocket

In contrast to the Comet techniques, the WebSocket is not a work around for the existing WHA
technology landscape. The name stands for a new API to be introduced for the JS runtime

37

Instant Synchronization of States in Web Hypertext Application

environment and a new application protocol for bidirectional messaging exchange. The new API
realizes a JS prototype called WebSocket. An instance of this JS prototype basically provides afunction to send messages and a callback handler for the subscription to incoming messages. In
the current version of the recommendation draft [41] only text messages are supported, but theworking group also discusses a support for binary messages. In contrast to XHR, outgoing andincoming messages are not related (e.g. by a request-response pattern). WHA client and server
can send and receive messages at any time and without precondition once a connection isestablished. Only the WHA client can initiate the connection. While the discussions about the
WebSocket API have reached the final phase, the standardization of a network protocol serving
this API continues. The solution currently implemented by user agents supporting the
WebSocket API bases on a draft of Hickson [42]. This solution, however, is not a generalconsensus. The HyBi working group of the Internet Engineering Task Force (IETF) has the remit
to find a final solution. Their current draft is documented in [43].

38Instant Synchronization of States in Web Hypertext Applications

3 Resource-centric Interaction
Interactions in a resource-centric distributed system base on mutual write and read operations toshared resources. The operations are based on knowledge about the state of these resources. This
chapter introduces state-of-the-art-methods for the keeping synchronous the representations of a
resource state at multiple sites of a distributed application. The concept consistency is refined withregard to timeliness and fairness of synchronization.

3.1

Resource Access Paradigms

A declared objective of this thesis is to present a solution that integrates with the resourcecentric architectural style of the web. Accordingly, interactions of users have to be mapped toshared resources. The term resource can denote data, services or peripherals [44]. The term
resource is always used to denote a data resource. The four basic access paradigms for sharedresources in distributed systems are remote access, migration, read replication and full
replications [45]. Figure 3-1 explains these with the help of finite state machines. Each statemachine represents the user site. The state machines not only outline the local transitions, butalso when and which messages are sent and received by the site.
The remote access paradigm is most common and also the foundation for REST. The accessing
site does not maintain a full copy of the state of a shared resource, but rather a subset obtainedon reading from the resource. Reading requires sending a message and waiting for a responsewith the portion of the state requested, as depicted in Figure 3-1a). If the site intends to write to
the resource it also needs to send a message. A write operation is not completed until a message
with a corresponding reply is received by the site.
Figure 3-1b) shows the migration paradigm. Migration reads and writes locally, i.e. without
sending messages and waiting/blocking until a response arrives. The entire resource and theexclusive read and write access rights migrate from site to site on demand. Only a site whichholds the resource can read from and write to it.
The remaining paradigms in Figure 3-1c) and d) base on replication. In the initialization, the site
obtains a representation of the entire state resource. A read replication approach enables theaccessing site to perform any read access locally without issuing messages. If the site has towrite to the resource, a proceeding like in remote access is required. The site sends a message
and waits for an acknowledgement of the operation. Additionally, the site may be requested to
update the local copy of the state and acknowledge the update. A full replication approach
supports local writing in addition to local reading. Synchronization of the state copy is done
within a separate synchronization step which is decoupled from writing and reading, butinvolves sending and receiving of messages.

39Instant Synchronization of States in Web Hypertext Applicationa) remote access
init

start

b) migration← read⊆idle→ update⊆

wait
read

start

← shareinit→ update← update→ error → update⊆← write⊆
read

idle

migrate→ share

wait
write

write
c) read replication
startd) full replication← share

init

start

← shareinit→ update→ update→ update⊆

← ok
sync

→ update⊆

idle

read

sync

idle

read

← update⊆→ error→ update⊆← write⊆

wait
write

write
← outgoing message→ incoming message⊆ message addresses state subset

Figure 3-1: Basic access models for shared state

3.2

Consistency in Real-time Interactive Applications

The key objective the access paradigms is to keep the views to a shared resource consistent, i.e.
unify the state representations even though they reside at different sites. In the context ofinteractive applications, this process is referred to as state convergence. The term consistency
thus refers to convergent state representations of a resource and not the integrity of theresource itself. Remote access, read replication, and full replication allow multiple sites to accessthe same subset of a resource state concurrently, while concurrency and precedence are notnecessarily related to physical time. They can also be defined with respect to the causal relations
between accesses[46]. In the causal view of time, accesses are said to be concurrent if they are
performed in the same context. If one access is performed on a state that already reflects
another access, the first one is said to depend causally on the second one. Causal dependence isdefined as the inverse of precedence in logical time. The order of accesses is essential for state
convergence. If, for example, two sites share a state in accordance with the read replication
paradigm and both receive the same two differential updates to their replica of the state, bothhave to perform the updates in the same order. Writing to a variable first the value 5 andafterwards the value 7 or vice versa results in different final values for this variable. The order40

Instant Synchronization of States in Web Hypertext Applications

among the accesses of multiple sites to the same resource can be maintained through continuous
sequence numbers or timestamps taken from a global wall-clock time (e.g. realized with NTP[47]). Solutions explicitly addressing causal relation of accesses are logical clocks [48] andvector time. In any case the provision of an order index (timestamp, number, etc.) is required foreach access. Logical time stamps have the advantage that they also serve as reliable reference tothe current state of a site.
If two concurrent accesses are in conflict with each other they are said to be competing [49]. Fora reliable handling of competing accesses they have to be atomic or applicable in isolation interms of the ACID properties [50]. As described above, finally, a total order for all accesses isrequired throughout the distributed system. This can be realized with locks. Each site thus has to
wait for all previous accesses of other sites to be committed before it can access the sharedresource itself. The migration paradigm explicitly assumes locking. If concurrency is intended in
the first place, e.g. for responsiveness reasons, competing accesses can be rejected when theyoccur. The issuing sites have to try again in that case. An alternative approach to rejection is
inclusion. Inclusion is applicable if write accesses are not semantically exclusive. For example,
two competing write accesses, both intending to increase the value of a variable by one, can be
included to one write access increasing the variable value by two. Inclusion minimizes thenumber of rejections and rollback where required.
0Site 11

0Site 2

T1

1
Object at (0,0)
001latency
0

1

1

0
T2

View inconsistency

1

Figure 3-2: Consistency-latency tradeoff

Consistency here refers to the perceivable result of user interactions, the process of state
convergence, however, requires to trade off simultaneity against instantaneity [9, 51]. Today, thebasic means of communication for networked applications is the message. Interactive
applications have to fill the gap between message passing on the network and the abstract
interaction paradigm they provide to the user. The transport of a message between any two sitesof an application is characterized by the underlying physical connection of these sites. The
predominant factors affecting the transport time of a message are throughput and packet delay.
While the delaying effect of throughput can be limited by reducing the size of messages, thepacket delay depends on network congestion, hops in the routes realizing the connection andthe physical limits of the transport medium. From approximately 1ms in a local network the41

Instant Synchronization of States in Web Hypertext Application

average packet delay adds up to 150ms on a global connection. The reference value for delays in
distributed interactive systems is 300ms [52]. Thus, on wide area network connections there isalmost no tolerance if each transaction includes at least one message roundtrip.
Any access to a shared resource that requires waiting for a message has a potentially negative
impact on the perceived instantaneity of responses to user actions, claimed by the requirementsa) and b) in section 1.1. A solution for this drawback is to decouple access to the resource andmessage passing, as for example in the replication paradigms. This decoupling implies that the
representation of the state maintained at a site can diverge from the versions of other sites. Userdecisions made with regard to an old and possibly incorrect state have to be corrected, in theworst case by a cancellation, i.e. a write access is rejected. This behavior conflicts withrequirement c) in section 1.1. To minimize the number of cancellations and roll backs, theversions of the shared state have to be kept synchronous across the sites. The actual degree ofdivergence between the different representations of a resource state depends on the message
latency. Figure 3-2 shows an example. The movement of a game character is rendered with delay
to the screen on Site2. Any reaction of the user on Site2 is thus inherently late. The situation is
unfair. Alternatively Site1 could delay the rendering of the effect resulting from the local accessfor the time of message transport. The play out of the effect would be simultaneous for bothsites, but simultaneity is bought with a loss of responsiveness for the Site1. Consequently, a
trade-off between the requirements a) - b) and e)-f) of section 1.1 is needed.
In summary, for the maintenance of a consistent shared state in real-time interactive
applications the following properties are required:•

Ordering and Causality Preservation: preserve natural cause-effect order•

Competing Access: concurrent access of multiple sites to the same subset of the shared
state

•

Simultaneity of access effect play-out: preservation of temporal relations between
accesses of different sites•

Instantaneity of access effect play-out: unperceivable delay between access and play-outof the respective effect

The remote access paradigm requires the sending of a message for each access and is thus
unsuitable for distributed, interactive applications. The migration paradigm allows fast read andfast write access, but interactions of multiple sites require the mutual reservation and migrationof the state. Concurrent access is thus impossible and the migration of the entire state may
require the transport of large messages on each access. This violates the requirements a), b), e)
and f) in section 1.1. Accordingly the migration paradigm is not applied in the practice of realtime interactive applications. The replication paradigms represent the most suitable
compromise between responsiveness and interactivity, since access to the state andmaintenance of consistency are partially decoupled. The read replication paradigm is suitable42

Instant Synchronization of States in Web Hypertext Applications

for state sharing based on continuous consistency and simultaneous effect play out, as claimedby the requirements c), d), e) and f) section 1.1. The full replication paradigm satisfies
applications that require instantaneous responses to user actions, i.e. applications where therequirements a) and b) of section 1.1 have a higher priority than the requirements e) and f).
Implementations of the full replication paradigm base on the optimistic assumption that any
divergence in the local state is resolvable while synchronizing with the other sites. In contrast,
implementations of the read replication paradigm are pessimistic in this regard. For this reason
full and read replication solutions are also said to realize either an optimistic or a pessimistic
approach for state sharing in interactive distributed applications. In the following sections thebasics of all relevant optimistic and pessimistic approaches are introduced and discussed withregard to the appropriateness for WHAs. A user action causing a resource state change is
generalized as event. The term event is also used as synonymous to user action hereafter.

3.3

Lockstep Synchronization

Lockstep Synchronization (LS) is an implicit method for the realization of read replication. It
complements algorithms that manage resource access pessimistically. In LS the state of theshared resource advances step-wise. Each site has to issue exactly one event per step and must
not proceed with the next step before having received and acknowledged the events of all othersites for the same step. Since events are transported with messages, event delivery suffers fromnetwork induced delays. LS can thus be realized for decentralized and centralized systems. For
the latter case an example is depicted in Figure 3-3.
E1C

E5C

E3C

E2C

E4C

E1S

E6C

E2S

E3S

Figure 3-3: Processing events in Lockstep Synchronization

The request for a change of the state, for example in response to a user action, is not applied by
the issuing client site to the local instance of the state immediately, but first send as event to theserver. When all events are received at the server, the server aggregates the changes to the state.
All events of the same step are considered concurrent. An event from step s is said to precede an
event from step t if s<t. Competing changes are resolved or rejected by the server. For that
purpose they can be ordered and applied sequentially or they can be applied in parallel byutilizing transactional memory concepts [53, 54]. After aggregation and conflict treatments, the43Instant Synchronization of States in Web Hypertext Application

server forwards the changes as new events to the clients. A client that receives a server event
applies the changes to the local instance of the state, advances in processing and sends the next
event. The next event implicitly serves as acknowledgement for the last step.
LSS ensures the presentation of events to clients is more or less simultaneous. The event
messages are still exposed to different latencies depending on the network connection between
client and server. The performance of the entire system depends on the latency of the last
responding client. Additionally, the duration of steps can vary. This makes the fluent
advancement of the state along fixed length real-time intervals challenging. LS is thus
inappropriate for games based on fast user action and reaction. Client errors and resultant
missing events have to be caught with timeouts. Improvements of LS especially with regard tocheating in competitive user interaction on a decentralized setup are presented in [11].

3.4

Bucket Synchronization

An improvement of LS is Bucket Synchronization (BS) [55]. Sites do not wait an arbitrary timefor events like in LS, instead all sites advance processing in fixed length time intervals. BS isapplicable for centralized and decentralized systems. Figure 3-4 depicts BS by the example of adecentralized configuration.

Ei1

Ei2

Ei2+1

Ei1 , Ei2

Ei2+1

Figure 3-4: Processing events in Bucket Synchronization

A premise of BS is a global clock to synchronize the timing of the sites. Gautier et al. utilized
Network Time Protocol [47] for this purpose. The time is subdivided into intervals of fixed
length T. All events issued in the same interval i-Δ are marked to take effect at the end of interval
i. Thus, each site delays local events by Δ intervals to ensure the messages transporting these
events to other sites have reached their destinations on time for simultaneous play-out. The
delay factor Δ has to be chosen with respect to the connection with the highest message delay.
Message delay and jitter should be measured continuously. Events that do not reach a site ontime are scheduled for a later bucket. For simplification Figure 3-4 only depicts the events sent

44

Instant Synchronization of States in Web Hypertext Applications

from Site1 and Site2 to Site3, although both sites would need to send these events to each othertoo. The second event of Site2 also arrives at Site3 before interval i takes effect. Nonetheless, theevent is delayed at the receiver until i+1 takes effect.
BS satisfies simultaneity as consistency objective. Accordingly, the concept is suited for therealization of pessimistic resource sharing. Like LS before, BS is not explicitly designed tosynchronize representations of resources residing at different sites. Events that imply competing
write accesses either have to be processed sequentially or addressed with, e.g. transactional
memory concepts [53, 54]. Events that are received late at least at one site represent an
unaddressed problem in BS. An event for interval i that is received at interval i+1 could arrive
after new events have already been issued. In that case the new events do not causally dependon the late event and thus refer to an inconsistent state. In a centralized realization of BS a
server would process all concurrent events before an interval is due and forward the results toall sites on time. Late events could be moved to a later bucket. In this case the effect of an event
may differ from the one intended by the user, but at least it is the same at all sites and the state
representations do not diverge.
The simultaneous application of events makes BS suitable for use cases with competinginteractions among users, where the play-out time of an event, i.e. a user action, has a significant
impact on the experienced fairness. Stock price tickers or quiz games with a buzzer are examples
of such use cases. The drawbacks of BS in this regard are probability and distribution of earlyreceived events. An early received event is an event that is received at least one interval before
its intended interval. If a site is manipulated, users may obtain presentations of an early eventand react ahead of time. They thus have an advantage. Since the time an event is received
depends on the delay of the corresponding message, users with a less delayed connection always
have an advantage. In this case encrypted messages and mutual rating and voting on sites can beapplied to ensure a certain level of fairness [12].

3.5Time Warp

A straightforward optimistic approach for state synchronization is to immediately apply achange locally and to communicate relevant events to all other involved sites without any delay.
In the following this approach is called Event Forwarding (EF). EF results for n sites and only
one event per site in at most n2 messages to communicate these events. An improvement of EF
utilizes a centralized architecture (clients and multiple servers) to reduce the number ofmessages [56]. In this later Advanced Event Forwarding (AEF) approach a server collects all
events, summarizes them and forwards one event to each site. This limits the number ofmessages exchanged in worst case at the same time among n sites to 2n. AEF can additionallyfilter the events forwarded to each site by relevance. The relevance is determined by the vieweach site maintains for the resource state. Only events about changes of the state subset that iscurrently part of the view are forwarded. For example in a distributed computer game only45

Instant Synchronization of States in Web Hypertext Application

those events could be relevant that affect the current room of the user character. Event filteringresults in smaller message sizes and less processing load at each user site.
Even if EF and AEF ensure that all messages sent from one site are received at any other site in
the same order, they respect neither the causality of events across sites, nor competing changes
to the state. They are thus only applicable if the subsets of the shared state changed by each site
are disjoint. The basic optimistic approach that respects event causality and competition is Time
Warp Synchronization (TW) [57]. TW is an early, decentralized mechanism and designed for
multi-processor as well as networked, distributed systems. Changes to the state copy are
executed in TW immediately when events are received. If an inconsistency is detected, forexample caused by the out-of-order application of events, a state replica is rolled back to the last
known consistent state and all subsequent changes are applied again in the correct order.
A state in TW is represented as a set of variables. These variables are modified by actions. All
actions originated by the same site at the same time are summarized as one event. For usage
within a distributed system, each event is shipped with one message. TW is based on sequentialconsistency. The order of events throughout the system is preserved by a concept Jefferson calls
virtual time. In principle, this virtual time and all implications for the relations of events arederived from Lamport [46]. Therefore, events are not only annotated with sender and receiver
name, but also with a timestamp in one-dimensional, logical time. The timestamp represents themoment the event should take effect at the resource and thus any replications. Following
Lamport, the execution of an event stamped with a time later than the current local time at thereceiver results in the correction of the local time to the time of the time stamp. The next locallyissued event increases the local time by one and the corresponding message is sent with the newtimestamp.
Site1

E1

Site2

E3

E2

E4

Site3

E5

Send
Processing
State Snapshots

Processing E1
SAProcessing E2
SB

Processing E4
SC− E5
Processing E3

Processing E4SDSEroll back to SC and send undo for E5

Figure 3-5: Processing of events in Time Warp mechanism

Figure 3-5depicts the processing of events at the receiver by the example of Site3. Normally, allreceived messages are collected in an input queue and sorted by their timestamps in ascendingorder. The events in the queue are processed after they arrive as soon as the site is idle. Even if
the event timestamp suggests its causal dependence on an as yet unreceived event the46

Instant Synchronization of States in Web Hypertext Applications

processing is not delayed. However, all events remain in the input queue even after being
processed in case a roll back is required. For the same reason a snapshot of the current state ismade before the execution of any event.
An event is considered late if it carries a timestamp which is before or equal to the current
virtual time at the receiver. If a late event arrives, such as event E3 at Site3 in Figure 3-5, thesystem jumps back to the last consistent snapshot of the state, rolls back the input queue
accordingly, inserts the late event and (re)applies all events in the input queue starting with the
newly inserted one. Two subsequent events do not have to be causally related, but only theconsequent rollback ensures the convergence of states across all sites.
The complexity of a roll back increases if the site that has to perform the roll back had alreadysend events itself based in the incorrect state. For example Site3 in Figure 3-5 already sent E5
before recognizing an inconsistency. For this purpose, each site maintains an additional queuewith undo messages for all messages it sent. When an out-of-order event is received that reveals
an inconsistency, the undo messages stamped at a later time are sent immediately.
A site receiving an undo message has to delete the corresponding message from the input queue
if the event has not yet been processed. If the contained event was already processed, i.e. theactions were applied to the local state, the site has to perform a rollback to the last state
snapshot before the message to be undone was applied. This eventually includes the sending of
own undo messages. Although the cascaded undoing of events does not result in live- or deadlocks, it may result in a considerable numbers of messages communicated among the sites.
Events originated between a virtual time and the moment of a rollback is required are discarded
like event E5. While in use cases like games a rollback could be experienced as a minor skip, thedisappearance of previously typed characters or drawn lines in serious office applications could
be critical. Jefferson argues that most undoes are performed before an event is processed, i.e. aslong as the event is in the input queue. However, this only holds if the processing of an event
takes considerably longer than its transport between any two sites. The rollback is the more
likely default case if utilizing TW on wide area networks.

3.6

Trailing State

Cronin et al. introduced in [58] an improvement to Time Warp and called it Trailing State
Synchronization (TS). TS maintains a delayed, consistent state that is used to patch the state
presented to the user if needed. TS does not require rollbacks and corresponding undo
messages. Additionally, it reduces the memory load caused by the state snapshots of TW. TS is
designed for decentralized systems. Nonetheless, it is applicable in centralized systems too,
while the central instances only serve as event hubs but do not have to process events
themselves. The state representation in TS is a usually a set of unrelated variables or a set ofobjects with object variables. The notions of action, event and message are the same as in TW.

47

Instant Synchronization of States in Web Hypertext Application

Also the ordering of events is ensured by logical clocks and timestamps on the messages
communicated between the sites.
The central concept of TS is to maintain at least one copy of the application state that is
intentionally delayed, the so called trailing state. All locally originated and received events are
instantly applied to the main state, the state rendered to the user. Additionally these events arequeued and applied with a fix delay to the trailing state. This concept is depicted in Figure 3-6. If
an event like E3 arrives that causally precedes events waiting for application to the trailing statesuch as E4 and E5, then E3 is scheduled for application to the trailing state before the events
already waiting. When E3 was applied to the trailing state, an inconsistency to the rendered stateis likely. Instead of rolling back events, all events in the queue waiting for application to thetrailing state are applied immediately to the trailing state and the resulting state becomes thestate rendered to the user. In practice, TS can utilize multiple trailing states with different delays
to the rendered state. That way, very late events can still be processed, while inconsistency at atime close to the logical time of the rendered state can be fixed with less processing effort.
Cronin et al. tested the TS in very demanding multiplayer network games and found that mostpatches of the rendered state are not perceived by the users. Nonetheless, patches may
invalidate local user actions that were only applicable in an inconsistent local state.
E1

E3

E2

E4

E5

Figure 3-6: Processing of events in Trailing State

3.7

Operational Transformation

Operational Transformation (OT) is an optimistic approach for the synchronization of state
copies in groupware systems. In particular OT is designed for real-time collaborative
applications which allow multiple users to concurrently edit the same text document. OT
systems monitor the actions of users such as insertion or deletion of letters. Actions are
represented as operations which remote sites have to apply to their local state instance in orderto achieve the same state as the originating site. An operation is in principle a parameterized48

Instant Synchronization of States in Web Hypertext Applications

function invocation. For example, the operations O1=delete(1,”a”) and O2=insert(3,”x”) transforma state “abcd” into the state “bcxd”. The first parameter of the operations refers to the offset in
the text; the second parameter contains the character to modify. If all sites in Figure 3-7a) startfrom the same initial state and apply the operations O1 and O2 in the same order, they should
obtain the same final state. Since OT is optimistic, both operations are applied to the state
instance of Site1 before they are sent to the other sites.

O1

O1

O2

O2

Figure 3-7: Preceding and concurrent operations

If in contrast O1 and O2 are issued concurrently like in Figure 3-7b), Site1 would obtain the final
state “bcxd” while Site2 and Site3 would obtain “bxcd”. Both operations are competing in thiscase and their order of application results in different final states. Most OT implementations
utilize logical clocks [48] and vector times to maintain a global order of operations. Total orderis achieved by additionally introducing priority rules, which for instance order concurrent
operation by the indices of the issuing sites. Applying operations in the same order at any site
however, is not necessarily sufficient to preserve the intention of users. Operations waiting for
application also have to be adapted to the effects of competing operations. This process is called
inclusion transformation or forward transposition. For example, Site1 has to find an O2’ which
has the same effect as O2 at Site2, but after the application of O1. The intention of O2 was to insert
an “x” before the “c” in “abcd”. After the character “a” was removed the “x” has to be inserted at
position 2 to preserve the original intention. A correct transformation O2’ would thus beinsert(2,”x”). A transformation O1’ at Site2 would look like O1, since O2 does not affect the deletionat position 1.
A straightforward realization of OT is the GOT algorithm [59]. Operations are totally orderedand executed at all sites in this order. The operation processing is done like in TimeWarp
algorithm. Once a remote operation Onew is received, all locally executed operations logically
positioned behind this late operation are undone, Onew is applied to the state and the undone
operations included with the new one and redone. The correct redo however, requires a special
procedure. The inclusion of the new operation Onew to an undone operation Oi also has an impact
on the undone successor Oi+1 of Oi, which was either issued in awareness of Oi or latertransformed to reflect the effects of Oi. Thus, the effect of Oi has first to be excluded from Oi+1

49

Instant Synchronization of States in Web Hypertext Application

which results in Oi+1’, then Onew can be included in Oi to Oi’ and finally Oi’ included in Oi+1’. Thishas to be repeated for all undone and redone operations. The exclusion transformation, also
called backwards transformation, is the reverse of the inclusion transformation and a peculiarityof GOT and SOCT2[60].
The original idea of OT as realized in dOPT was to apply operations in the order they arereceived and to delay remote operations only until all causally preceding operations have been
received and applied. For this purpose, the order of including and applying any two concurrent
operations must not result in different states [61]. Ressel et al. formalize this property of the
inclusion as Transformation Property 1 (TP1) [62].
Definition 3-1: Transformation Property 1 (TP1)

For any two concurrent operations O1 and O2 the inclusion transformation function
transform has to satisfy the property:
transform(O1, O2) ≡ transform(O2, O1)
The property requires that the inclusion transformation preserve the relation of the effects of O1
and O2, independent from the transformation order. The practical consequence of this definition
is apply (transform(O1, O2), apply(O2, S)) = apply (transform(O2, O1), apply(O1,S)), where apply
evaluates an operation in a state and returns the resulting state. TP1 alone however, is proven to
be insufficient to realize OT correctly between more than two sites [60, 62, 63]. The reason canbe found in the priority rules, which are used to establish an order among concurrent operations
and complement the partial order provided by logical clocks. If sites diverge by more than one
operation in state, i.e. one operation is concurrent to two or more operations of another site, thestates may not converge.

O1

O2

O3

Figure 3-8: Concurrence of multiple operations

Figure 3-8 depicts an example. The operations O1 and O2 are concurrent, while O3 causallydepends on O1. The initial state at all sites is “abcd”, O1=delete(1,”a”), O2=delete(3,”c”) andO3=insert(3,”x”). According to dOPT O3 would be applied to the state without changes at Site1,
while both operations have to be included with O2 before its application. The final state at Site1 is50

Instant Synchronization of States in Web Hypertext Applications“bxd”. The same happens at Site3. Site2 in contrast includes the effects of O2 in the concurrent
operations O1 and O3. Neither O1 nor O2 are changed, so O3 and O2 refer to the same offset when O3
has to be transformed. If now a priority rule is used based on the site index, O3 could be logically
positioned before O2 and therefore bypass a necessary modification. The final state at Site2
would thus be “bdx”, which diverges from “bxd”.
An approach to prevent the above situation is to ensure a global order for concurrent
operations. SOCT4 utilizes a central sequencer for this reason [64]. The sequencer provides all
sites on demand with an operation number. The number is taken from a continuous sequence.
Before sending an operation each site waits until all operations with a lower sequence number
have been received, includes these operations into the operation to be sent and finally sends theoperation. The sequence numbers replace logical timestamps. Another solution for the above
problem is the introduction of a second property for inclusion transformations [60, 62]. Ressel
et al. formalize this as Transformation Property 2 (TP2).
Definition 3-2: Transformation Property 2 (TP2)

For any three concurrent operations O1, O2 and O3 the inclusion transformation function
transform has to satisfy the following property:
transform (O3, transform(O1, O2)) ≡ transform(O3, transform(O2, O1))
Like TP1 before, TP2 requires the inclusion transformation to be agnostic with regard to theorder of transformations across multiple steps. Practically TP2 claims:
apply(transform(O3, transform(O1, O2)), apply(transform(O1, O2), (apply (O2,S))) =apply (transform(O3, transform(O2, O1)), apply(transform(O2, O1), (apply (O1, S)))
Accordingly, the adOPTed algorithm bases on the idea to follow all potential orders for the
inclusion of concurrent operations [62]. For this purpose the algorithm requires maintaining an
n-dimensional interaction model with all these ‘paths’, where n is the number of sites. Theinteraction model is used to ensure all operations can be transformed in a context which equals
the context of their origination. GOTO and SOCT2 base on the idea of restoring the situation
where sites do not diverge by more than one operation in state and all preceding operation were
executed in the same order [60, 63]. Concurrent operations which satisfy this condition are said
to be context equivalent. The algorithms are similar to adOPTed, but require a site to explore analternative order of inclusion for operations only on receipt of an operation that was executed insuch an alternative context. Context equivalence is only required for transformation. Therefore
GOTO and SOCT2 successively recover the executed operations by an exclusion transformation –similar to GOT – and include the resulting operations in the order required for a safe
transformation of the received one. For example, when O3 arrives at Site2, O2 is excluded from O1’,
which is the version of O1 already applied at Site2. Afterwards O1 is included with O2 to O2’ and O2’
included with O3. O2’ and O3 are context equivalent.

51

Instant Synchronization of States in Web Hypertext Application

Compared to GOT the algorithms adOPTed, GOTO and SOCT2 require less rollback since they
make use of TP1 and TP2 and therefore perform better in practice. But while the algorithms are
fine, the transformation functions proposed in combination with them do not satisfy TP2 in allcases [65, 66]. Consequently, these transformation functions only work reliably in a setup with
two sites, unless workarounds such as tombstones are utilized [66]. In a centralized system, aserver can order concurrent operations uniquely and bypass the requirement of TP2. The Jupiteralgorithm is very similar to GOTO and SOCT2 [67], but the interaction model is 1-dimensional
only. Whenever a past operation is included with a recently received one, the past operation is
also transformed with respect to the new one. All later transformations are thus always
performed on context equivalent operations. If for example the interaction in Figure 3-8 werelimited to Site1 and Site2, while Site1 originates O3 too after O1, then Site2 is required to include O1
into the stored version of O2 and later transform O3 against the resulting operation O2’ in thestore.
OT is applicable to any data structure with directed order, including graphs and trees. Datamodels and transformation functions have been proposed for text with tree-layout [68] and theStandard General Markup Language (SGML)[69].

3.8

Differential Synchronization

An approach similar to OT is Differential Synchronization (DS). DS emerged from version control
systems in collaborative document editing and was not originally designed for interactive
applications. Normally, state instances at different sites are allowed to diverge for hours, but DS
approaches are also suitable for centralized interactive applications [70].
In contrast to OT, DS realizations do not monitor all user actions to derive inherent operations.
At fixed intervals the user version of a state, usually a text, is compared to its version of the lastinterval. The changes that have been applied by the user are isolated as differences. In addition
to each difference, meta data is collected which describes the context of the change in detail. The
context is supposed to help the receiver of a difference to find the position in text where thechanges have to be applied. For example, the context can include the text that was previously at
the same position, the text before and after a new text fragment or the number of charactersinserted.
The differences found per interval are sent to another user site. Since the other user may haveapplied changes in the interval too, the differences have to be reflected in the current version of
the state and the version of the last interval. The resulting modifications which update bothstates to versions that include the remote changes are called patches. After the patches havebeen applied, the changes performed by the user are identified and sent back to the other site asdifferences again. The patching process repeats at the other site.
If more than two sites are involved, a server can be used to organize the patching procedure[70]. If the interval chosen for deriving differences and applying patches is short enough, DS

52

Instant Synchronization of States in Web Hypertext Applications

applications are perceived as being distributed interactively by the user. DS realizations do notnecessarily rely on timestamps. The context of a difference is sufficient to correctly patch a state.
However, the text context alone may not be sufficient to create a correct patch. Especially ifstates diverge too much, additional information about user intentions and semantics ofdifferences is required. For this reason DS is also combined with OT [71], while theirimprovement is the subject of ongoing research.

3.9

Discussion

Pessimistic synchronization approaches delay local events artificially, but ensure with small
variations simultaneous play out of events at all sites. LS and BS are thus appropriate solutions if
simultaneity of events is a higher priority than instantaneity of local events. This is usually thecase if an advance in time also means an advance in interaction. Trading or gaming applications
are examples for corresponding use cases. LS and BS prevent user perceivable roll backs, since
all concurrent events are processed at once before playback. The pipelining of BS has over LS theadvantage that it does not block for the time of a step. BS thus satisfies the requirements c)-f) insection 1.1 and is especially suited for competitive user interactions.
EF and AEF are optimistic approaches, but since they are not really suited for concurrent write
access to the same state they are inappropriate for the realization of read and full replication
systems. TW and TS are agnostic with regard to user intention. Events are applied in total global
order at all sites. Virtual time only ensures partial order. The total order is obtained byartificially ordering concurrent events, e.g. by site indices. However, concurrent events could
have a different appearance if they were issued in awareness of each other.
In TW local operations are even undone without replacement once a late operation has to becaught up. Users experience this undo as removal of their actions. Such a removal may besatisfactory in games, but not in collaborative editing use cases. TS could benefit from thefindings of DS and advance to a suitable approach for collaborative interaction. However, DS
cannot resolve inconsistency reliably, so a combination of DS and TS would require an extensive
evaluation to find out whether both approaches actually compensate the shortcomings of eachother or not.
Compared to TW and TS, OT has the advantage to not require the maintenance of trailing states,
state snapshots and the execution of explicit patches or rollbacks. The transformation ofoperations is isolated from the actual state at site and only affects the operation parameters.
Without the need of TP2, OT realizations are also reliable with regard to state convergence. OT
thus satisfies the requirements a)-c) in section 1.1 and is well suited for collaborativeinteractions. For real-time interactive applications with mixed-use, collaborative or competitive
cases, a combination of OT and BS is therefore the most promising approach. Such a combination
could trade off between optimistic and pessimistic synchronization with respect to the current

53Instant Synchronization of States in Web Hypertext Application

operation context. The requirement g) introduced in section 1.1 has to be addressed by an OT
tie-breaking rule that is balances the different intentions of interacting users.

54

Instant Synchronization of States in Web Hypertext Applications

4 Related WorkIn the following sections recent efforts in porting state replication techniques to WHAs are
introduced and discussed. The introduction starts with theoretical efforts, continues withmiddleware solution and tools and ends with entire software frameworks comparable to the one
resulting from this work. The chapter highlights positive aspects, but also identifies inadequacies.

4.1

Theoretical Efforts

WHA Technologies form a flexible platform for the seamless adaptation of most algorithms andconcepts known from parallel and distributed computing. Accordingly, also the state of the art
about optimistic and pessimistic synchronization of resource representations (i.e. replicatedobjects) is applicable to this platform with modifications.
In the research area of OT these modifications mainly address the centralized architecture, thepolling-based link between user agent and origin server, as well as the scalability needs ofapplications on the Web.
Related work in the context of applying OT to WHA [72-74] bases on HTTP as sole available
communication protocol. A necessary design objective is thus to minimize the number ofmessages exchanged between user agent and origin server. The approach chosen other authors
is to buffer user operations at the client and send them as sequence to the server in predefinedintervals. Operations of other clients are piggy-backed on the response from the server.
Differences among the related approaches can be found in the processing of operations at theserver. While the work of Wang et al. [72] and Shen et al. [73] is based on a sequential handlingof clients, Shao et al. [74] process messages in intervals. In [72] a client is not allowed to send
new operations until the server has explicitly acknowledged a previously sent sequence. At any
time the server processes only operations of one client. All operations are collected in a central
history buffer. When an operation sequence arrives at the server, it is first transformed against
all concurrent operations in the history buffer and then appended at the end of this buffer. The
client receives as immediate response the list of concurrent operations from the history buffertransformed against the recently sent operation sequence. Individually transformed operations
for clients are not stored. The acknowledgement mechanism ensures that a client always sends
operations directly causally dependent on the last operation received from the server.
The maintenance of only one history buffer saves physical resources at the server and thus has apositive impact on the scalability as argued in [72]. For each client, the communication ofoperations appears as two-way exchange with the server. Instead of a vector timestamp per
operation, a client references to the last operation obtained from the server to indicate where tocontinue in the next request. This kind of causality indicator keeps the messages exchanged
between client and server short. A drawback of this algorithm is the loss of a temporal relation

55

Instant Synchronization of States in Web Hypertext Application

between operations from different clients. If requests of clients A, B and C arrive at the server
concurrently and are served in the order A, B, C, then A will get the operations of B and C with adelay, B gets the operations of A immediately and the operations of C with delay, and C gets theoperations of A and B immediately. These variations can lead to irritations in collaborative
editing, especially if the users work on the same part of text with different intentions.
The concept and the algorithms of Shen et al. [73] equal the work of Wang et al. [72] in mostnoteworthy details. While Wang et al. documented their work in the context of the software
project Google Wave, Shen et al. provide the descriptions with sophisticated formalisms.
Shao et al. abstain from a strict sequencing of client accesses and instead introduce server
timing. The server continuously receives messages with operation sequences from all clients andbuffers them in input queues. Operations from the input queues are processed at predefinedintervals, the results buffered in output queues for the clients and piggy-backed on the responseof the next client requests. The causal relations of operation are also restored by a reference tothe last operation received. The server appears to the clients as another client. Batch
transforming of concurrent operations from different clients preserves the temporal relations ofoperations experienced by the user. For example, concurrent operations from sites A and B are
played out simultaneously at site C. This is a clear advantage over the sequencing-based
approaches in [72, 73]. The need for input and output buffers represents a drawback. Although
the buffering expense growth linearly with the number of clients, the server has to maintain thestate of the communication session for each client. The need for session management at theserver complicates load balancing in large-scale applications.
Final StatePathB ,1x

PathB , 2yOAOCInitial StateOBz

Figure 4-1: State space and transformation paths

If several users edit a document at the same time they produce concurrent operations andtemporarily reach non-converged local states. This aspect is shown in Figure 4-1. Three clients
A, B and C start at the same initial state, create two operations each and reach the intermediate
states x, y and z in state space. To enforce the convergence of state copies, each client has toapply transformed versions of the remotely originated operations. As Figure 4-1 indicates,
operations can be transformed and applied in different orders. Each order is a transformation

56

Instant Synchronization of States in Web Hypertext Applications

path in the state space. Figure 4-1 highlights two of four possible transformation paths for theoperations of A and C with respect to the state of B. When operation sequences of multiple
clients are transformed, the server has to select an appropriate transformation path for each.
The OT control algorithm used in [72] and [73] bases directly on the findings of Nichols et al. in[67]. Nichols et al. take advantage of a central component all operations have to pass. They use
the server to enforce a global order for all operations. The global order prevents two clientsfrom receiving two operations in different orders and thus makes TP2 unnecessary. All
operations can be transformed along the same path at all sites.
The OT control algorithm realized by Shao et al. bases on theoretical work of Li and Li [75]. Li
and Li demonstrated how challenging the achievement of TP2 for inclusion functions is. They
proposed a solution which avoids critical transformations by deriving transformation conditions
from the operation history and establishing the transformation path with respect to these
conditions. The work of Li and Li emerged from a multi-peer environment without a central
point for the enforcement of a global order for operations. WHAs however base on a centralized
infrastructure. The advantage of the algorithm proposed by Li and Li over the simpler algorithmof Nichols et al. in the application context is marginal. Using the same transformation path for all
clients as in [72] and [73] rather reduces the number of transformations required for each client.
Shao et al. do not limit the state model utilized in their work to character, word or token
streams, as Wang et al. and Shen et al. Nonetheless, the algorithms of these two should also be
utilizable for any data structure that can be mapped to a linear address space (e.g. arrays, trees).
The work of Fraser in the research area of DS [70] was conducted with explicit focus to the web.
Based on predefined thresholds (i.e. timeout or character count) the local text copy is analyzed
for differences at the web client and the results sent via XHR to the web server. From responses
to XHRs the web client obtains patches for the local text copy. The theoretical results of Fraser
are complemented with a number of programming libraries and tools for use in WHAs. Thanks
to this practical support the algorithms of Fraser have been adopted by a number ofapplications, as the next section will outline. Although DS is an optimistic approach it is notprimarily suited for the instant communication of state changes as already argued in Chapter 3.
Documentation of theoretical efforts on porting TW and TS to the web has not been found.
The only pessimistic synchronization technique that reached the web by now is STMS. In [76]Noel describes an extensible software transactional memory approach which is also suited for
application in WHAs. With XHRs transactions are send to the server and results as well as copies
of updated memory portions transported back to the web client. Pessimistic synchronization
techniques that focus on simultaneous event play-out have not yet found the way to the web.
This is probably due to the lack of support for instant delivery of server generated messages in
the pre-WebSocket era.

57

Instant Synchronization of States in Web Hypertext Application

4.2

Middleware and Tools

Motivated by the business prospects of real-time applications on the web, since 2006 theengineering community has produced a number of software solutions for message passing
between web clients, distributed publish/subscribe in web applications and object replication
between web server and web clients. The innovativeness of these solutions can be found in theway of abstracting the technological realities to provide APIs for well-known communication
patterns.
The communication pattern most often reflected in software solutions for the web today ismessage passing. Relevant representatives are CometD [77], Socket.io [78], Strophe.js [79],Kaazing [80] and Jwebsocket [81]. CometD, Socket.io, Strophe.js and Kaazing primarily bridge
differences in the availability and implementation of communication APIs in different browsers.
For example, they implement several of the push techniques introduced in Chapter 2 as well as
WebSocket support, and select the most appropriate communication method at runtime.
Jwebsocket is based on the WebSocket API only. In all solutions the software engineer programs
an application against a unified, proprietary interface. CometD, Socket.io, Kaazing andJwebsocket are complemented by a backend part. CometD, Socket.io and Jwebsocket provide
server implementations compliant with Node.js and Java. Kaazing includes a gateway whichmaps messages to technologies more common in server programming, such as XMPP and JMS.
Stophe.js is a client-only software library which implements BOSH [82], an XMPP binding for
HTTP. Stophe.js has to be used with either a BOSH-XMPP gateway or BOSH compliant XMPP
servers.
All named solutions are extendable and in addition to the basic message passing pattern the
support publish/subscribe communication patterns in all facets of [14]. Although event channels
are a foundation for synchronization techniques in object replication, real support for replicatedobjects is out of scope for cometD, socket.io, strophe.js, kaazing and jWebsockets.
Software solutions supporting object replication on the web are XSTM, Google-diff-match-patch(abbreviated as GDMP in the following) [83] and Jinfinote [84]. XSTM is software transactional
memory implementation. A JS library enables web application engineers to create transactions
at the web client and send them to the server to be committed. A strength of XSTM is the wide
platform coverage. Implementations are, for instance, available in Java, .Net and Objective C. The
theoretical foundation is presented in [76]. GDMP implements the DS algorithms of Myers [85]and thus is tailored to text objects. GDMP does not include a solution for the communication
with a backend and is limited to a number of JS libraries for text processing. The integration withthe sites of a web application has to be done by the application engineer. Jinfinote is a JS
frontend for the OT library and tools in the Infinote package [86]. Jinfinote is seamlessly
integrated with any WHA that requires collaborative text editing. According to available
descriptions, Infinote implements the OT algorithm of Ressel et al. [62] although it utilizes

58

Instant Synchronization of States in Web Hypertext Applications

centralized architecture. A TP2 hard inclusion function is not documented. GDMP and Jinfinoteaddress plain text only. Both lack considerations about rich text objects.

4.3

Software Frameworks

While this thesis was being prepared, two holistic solutions for the fast realization of real-time
interactive WHAs emerged. The first is Google Wave [87]. Originally introduced as a new service,
the software is today available under open source license from the Apache Foundation. The
second is IBM Cooperative Web Framework (CoWeb) [88]. CoWeb is available under open
source license today from the Dojo Foundation.

Figure 4-2: Architecture of Wave

Figure 4-2 outlines the software architecture of Wave. Basically, the Wave Server maintains a
number of sessions. Each session reflects the communication of a group of users. Users may
create, collaboratively edit and delete documents within a session. Documents can be ordered,e.g. to form a message thread. Wave Client and Wave Server are connected by a virtual,bidirectional message channel which is realized with the techniques introduced in section 2.3.3.
The message exchange is used for the realization of the OT concept described in [72]. The
documents of Wave sessions are the rich text objects to be replicated.
Wave is a software framework and application platform. Applications created with theframework require the Wave platform as runtime environment. Framework and platform,
however, not only enable novel collaboration use cases but also limit the design andpresentation options for WHAs. The Wave platform has a user interface for the presentation of
Wave sessions at the user agent. This user interface is strongly coupled with the Wave Client andsupports a number of use cases from collaborative editing of rich text to search. Using the Wave
Client directly from a WHA client is not envisioned. WHA clients have to be designed as layout
elements for a presentation within documents of a Wave session. Such a layout element isreferred to as Gadget. A WHA client must not access the Wave Client and its data directly.
Instead, it can access data about the session it is utilized in, as well as a special associative array.
The associative array is distributed between all instances of the same Gadget and reflects a

59

Instant Synchronization of States in Web Hypertext Application

shared Gadget state. The array is synchronized instantly between all gadget instances on an
update. Concurrent write operations to the same field are serialized at the server. The value of afield always reflects the value of the last update. Combined updates of multiple fields substitutetransactions. The WHA client representing a Gadget cannot read from or write to the documentsof the session it is utilized in. For that purpose the WHA engineer has to provide a software
agent, called Bot in Wave terminology. The Bot has its own life-cycle and is executed in a
dedicated runtime environment (Bot RE), which is attached to the Wave Server. In contrast to
the Gadget, the Bot can listen to changes in Wave documents, create documents and modify
document contents. The Wave Bot Interface provides the Bot with the same options as the Wave
Client does for the user. Additionally the Bot can access several communication interfaces, forexample to contact a WHA Server in a proprietary way. A Bot, however, has no means tocommunicate directly with a Gadget from the same WHA.

Figure 4-3: Architecture of CoWeb

In contrast to Wave, the CoWeb framework does not tie an application down to a special
platform. WHAs are rather developed around CoWeb as depicted in Figure 4-3. The basic
components are still similar to their Wave equivalent. The CoWeb Server manages collaboration
sessions, where a session groups a number of shared objects. Through a message passing
channel realized with Cometd [77], a CoWeb Client sends operation requests to and receives
updates from the CoWeb Server. CoWeb generalizes documents as named collections. A
collection can contain characters and tokens as well as any object. A rich text document is, forinstance, represented as a collection of tokens. A shopping list is represented as a collection of
objects describing goods. The OT algorithm to modify collections is not documented. In addition
to collections, CoWeb directly supports the synchronization of named objects within a session.
The algorithm to synchronize attributes of objects equals the algorithm that Wave utilizes tosynchronize the associative arrays representing a Gadget state. CoWeb does not support thetransactional modification of multiple object attributes at once.
A WHA Client embeds the CoWeb Client like any other JS library. The CoWeb Client Interface
provides broad access to session life-cycle management, session data and even the WHA Bots

60

Instant Synchronization of States in Web Hypertext Applications

attached to the CoWeb Server. This Bot concept is very similar to that of Wave, except that a
WHA Client and a WHA Bot can communicate directly via a request-response pattern. This
peculiarity makes a WHA Server obsolete as a separate component in most use cases. However,
the CoWeb Server does not provide any other interface a WHA Server could use to accesssessions or session data, e.g. to store them persistently or export them. Such interfaces would
have to be realized with Bots.

4.4

Summary

In section 3.9 a combination of OT and BS is identified as appropriate to cover a broad range of
online interaction use cases. With OT as algorithmic base Wave and CoWeb reinforce thisconclusion. Since both solutions are tailored to cooperative work use cases, they do not addresscompetitive interactions as supported by BS algorithms.
The adaptation of OT algorithms for applications on the web is quite advanced. Lessons learned
from solutions for mapping full-duplex message passing to a request-response based
communication link like CometD and Socket.io simplified the porting of state-of-the-art OT
algorithms. OT libraries like Jinfinote serve as notable proof for this development. The efforts ofWang et al., Shen et al. and Shao et al. bring recent findings in OT theory to the web. Although thealgorithms of Wang et al. and Shen et al. are well tailored to the engineering practices for WHAs,
their strict sequential processing of client requests breaks the temporal relations of operations.
Users may have problems understanding which operations are reactions to theirs. Shao et al.
propose a bulk transformation of operations from different clients at fixed-length intervals. Thisapproach basically ensures preservation of temporal relations. The synchronization of theserver interval with the client intervals would further improve this. Their transformation
algorithm uses transformation paths individually computed per client. A performancecomparison to an algorithm for transformations along a common path is lacking.
An adaption of BS algorithms for WHAs is not documented. A possible reason is the latencyprone communication of the pre-websocket era.
The software frameworks of Wave and CoWeb, the architecture as well as the component
interfaces, follow the same, almost obligatory pattern. The strong coupling of Wave to theintegrated platform however, makes Wave the less appropriate choice for the development of astandalone cooperative work application. The missing support for communication between
client-site and server-site extensions (Gagdets to Bots) emphasizes this point. CoWeb supports
the communication of WHA client and WHA server surrogates (Bots) by shared objects and arequest-response mechanism similar to legacy HTTP communication. Also CoWeb is not limited
to the synchronization of text like Wave. Shared resources are either treated as simple objects(primitive types and associative arrays) or collections of simple objects. OT operations like
‘insert’ and ‘delete’ are applicable to any collection. Missing is the support for the transactional
modification of multiple objects attributes at once. Also CoWeb does not support custom data61

Instant Synchronization of States in Web Hypertext Application

models for shared resources, custom operations and custom inclusion functions. Software
engineers thus have to map their required data model to the available data model if at all
possible.

62

Instant Synchronization of States in Web Hypertext Applications

5 Instant Synchronization of a Shared State
This chapter describes the concept of the thesis. It introduces a communication scheme forcommunicating changes to a shared resource. Also the chapter contains algorithms for the
resolution of conflicts among concurrent operations, including definitions of basic terms andconcepts.

5.1

Overview

The intention of the system proposed here is to support an application engineer in realizing realtime interactive applications. Ordering and causality preservation, competing access, simultaneityof access effect play-out and instantaneity of access effect play-out are identified as relevant
consistency properties in a resource-centric environment in section 3.2. The properties
instantaneity and simultaneity cannot be achieved at once for the access effect play-out if thecommunication of the involved sites suffers from human-perceivable delays, as typical on theInternet. This peculiarity will be covered in the described system by two complementary
operation modes a software engineer can make use of for an application accessing a sharedresource in the context of an interaction. These modes define whether an access is issued in a
pessimistic or an optimistic context, i.e. a competitive interaction or a collaborative interaction.
The operation modes are:(1) Continuous convergence and effect simultaneity: Simultaneous play-out of effects
resulting from simultaneously issued actions requires all sites, even the site that issued
the action, to wait with the play-out until the last site is ready to do so. As a benefit,
effects of user actions can be played out in the same order at all clients and checked for
concurrency constraints before. Users experience the state to be convergent after theplay-out of any event. This operation mode satisfies the requirements a)-g) introduced in
section 1.1.
(2) Convergence on quiescence and instantaneity: The effect of a local user action isplayed out instantly. At this moment the site has no information about simultaneous andpotentially competing events from other sites. Accordingly, convergence cannot be
achieved until the system is quiescent; i.e. all messages have been delivered andprocessed, no more messages about user actions are on their way. Users experience thesystem state to be consistent when no other user is active. Intermediate states candiverge, to the extent that a particular state presented to the user at one site is neverachieved at the other sites. This operation mode satisfies the requirements a), b), c) andg) introduced in section 1.1.
Although both operation modes are fundamentally different, their combined use within the same
application makes sense if the objects comprising the application state have different
characteristics and constraints. An assisted browsing application, for example, can allow two

63

Instant Synchronization of States in Web Hypertext Application

users to collaboratively edit text in operation mode (2), while a shared mouse pointer they moveis synchronize under operation mode (1).
In the following, the system architecture, a suitable communication scheme for the interacting
sites and an algorithm to achieve convergence according to operation mode (1) and (2) areintroduced. The communication scheme realizes a BS approach. The algorithm that ensures state
copies convergences bases on the theory of OT. The rationale for BS and OT is provided in
section 3.9.

5.2

State Representation and Synchronization

The system introduced here bases on variations of the client-server paradigm to simplify the
integration with the existing web architecture and its ecosystem. In contrast to peer-to-peer
systems a centralized architecture constitutes a single point to supervise restrictions, security
policies and execute trusted application logic. This point cannot be bypassed without breaking
the application itself and is thus a reasonable requirement of a web application operator. From atechnological point of view a client-server architecture simplifies state convergence. Any
communication is limited to a message exchange between the two sites. No potentially late or
hidden messages have to be reflected in access ordering. The client-server paradigm does notprevent the distribution of the server, for example to scale the system.
The web architecture is designed to obtain the states of resources and mutually change resource
states. To cope with the consistency-latency tradeoff discussed in section 3.2 a hybrid
read/write replication paradigm is applied. The server maintains a resource state SLead (alsocalled lead state of the resource). All clients maintain copies of a subset of the lead state. A copyof such a subset is denoted SCopy. In case any non-resolvable inconsistency is detected in a copy,
the copy is replaced by the most recent version of the subset in the lead state.
Example 1: Set of numbers

Example 2: Tree

{a=5, b=8, c=10}

div
ul
li
hello
li
world
hr

Table 5-1: Examples for state representations

The state has to be representable by any set of uniquely addressable, discrete, interactive
objects, e.g. objects which can be changed by an action, but do not change themselves as afunction of time. The following examples show two possible state representations, a set of
natural numbers and a tree, such as used for the DOM. The objects in the first example are the64Instant Synchronization of States in Web Hypertext Applications

variables a and b, which can be addressed by their names. The objects in the second example are
the nodes of the tree, such as div, ul and li. The value of a node is addressable by its path in thetree, where div/ul/li[2]/ could refer to the second li node and its value “world”.
A user action is represented as an operation. An operation comprises a deterministic function
which maps a given state and a list of parameters to a new state, i.e. modifies the state of a
resource. Figure 5-1 depicts a strongly simplified example for the communication flow between
clients Client1, Client2 and the Server. The state representation used in this example is a set ofnumeric variables. Operations to change the resource state are defined by the two functions add
and mul in this example. The add function adds a constant to the value of a variable in the state.
The mul function multiplies the value of a variable with a constant and stores the result to thevariable. The server does not create operations itself, but all operations requested by clients arecommunicated through the server. The server does not simply dispatch operations, but may also
rewrite operations, for instance in the event of access conflicts between two concurrent
operations. In Figure 5-1 the operation add(a,5) is applied according to operation mode (1), theoperation mul(b,2) according to operation mode (2).
Figure 5-1 already points out two major differences to pure read replication: i) an update of thecopies initiated by the server does not transmit the entire copy, but only the difference to thelast copy sent to the client, ii) clients can apply changes to their state copy before sending themto the server. Property ii) is required to fulfill the operation mode (2), i.e. convergence onquiescence and instantaneity. The dotted line in Figure 5-1 denotes a moment when the system
is quiescent.
1
SCopy:= {a = 3, b = 5}

1
SCopy:= {a = 8, b = 10}

1SCopy:= {a = 8, b = 5}

mul (b,2)
Client12
SCopy:= {a = 3, b = 5}2
SCopy:= {a = 8, b = 5}2
SCopy:= {a = 8, b = 10}

add (a,5)
Client2

ServerS Lead := {a = 3, b = 5}

add (a,5)
S Lead := {a = 8, b = 5}

mul (b,2)
S Lead := {a = 8, b = 10}

Quiscence
Figure 5-1: State and operations

5.3

Communication Scheme

Simultaneity of event play-out, i.e. the effect of applying an operation to the user-visible state
requires the synchronization of clients. This synchronization has to respect the different

65Instant Synchronization of States in Web Hypertext Application

characteristics of the communication channels between client and server, in particular the(throughput-induced) latency of operations. The system proposed here utilizes an adaptation of
the bucket synchronization algorithm. Bucket synchronization is a more appropriate choice thanlockstep algorithms discrete interactive objects whose states are not dead-reckoned by default
while waiting for updates. The following sections explain the basic synchronization process thendiscuss details of the synchronization process with regard to simultaneity approximation andcheating.
5.3.1

Operation pipelining

The synchronization mechanism subdivides time into so called bucket intervals of length T.
These intervals help to cluster operations into groups for simultaneous application. All
operations Oi that shall be applied to the local state copy of all clients within interval i have to beissued in the interval i – a - 1. The parameter a, called pipeline-depth, determines the magnitudeof the play-out delay. The play-out delay itself is defined as Δ:=aT. The play-out of any operation
effect to the user is thus delayed by at least the time Δ. An overview of these symbols and theirrelation to parameters is given in Figure 5-2.
All operations O1, …, Ok created at a client C during interval i-a-1 are added to a new request
message Ri in the order of their creation. The message itself refers to the interval i, for which thecontained operations are intended to be applied to the state copies of all clients in the system. Ri
must be sent by the client to the server by the end of interval i-a-1. A request message has to becreated and sent by each client at the end of each interval, even if no operations have to becommunicated. Frequent request messages serve as indicator of the client liveliness and thelatency on the channel connecting the client.
The time the server receives a request message Ri has no impact on the play-out interval of theoperations contained. The server continuously receives request messages of different client forvarious intervals. The server orders the received operations, applies them to the lead state andsends the resulting operations O’1, …, O’n for the adaption of state copies to all clients. The
resulting operations are not necessarily a simple summary of the operations received from allclients. For the purpose of conflict resolution, the server can and may have to change them sothat the state copies at all clients converge.
The operations a client is required to apply to its local copy of the state are contained in the
update message Ui. The update message refers to the interval i in which the operation shouldtake effect at the client. At the moment client C receives Ui the interval i begins for this client.
This moment is referred to as time ti. The client has to apply the contained operations to the
copy of the state. The state change is required to take effect in the presentation to the user
without further delay. To ensure simultaneity between clients, the server sends update
messages individually delayed by time d. An update message triggers the interval increment andthus the release of the next request message with the operations for interval i+a. The pipelining
of update and request messages in the communication scheme is depicted in Figure 5-3.

66

Instant Synchronization of States in Web Hypertext Applications

The latencies of request and update messages are reflected in Δ. Δ is the longest expected periodof time that must elapse between the begin of transmission for Ri and the reception of Ui acrossall clients. It is determined by the latency of the slowest communication channel between serverand clients and the time the server requires for processing client operations. Accordingly, for all
clients the message roundtrip and the processing of operations at the server should take lesstime than Δ.
Operation
Creation

Operation
Playout

O1, O2, … Ok

O’1, O’2, … O’n

C

Ui-a

S

Ri

i-7

i-6

Ui

i-5

i-4

i-3

T

Ri+a

i-2

i-1

i
ti

d
∆

Figure 5-2: Adapted bucket synchronization

The server-controlled timing allows modifying Δ at runtime if request messages tend to be late.
A messages is considered late if it is not finally received at time∆

− . Figure 5-3 suggests thetime required for message reception is negligible. In fact, throughput and message length(number of contained operations) can lead to a significant reception time. To modify Δ theserver can adapt the parameters a and T within predefined boundaries. These boundaries define
the best and worst configuration for a distributed, interactive application and thus need to bechosen individually. If the system is already in the worst configuration and more than apredefined number of request messages in a sequence arrive late at the server, the sending
client is disconnected. Even if a late message is still being processed, the server must send thesubsequent update message on time. If an update message is late, clients are not affected unlessthey use the time span between any two subsequent updates to estimate the likely arrival timeof the next message. This can be reasonable if the states of objects need to be dead-reckoned at
the client. For this reason the server changes the parameters slowly over a number of intervals
defined by the application developer.
The definition of operation lateness follows the definition of message lateness. However, an
operation is not necessarily late if the message it was contained in is late. At the server, an
operation for interval i is on time as long as its processing can begin at∆− , i.e. it has been

completely received at this time. Late operations for i are not considered for this interval any
more. Depending on when they are received, they take effect in a later interval or they arerefused if they have been substituted by operations of a later interval.

67

Instant Synchronization of States in Web Hypertext Application

Request and update messages are required to be received in the order they have been sent. For
the synchronization scheme, message delivery is assumed to be reliable, i.e. messages areneither lost nor are their contents corrupted. However, the consistency objective of thesynchronization scheme is to enable convergence of state copies. This does not necessarily
include the need for a consistent history of operations at all clients. In contrast, a necessary
condition for the communication scheme is that messages can be received and processedinterleaved at client and server. The communication channel must thus not be a queue, whichblocks the processing of messages for interval i as long as still messages of interval j < i have tobe processed.
An example parameterization for the communications scheme that follows the definition of theIEEE standard for distributed interactive simulations [52] is a = 3, T = 50ms, while generally a =Δ / T, T = 50ms is a reasonable heuristic to determine the number of intervals based on the
expected roundtrip time for messages between clients and server.
Operation
Creation

Operation
Playout

O1, O2, … Ok

O’1, O’2, … O’n

C

Ui-a

S

Ui-5

i-7

Ui-4

Ri Ui-3

Ri+1 Ui-2

Ri+2 Ui-1

i-6

i-5

i-4

i-3

T

d

Ri+3

i-2

Ui

Ri+4

Ri+5

i-1

Ri+a

i
ti

∆
Figure 5-3: Pipelining of request and update messages

5.3.2

Latency estimation and fairness

Ensuring a simultaneous play-out of operation effects across all clients requires thesimultaneous reception of update messages at the clients. The latencies of messages can varyfrom client to client. The main reasons for those variations on the internet are the geographicaldistance between communicating sites and the different characteristics of access networks (3G,
Cable, etc.). Accordingly, the server needs to delay update messages for clients artificially by the
expected latency the message will be exposed to. This delay d has to be determined individuallyfor all clients as depicted in Figure 5-4. In practice, a grouping of clients with similar send delays
is reasonable.
A simple estimation of latencies and the resulting delays dC for sending updates to clients can becalculated with the roundtrip times for past messages. The roundtrip time ρC for a client C ismeasured at the server and determines the time between the beginning of sending an update
messages and the beginning of receiving the subsequent request messages. Instead of only one

68Instant Synchronization of States in Web Hypertext Applications

roundtrip, the average for the w last roundtrip times is calculated to smooth out the jitter effects.
Half the difference between this average value and the play-out delay Δ finally represents thevalue of the imposed delay for a client. This estimate for dC is summarized in the following
formula:
=

1
2

−

∑

This estimate does not ensure an absolutely simultaneous play-out of operation effects. The
actual characteristics to which messages will be exposed are not predictable accurately.
Additionally, the processing time of events may differ from client to client. Thus, a variation
remains between the moments of play-out across clients. Nonetheless, the latency estimation
can hide variation of play-out times to a degree that makes them imperceptible for the user. If
latencies differ from one communication direction to the other, as for instance in satellite-added
access networks, a global clock for physical time and message timestamps have to be utilized to
calculate the differences between latencies of both directions.
Supporting the simultaneous application of operations to copies and the simultaneous play-out
of effects aims to enable the fair state-based interaction of users. This is required in trading or
gaming use cases, where users compete with each other instead of collaborating. Simultaneousplay-out of operation effects ensure that all users have the same information at the same time
and thus have the same time to react to this information. The reactions are collected in the sameinterval and should be treated as concurrent by the server.

RCi+1 a

RCi 1

RCi 2

ρC

2

ρC

1

RCi +2 adC1
dC2

Figure 5-4: Individually delayed update messages

The latency estimate discussed above assumes all clients send their request messages Ri as soon
as they receive the update message Ui-a. Where users compete with each other, one user can takeadvantage of manipulating the message timing in the client implementation. An example is given

69Instant Synchronization of States in Web Hypertext Applicationin Figure 5-5. Client C1 intentionally delays sending message

by time thold to make the server

believe the round-trip time and consequently the message latency is higher than it actually is.
The incorrect value is used by the server to determine. Consequently, the server sends Uilong before it actually needs to. The message arrives at the client by time tadvantage earlier thanintended by the server. If the time tadvantage is greater than the interval length T, the client cansend reactions to the operations contained in Ui one or more request messages earlier. For
example in Figure 5-5, client C1 has enough time to include its reactions to Ui inother clients can included their reaction first in, while the. If this reaction of C1 is a bid in an auction

application and the client repeats its behavior continuously, other clients and the users would
experience the application as unfair.

RCi 1

RCi 2

d C1
Figure 5-5: Taking advantage of delayed request messages

For applications that have to cope with the above scenario two options are suggested for the
implementation of the system proposed here:a) The cheating problem arises if a client can include its reactions to an update message inan earlier request message than other clients. To remove this possibility, the pipeliningof operations can be eased by setting parameter a:=1 and thus Δ =T. In this configuration
the proposed algorithm operates like round-based approaches.
b) The client achieves the possibility to cheat by delaying its own request messages andthus disturbs the latency estimation at the server. If the server uses latency informationof a third party the client data can be checked for plausibility. Krishna et al. present in[89] a suitable algorithm to determine the latency of an internet host by the latency of
the DNS server closest to this host.

70

Instant Synchronization of States in Web Hypertext Applications

5.4

State Copies Convergence

With the communication scheme, a basic algorithm for communicating state changes between
clients and server is introduced that preserves the temporal relation between events and thus
satisfies the synchronization consistency objective. The sequencing of messages and ordering ofoperations within messages are additionally the foundation for the maintenance of a global
operation-effect order. But how is operation concurrency addressed in order to achieve state
convergence? To motivate the challenges for both configurations, continuous convergence andconvergence on quiescence, Figure 5-6 shows an example.
For simplicity, the messages and intervals are hidden in the figure. Each operation is containedin a single message. The state is represented as a set of the numeric variables a:=2 and b:=4. The
state variables can be modified by the two functions add and mul. The clients Client1 and Client2
simultaneously create the operations O1 and O2, later Client1 creates operation O3. The Server
receives the operation in the order O2, O1, O3. To correctly process the operations the Serverneeds to know that apart from the order of reception, O1 and O2 emerged from the same initialstate, while O3 bases on the assumption a=4.
a)b)Client1

ServerO1 := mul (a,2)

Client2O2 := add ( a,5)O3 := add (b, a)ServerO1 := mul (a,2)

Client2O2 := add ( a,5)O3 := add (b, a)
O1' ,O2'

O1' ,O2'O3'

Client1

O3'

Operation Mode (1):Continuous Convergence

O2'

O1'

O3'

Operation Mode (2):Convergence on Quiscence

Figure 5-6: Challenges in copies convergence

Considering the causal relations of operations at the Server only is not necessarily sufficient.
Depending on the order of applying O1 and O2, the lead state is finally either SLead = apply(O3,apply(O1, apply(O2))) = {a=14, b=18} or SLead = apply(O3, apply(O2, apply(O1)))= {a=9, b=13}. If theentire system is operated in mode (1) as depicted in Figure 5-6a), i.e. updates are requested but
first executed when the corresponding updates from the server are received, the server can
decide on the global order of operations. Nonetheless, the server needs to know that O3 depends
on O1, rather than on. If, additionally, the system operates in mode (2) as depicted in

Figure 5-6b), O3 has already been applied to the local state copy. Client1 has to consider

71

Instant Synchronization of States in Web Hypertext Application

concurrent to O3 and needs to know whether O1 was respected byor not. In this case thedecision of the Server on the order of applying O1 and O2 significantly affects the convergence ofcopies.
The deterministic application of all operations in the same order at all sites can ensure state
convergence, but not the preservation of operation semantics. The sequential application ofcompeting operations, for instance two operations changing the same variable in the system
state, can finally result in the loss of operation effects. In this case users can get the impressionthat their intentions are not reflected in the converged state. The following section will describe
how causally dependent and concurrent operations are recognized in the system described here.
Additionally, conditions are defined for determining competing operations and an algorithm isintroduced for resolving competitions while preserving the original intentions of users.
5.4.1

Preservation of Operation Causality

The first step towards state convergence is to enable all sites in the system to bring operations
into the same order before applying them. For ordering operations in the system partial
ordering is favored over total ordering for performance reasons. Accordingly an operation O1
can precede an operation O2 or both operations can be concurrent. An operation O1 causally
precedes O2 if the process which issued O2 was aware of the effect of O1 on the state from which
O2 was created. Two operations O1 and O2 are said to be concurrent if neither precedes the other.
Thus, both operations were created independently.
To enforce partial ordering vector time is utilized, a variant of logical time [46]. A peculiarity ofthe system described here is the architecture that hides clients from each other. Any
communication is pairwise between client and server. Accordingly, the vector used to indicate
the logical time at the sites has only two components, one for the client, and one for the server.
For shipping with messages, each operation is annotated with an instance of this vector as
reference to the state the operation originated from.
Definition 5-1: State Reference

The state reference is a two component vector of natural numbers with the form∶=

whose components cclient and cserver are addressable by theconstants client and server and the infix function [], so that [

]≝
and
0
[
]≝
. The vector is initiated at each site with the value. Sites count0
operations locally and increment their component in the local reference. The vector
component of the remote site always contains the index of the most recent causally
preceding operation known from the remote site. If the state references are equal, theoperations must be equal.

72

Instant Synchronization of States in Web Hypertext Applications

Figure 5-7 depicts an example how state references are utilized. When the client creates the first1
operation O1 no operation of the server has been received, so the client annotates O1 with.
0
The first operation of the server O3 is created in causal dependence to O1. This dependence isreflected in the client component of the vector, which has the value 1. Additionally the counter
for local operations at the server is increased by 1 and the value reflected in the state reference1of O3, which is now. O3 is received at the client after the client sends its second operation O2.
1
Accordingly O3 does not reflect O2 in its state reference, the respective vector component still has
value 0.
⎛1 ⎞⎜ ⎟O1⎝ 0 ⎠

⎛3⎞
⎜ ⎟

⎛ 2⎞
⎜ ⎟

⎛ 4⎞
⎜ ⎟

O5⎝ 2 ⎠

O2⎝ 0 ⎠

⎛1⎞
⎜ ⎟

⎛2⎞
⎜ ⎟

O3⎝ 1 ⎠

O4⎝ 2 ⎠

O7⎝ 2 ⎠⎛2⎞
⎜ ⎟O6⎝ 3 ⎠

Figure 5-7: Example of handling state reference vectors

In practice, the state reference can be derived from the interval of the message an operation isshipped with and the number of this operation in the sequence of operations shipped with thesame message. However, to simplify the following definitions, the reference is considered
explicit. With the reference as ordering criterion, the operation can be defined formally.
Definition 5-2: Operation

An operation is data structure of the form Operation := <f, p> where f is a the function withthe signature f: Parameter × S* → S* to be applied to the state S ∊ S* and p ∈ Parameter isthe vector of parameters for the application of f to a state S. S* is the superset of allreachable states.
The parameters of each operation should refer to a continuous namespace. For convenience, in
the remainder of this work the abbreviated notation ( , , … , ) is still used whenever theoperation instance( ,( ,,…,)) is meant, where ( ,,…,)is the component

notation of p. Additionally, the helper function reference: Operation→ Reference is introduced,
which returns a state reference for an operation. With the help of this notation, the server
component of the state reference for an operation Ox is addressed with the notationreference(Ox)[server]. The client component of the state reference is addressed withreference(Ox)[client]. Causal precedence and causal concurrency in the system are formallydefined in the following.

73

Instant Synchronization of States in Web Hypertext Application

Definition 5-3: Precedence

An operation Ox precedes an operation Oy denoted Ox → Oy if all components in the statereference of Ox are less than or equal to their respective components in the state referenceof Oy.
→

≡

(

) ≠

(

)∧ ∀ ∈{

}

,

(

)[ ]

[ ]

≤
Definition 5-4: Concurrence

Two operations Ox and Oy are concurrent, denoted Ox|| Oy, if neither Ox precedes Oy nor Oy
precedes Ox.
∥

≡

(

) ≠

∧

↛

∧

↛

)

The definitions allow server and client to restore the partial order of operations. For the→( ∥ )→→
example given in Figure 5-7 the partial ordering of operations is
)∥

→

((

). To conclude with the same state, both sites need to resolve the partial order toa total order. Utilizing a priority rule for the order of applying concurrent operations, such as“server operations first”, enables both sites to conclude with the same total order for applying
the operations.
5.4.2

Preservation of Operation Semantic

The conclusion of a total order for all operations in the system is a necessary condition for state
convergence. A convergent state, however, is not necessarily experienced as correct state by theuser. Especially the prioritization of concurrent operations has a significant impact on thecorrespondence of the intended and actual states. Two exemplary system configurations andpossible operation sequences are discussed in detail in the following.
Example1: The first example configuration is already used above. The state comprises a set oflabeled numeric variables with initial values S = {a, b | a=2, b=4}. The functions for utilization in
operations are add and mul, to either add a numeric value to a variable in the state or multiply avariable in the state by a numeric value. The two operations O1 and O2 are exchanged between
clients and server as depicted in Figure 5-8 The server forwards the operations as O1’ and O2’. If
O1 || O2, the operation priority is decided based in the site index, so operations of Client2 are
executed first.
O1 → O2 (Figure 5-8a)
Case

O1

O2

SLead

SCopy1

O1 || O2 (Figure 5-8b)
SCopy2

SLead

SCopy1

SCopy2A

add(a,2)add(a,3)

a=7, b=4

a=7, b=4

a=7, b=4

a=7, b=4

a=7, b=4

a=7, b=4

B

add(a,2)mul(b,3) a=4, b=12

a=4, b=12

a=4, b=12

a=4, b=12

a=4, b=12

a=4, b=12C

mul(a,2)mul(a,3)

a=12, b=4

a=12, b=4

a=12, b=4

a=12, b=4

a=12, b=4

a=12, b=4

Dmul(a,2)add(a,3)

a=7, b= 4

a=7, b= 4

a=7, b= 4

a=10, b= 4

a=10, b= 4

a=10, b= 4

Table 5-2: Operation allocation for example 1 in operation mode (1)74Instant Synchronization of States in Web Hypertext Applications

O1

O1

O1'

O1'

O1'

O2

O2

O2'

O2'

O2'

O1

O2

O1

O2

O2' ,O1'O2' ,O1'

O2'

O1'

Figure 5-8: Operation ordering

Table 5-2 summarizes four cases for the allocation of the two operations in operation mode (1).
SCopy1 and SCopy2 refer to the state at Client1 and Client2 respectively. If O1 → O2 the user at client1 isaware of O1 when O2 is created. This awareness is reflected in the decision for theparameterization of O2. The state convergences at all sites and the intentions of users arerespected. Even if O1 || O2, the state converges. Nonetheless the question remains for Case D of
Table 5-2, whether 7 as final value for a is closer to the original user intentions than the actual
value 10. Instead of using a static property for operation prioritization, the priority rule could
respect operation semantic, such as operation with mul function first, or balance decisions fairly
over the interacting users. A fair balance of priority decisions across all clients is especially ofinterest if the state change is absolute instead of relative. For example, a set function which sets avariable in the state to a given value would necessarily result in a final state that does not reflect
the intentions of all users.
O1 → O2 (Figure 5-8c)

O1 || O2 (Figure 5-8d)

Case O1O2

SLead

SCopy1

SCopy2

SLead

SCopy1

SCopy2A

add(a,2)add(a,3)

a=7, b=4

a=7, b=4

a=7, b=4

a=7, b=4

a=7, b=4

a=7, b=4

B

add(a,2)mul(b,3) a=4, b=12

a=4, b=12

a=4, b=12

a=4, b=12

a=4, b=12

a=4, b=12C

mul(a,2)mul(a,3)

a=12, b=4

a=12, b=4

a=12, b=4

a=12, b=4

a=12, b=4

a=12, b=4

Dmul(a,2)add(a,3)a=10, b= 4

a=10, b= 4

a=10, b= 4

a=10, b= 4

a=7, b= 4

a=10, b= 4

Table 5-3: Operation allocation for example 1 in operation mode (2)Table 5-3 summarizes four cases for the allocation of the two operations in operation mode (2).
If O1 → O2 the user at client1 is again aware of O1 when O2 is created and reflects this awareness in
O2. If O1 || O2 the clients apply their own operation before sending them to the server. In case D of
Table 5-3 this proceeding results in a conflict. SCopy1 is divergent to SLead and SCopy2. Client1 would
be required to apply O2 after rolling back O1 for this purpose. Alternatively, convergence could be

75

Instant Synchronization of States in Web Hypertext Applicationachieved in case D if O2’ reflected the context change of O1, i.e. the duplication of a, which would
result in O2’ = add(a,6) rather than in O2’ = add(a,3). A change of the priority rule would only
move the problem from Client1 to Client2. The conflict does not arise in cases A-C. In these cases
the operations either refer to different variables in the state or the application order ofoperations does not matter since the functions are commutative.
Example 2: The second example configuration is a state is a set comprised by strings S = {v, w |v= “xb”, w = “xz”}. The function ins is introduced to insert a character at a given position in astring. The first position in a string is 0. So, ins(v, 1, “b”) inserts “b” at the second position of v,
which results in v=”abcd”. Again the two operations O1 and O2 are considered in theconstellations of Figure 5-8. The allocations for the operations are summarized in Table 5-4 andTable 5-5.
O1 → O2 (Figure 5-8a)

O1 || O2 (Figure 5-8b)

Case O1O2

SLead

SCopy1

SCopy2

SLead

SCopy1

SCopy2A

ins(v,0,”a”)

v=”aaxb”

v=”aaxb”

v=”aaxb”

v=”aaxb”

v=”aaxb”

v=”aaxb”

w=”xz”

w=”xz”

w=”xz”

w=”xz”

w=”xz”

w=”xz”

v=”axb”

v=”axb”

v=”axb”

v=”axb”

v=”axb”

v=”axb”

w=”xyz”

w=”xyz”

w=”xyz”

w=”xyz”

w=”xyz”

w=”xyz”

v=”axbe”

v=”axbe”

v=”axbe”

v=”axeb”

v=”axeb”

v=”axeb”

w=”xz”

w=”xz”

w=”xz”

w=”xz”

w=”xz”

w=”xz”BCins(v,0, “a”)
ins(v,0, “a”)
ins(v,2, “e”)

ins(w,1,”y” )ins(v, 0,”a” )Table 5-4: Operation allocation for example 2 in operation mode (1)In Table 5-4 the state converges for all cases in operation mode (1) if O1 → O2. The user at Client2
is aware of O1 and thus O2 reflects the effect of O1 to Sclient2. If O1|| O2, again the state converges,
but Case C unveils a problem with the final state. Caused by the priority rule O2 is applied firstand changes the value of v so that the effect of O1 in the new value of v is different. The character“e” is inserted before the “b” and not behind as intended. If v is document in a collaborative text
editor, the user who issued O1 would experience the value of v as incorrect. To preserve thesemantic equivalence of O1 and O1’ the server would need to modify O1’ to reflect the change of O2
to the state. The value of the forwarded operation should be O1’ = ins(v, 3,”e”). Changing thepriority rule would only move the problem from one site to the other.
O1 → O2 (Figure 5-8c)

O1 || O2 (Figure 5-8d)

Case O1O2

SLead

SCopy1

SCopy2

SLead

SCopy1

SCopy2A

ins(v,0,”a”)

v=”aaxb”

v=”aaxb”

v=”aaxb”

v=”aaxb”

v=”aaxb”

v=”aaxb”

w=”xz”

w=”xz”

w=”xz”

w=”xz”

w=”xz”

w=”xz”

v=”axb”

v=”axb”

v=”axb”

v=”axb”

v=”axb”

v=”axb”

w=”xyz”

w=”xyz”

w=”xyz”

w=”xyz”

w=”xyz”

w=”xyz”

v=”axbe”

v=”axbe”

v=”axbe”

v=”axeb”

v=”axbe”

v=”axeb”

w=”xz”

w=”xz”

w=”xz”

w=”xz”

w=”xz”

w=”xz”BCins(v,0, “a”)
ins(v,0, “a”)
ins(v,2, “e”)

ins(w,1,”y” )ins(v, 0,”a” )Table 5-5: Operation allocation for example 2 in operation mode (2)76Instant Synchronization of States in Web Hypertext Applications

Although in Case A the operations refer to the same variable in the state, the final state correctlyreflects the semantic of both operations. The parameterization of O1 and O2 in Case A makes theoperations commutable, although function ins is not commutative. In Case B the operations are
isolated since they refer to different variables in the state.
In Table 5-5 the state converges for all cases in operation mode (2) if O1 → O2. Also the semantics
of operations is preserved; for all operations the context is not changed between the moment it
was issued and the moment it is applied. If O1 || O2, there is again a problem if O1 and O2 refer tothe same variable in the state while not being commutable. Client1 applies O1 to the local state
before sending it to the server. Accordingly “e” is positioned behind the “b” in v and not before it
as for Client2 and the Server. A rollback of O1 at Client1 is no option, because the semantic of O1
reflects the intention of the user at Client1. The only alternative to achieve convergence is toensure that the context change caused by O2 at server and Client2 is reflected in O1’ before
applying it at the Server and forwarding the operation to Client2. The operation should thus be
O1’ = ins(v,3,”e”). Case A and B are unproblematic for the same reasons as in operation mode (1).
Both examples discuss the handling of operations from different clients at the server. However,in operation mode (2) also the clients have to resolve the semantics for concurrent operations. A
forwarded operation received at the client can be concurrent to an operation issued and appliedat this client since the last forwarded operation was received. The cases of the above examples
do not differ in this situation and are therefore not explicitly discussed here.
The examples illustrate that semantic violation between two operations O1 and O2 are caused if
O1 || O2 and if O1 and O2 are not commutable in the order of application without modification.
This observation is used to define the competition of two operations as follows:
Definition 5-5: Competition

Two operations Ox and Oy are said to be competing, denoted Ox # Oy, if these operations areconcurrent and if their order of application to any state S ∊ S* results in different final
states.
#≡∃ ∈ ∗

∥

∧

,

,

≠

,

(

, )

The function apply applies an operation to a given state S. The function has the signature:( , )≝

×∗∗and is defined with( )(( ), ).

→As state of the art, different mechanisms for handling competing operations are discussed. In
addition to pessimistic mechanisms such as locking, optimistic mechanisms are introduced suchas rollback, patching and inclusion. Inclusion mechanisms have the advantage that they fulfill the
instantaneity requirement on the one hand, while on the other hand they do not require therollback of operations whose effects were already presented to the user. The objective of77

Instant Synchronization of States in Web Hypertext Application

inclusion mechanisms is to achieve commutability of two competing operations bytransformation.
Definition 5-6: Inclusion Transformation

The transformation function

:

×

→

includesthe effect of an operation Oy ∈ operation into a competing operation Ox ∈ operation written
Ox’ =transform(Ox, Oy). Function and parameters of the operation Ox are changed relative tofunction and parameters of Oy, so that the effect of applying Ox in S is the same as in S’ with
S’ = apply(Oy, S). The transformation function must not require modifying operation
function and parameters relative to the current state S. The transformation function isdefined in accordance to the system configuration, i.e. state representation and operation
functions, but has to satisfy the following property:
,

,

,

=

Precondition (1): ∄

∈

→

∧

Precondition (2):arecontext equivalent

,

,

(

, )

#

The property of the inclusion transformation corresponds to the TPI defined in [62]. The
property ensures that the execution of operations in a different order results in the same final
state. Otherwise a finally transformed operation could result in an unexpected effect. The
preconditions eliminate the need for TPII. Precondition (1) ensures operations are transformed
against the correct order of concurrent operations. For this reason, operations are sequentiallyexchanged between client and server, no operation Oz with∥(→) is hidden from eithersite.
In addition to Precondition (1), context equivalence of the two operations Ox and Oy is enforced
by Precondition (2). This means, that for any three operations Ox # Oy # Oz that arose from thesame state, the transformation transform(transform(Ox, Oz), Oy) is invalid. The result oftransforming Ox against Oz appears like an operation that arose from a state, in which Oz was
already applied. Even though this transformed operation is practically still competing with Oy ,the result of a transformation against Oy does not have the same effect as transform(Ox, Oy). The
correct transformation would be transform(transform(Ox, Oz), transform(Oy, Oz)). A similar
situation is given if (Ox → Oy) ║ Oz, where Ox # Oz and Oy # Oz. In this case the transformation of Oy
after Ox requires a version of Oz that also reflects the effect of Ox. The correct transformation of Oy
would be transform(Oy, transform(Oz, Ox)).

78

Instant Synchronization of States in Web Hypertext Applications

Definition 5-7: Context Equivalence

Two competing operations Ox and Oy are context equivalent if they arose from the samestate or reflect the same history of operations since that state (by transformation or directcausal dependence).
An inclusion function for example 1 could be defined as follows:
,(

, ,

, ) ,

,(

, ,

, )

,(

, ,

,

×

, ) ,

=

∧

=

∧

,

=

,

,(

, ,

,

+

, ) ,

=

∧

=

∧

,

=

,

,(

, ,

,

=

,

, ,

, ×

,

=

≝
,(

, ) ,

=

∧

, ) ,

=

=
,(

, ,

∧

∧

=

∧

,

, ) ,

This inclusion function satisfies the conditions of the transformation function, but does notrespect the operator precedence rules for the prioritization of the mathematical operations mul
and add. If operations with mul should have higher priority in the inclusion function, a new
operation function would be required in the system that first rolls back the addition (i.e.
subtracts the previously added value), multiplies the referenced value in the state and adds thesubtracted value again. This procedure is required since the inclusion transformation must notrefer to the current state S of the system.
A possible inclusion function for example 2 could be defined as follows:
,(
≝

, ,

, ,

,(

, ) ,
, ,

,

,(
+ 1,

, ,

, ,

, ) ,

,(

, )
,

<

,

∨

, ,

, ,

, ) ,

,

=

,

∧

,

<

,

This inclusion function simply increases the offset for inserting the character in the targeted
string if the other operation added a character at a lower offset of the string before. If both
operations refer to the same position in the string, the values of the characters to be inserted arecompared. Characters with a lower value are always written first.
The second inclusion function reveals a problem with regard to fairness of tie breaking. If theintentions of two operations cannot be combined as in the example, a fair tie breaking solution
has to be provided. Fair would mean either to disable both operations or to ensure an equal
distribution of success between the operation originators if tie breaking situations occur
recurrently. Disabling operations is the simpler approach, but means that the application state
does not advance. This can provoke the same tie breaking situation. For an equal distribution of
success between operation originators a random operation priority would be required. The
physical time of operation origination is inappropriate in this regard. Network delays affect thetime operations are transformed. Since delays mainly depend on the physical distance between

79

Instant Synchronization of States in Web Hypertext Application

two machines, the distance between client sites and server site would determine whether andoperation originator loses or wins conflicts. The equal distribution of success between operation
originators has to be enforced. Therefore, the session state is exposed to the inclusion functionin the form of the bucket interval index later.

5.5

Operation Mode Determination

The decision for the introduction of two operation modes follows the study of use cases forapplication on the web and the clear distinction of requirements for competitive andcollaborative user interactions. While in competitive use cases, simultaneity is higher ordermagnitude than instantaneity, in collaborative use cases instantaneity is higher order magnitude
than simultaneity. Nonetheless, collaborative and competitive use cases do not appear in
isolation. Instead of dedicated sessions, each with its own operation mode, sessions with a mixof both operation modes are required. To determine whether a local operation is allowed to be
applied instantly or not, a global schema is introduced for operations.
Definition 5-8: Operation Schema

The schema is composed by the two functions

ℎ

,

:

→{ , }

that determine for any operation Ox ∈ Operation if Ox is applied in operation mode (1) or(2). If and only if synchronous(Ox) is true the operation has to be treated in accordance tooperation mode (1). If and only if instant(Ox) is true the operation has to be treated inaccordance to operation mode (2). The functions have the same domain of definition andmust satisfy the following properties:i) ∀ ∈ii) ∀ ∈
iii) ∀

∈

( )∨
∄

ℎ
ℎ

∈

(

)∄

∈

( ) ∧(
( )∧
ℎ

( )≠
ℎ
∧
#
(

,

( ))
)

Property i) ensures an operation is either to be applied in operation mode (1) or (2), but neverapplicable in both at the same time. Property ii) states that any two competing operations
cannot be classified in different operation modes. This condition is required to ensure
convergence. An approach to achieve property ii) is to classify the entities of the state byoperation mode and let the operation inherit the mode of the entity its parameters refer to.
Property iii) requires the transformation not to change the schema of an operation. The schemabases on the determination that operation mode (1), continuous convergence, is the default
operation mode. The schema functions have the same domain definition, so in principle one
function is sufficient to determine both cases.
At this point all customizable system characteristics have been introduced. The following
definition summarizes the basic System Configuration:
Definition 5-9: System Configuration

80

Instant Synchronization of States in Web Hypertext Applications

The System Configuration is a data structure containing all customizable systemproperties having the form
= 〈 ∗, ∗,,, , 〉 where:S*

is the set of all reachable statesf*is the set of all operation functions supported for transforming the state

instant

is the schema function that determines the mode for any operation

includeis the inclusion function required for operation transformationT

is the initial length of an interval in operation pipeliningais the number of pipelines

5.6

Control Algorithm

The integration of communication scheme, state copies convergence and operation mode
determination is defined by a control algorithm, distributed between client and server. WHAs
base on a thin client application model. The control algorithm is thus designed to handle asmuch processing as possible at the server. The algorithm supports any system configuration andis thus applicable for all state representations and operation functions, as long as thecorresponding schema and inclusion function conform with the above defined properties.
The communication scheme requires all clients to collect operations for an interval and send
them to the server at once. The server thus has to transform n lists of operations per interval,
where n is the number of clients. While the first operations of each list are context equivalentand thus transformable against each other, the remaining operations in the list are not. The
correct transformation of the operations O1 and O2 against O3, where (O1→ O2) || O3, requires totransform O2 against transform(O3, O1) as shown in [62]. For the transformation of any two listsof concurrent operations, Algorithm 5-1 is defined. This makes use of the transformation
function transformi defined in Definition 7. The index i refers to the current bucket interval of thepipelining approach. For each bucket interval a new instance of the transformation function iscreated from the interval index. This mechanism allows binding the tie-breaking rules of thetransformation function to the session state.
1transformlist: List

2

transformlist (L1, L2) = L where

3

L = L1

4for i = 0 to |L|5

for j = 0 to |L2|

6

if L[i] # L2[j]7

L[i] = transformi(L[i], L2[j])8

L2[j] = transformi(L2[j], L1[i])

9

endif

× List→ List81

Instant Synchronization of States in Web Hypertext Application

10

endfor11

endforAlgorithm 5-1: Transformation of operation lists

The algorithm makes use of the data structure List. List is an ordered set of elements and comeswith the function push, peek, concatenate and | |, the operator [ ] and the constructor function
List. The push function adds an element to the end of a list. The peek function retrieves the lastelement of the list without removing it. The function concatenate appends all items of one list toanother. The | | function returns the number of elements in a list. The [ ] operator refers to anelement in a list by its position, where the first element has position 0. For the instance of List
example = a, 4, x, c the notation example[2] refers to x, |example| is 4, push(example, 9) results in
a, 4, x, c, 9, peek(example)would then result in 9, concatenate(example, example) results in a, 4, x,
c, a, 4, x, c.
The order of transforming the lists of operations against each other directly affects theconvergence of states at the clients as discussed in chapter 4. To be able to abstain from TP2, one
central order for the operations from all clients has to be determined during transformation, thecommon transformation path. Before, context equivalence for any two lists of operations has tobe achieved before transformation. The algorithm is explained by the following example.
The server receives four concurrent operation lists A, B, C and D, which only contain operations
already applied at the clients. How the server decides for the order of the lists does not matter.
For a better readability alphabetic order is taken in the example. To additionally shorten theformulas the abbreviated notations AB = transformlist(A,B) and ACB = transformlist(AB,C) areintroduced. In the end each client requires properly transformed versions of the operation listsof the other clients. It would be incorrect to simply send BA, CBA and DCBA to the client who sent A,
because CA and B are not context equivalent and thus cannot be transformed against each other.
Instead CA has to be transformed against BA, which results in. Also D has to be transformed

against the transformed versions of B and C. However, the resulting list only works for the client
who sent A. According to the argumentation above the client who sent D has to receive A, BA and, but these lists do not yet reflect D, so they all additionally have to be transformed against
their context equivalent counterparts of D. The correct operation lists the client who sent D
should receive is,andTable 5-6: Exemplary transformation matrix

82.

Instant Synchronization of States in Web Hypertext Applications

The lists the clients who sent B and C should receive have to be created in a way which combines
the approaches for the cases A and D. Table 5-6 shows the complete compilation of required
transformation results in the example. The operation lists for each client depend on the index ofa client’s operation list in the preselected order of the server. For example, if a client sent B, theserver takes all lists from column B followed by the lists on the diagonal behind the component(B,B). The respective cells are shaded in Table 5-6. The generalized version of this matrix isreferred to as transformation matrix in the following and produced with the help of Algorithm
5-2.
The algorithm introduces the data structure Matrix with the constructor function
Matrix:integer→Matrix, and the operator [ ]. The constructor function Matrix(n) creates anempty matrix with n × n components. The operator [x, y] refers to the component in row x andcolumn y of the matrix.
→ Matrix

1

intervaltransform: List

2

intervaltransform (L) = M where

3

M = Matrix
4

for i = 0 to |L|5

if i > 0 then M[0,i] = transformlist(L[0], L[i])6

M[i,0] = L[i]7endfor8

for i = 1 to |L|9

for j = 1 to |L|10

if i=j then11

M[i,j] = transformlist(M[i,j-1], M[i-1,i-1])

12elseif (j > i) then13

M[j,i] = transformlist(M[j,i-1], M[i-1,i-1])

14

M[i,j] = transformlist(M[i,i], M[j,i])

15

endif

16

endfor17

endforAlgorithm 5-2: Creation of the transformation matrix

The retrieval of operation lists to be sent to the clients is described by Algorithm 5-3. The
algorithm first inspects the columns from the first row to the diagonal and afterwards follows
the diagonal to obtain the lists for each client. In contrast to a pure optimistic solution, thealgorithm also respects pessimistic operations, i.e. operations created in mode (1). Those are
selected

from

:

the
×

diagonal

componentinthematrixbythehelperfunction→in line 9. The set Condition refers to any

condition on the elements in the list. The select function returns elements according to the orderof the original list.

83

Instant Synchronization of States in Web Hypertext Application→ List1

extract: Matrix

2

extract (M) = L where

3

L = List()

4

for i = 0 to |M|5ltmp = List()

6

for j = 0 to i

7

ltmp = concatenate(ltmp, M[j, i])8

endfor9ltmp =concatenate(ltmp, select(M[i, i], x with synchronous(x)))

10

for j = i+1 to |M|

11ltmp = concatenate(ltmp, M[j, j])12

endfor13

push(L, ltmp)

14

endforAlgorithm 5-3: Creation of operation lists resulting from transformation

Server and client process operations in accordance with the pipeline scheme. Before an
operation sent from client to server is processed at the server and forwarded for application in
the target interval, the client can receive multiple messages with concurrent operations. The
server faces the same situation, i.e. operations received from the client still concur with
operations recently sent to this client. Accordingly both first have to update the incoming
operations with regard to recently sent concurrent operations. Recently sent operations are
stored continuously in a history buffer. Operations are deleted from the history buffer after acomplete roundtrip of operations. The update function is described in Algorithm 5-4. The
precondition of the algorithm is that all operations in the non-empty list of incoming operations
L share the same value for the reference component s. That means, for example, all operations
received from a client should point to the same last server operation as causal context.
× List×{,} → List

1

update: List

2

update(L,H,s) = P

3

P= List()4

htmp = select(H, x with reference(x)[s] > reference(L[0])[s])5P = concatenate(P, transformlist(L, htmp))

Algorithm 5-4: Updating operations for transformation in the current state

The control algorithm for the server i) updates the operations from all clients, ii) creates thetransformation matrix, and iii) retrieves the operation lists to be sent back to the client. Since thestate reference of each operation is limited to one client, the server has to overwrite the statereferences for outgoing operations. The control algorithm at the client is limited to updating
incoming operations from the server with respect to locally created, concurrent operations.

84

Instant Synchronization of States in Web Hypertext Applications

The functions intervaltransform and transformlist mostly account for time complexity of thetransformation algorithm. The time complexity of intervaltransform depends on the number ofrequest messages per interval n=|L| and the time complexity of transformlist. The intervaltransformation fills the n×n transformation matrix with results of list transformations. The
algorithm initializes the first row of the matrix while skipping the first element. Hence, it
performs n-1 list transformations. Afterwards it initializes the diagonal and again skips the firstelement, i.e. n-1 list transformations. In parallel to filling the diagonal from the left-upper to theright-lower corner, the algorithm fills the two triangles below and above the diagonal. Since thefirst row and the first column of the matrix are already initialized, only (n-1)2 fields minus the
diagonal n-1 have to be initialized. These steps result in the following complexity calculation:−1+− 1 + ( − 1) − ( − 1) =− . Accordingly the time complexity of the intervaltransformation algorithm can be estimated with O(n2). The time complexity of transformlist
depends on the length of the operations lists to transform against each other. If the first list is oflength k and the second list of length l, the algorithm performs 2kl inclusions. The timecomplexity can thus be estimated with 2max(k,l)2, which is also equivalent to O(n2).

85Instant Synchronization of States in Web Hypertext Application

6 Instant State Synchronization System
Chapter 5 describes communication scheme and algorithms in a theoretical context. This chapter
adds the recommended system architecture for utilizing communication scheme and algorithms ina practical context.

6.1

Overview

The Instant State Synchronization System (IS3) is an abstract realization of the communication
schema and the algorithms for real-time state synchronization introduced in chapter 5. The
system design puts forward the principle of a generic state representation and respective
operations to modify this state. It refines the communication scheme by naming the involved
components and defining the interfaces between them. IS3 extends the legacy Web architecture
by introducing new client and server components, as well as interfaces to connect to legacy
components. The maintenance of the shared state in IS3 is positioned orthogonally to thecontinuation-based interactions of WHA Client and WHA Server. Nonetheless, the state is only
kept as long as a WHA session continues.
A basic system overview is depicted in Figure 6-1. The IS3 Client realizes the client algorithms
and the link to the WHA Client. The IS3 Server maintains the lead state and dispatches statesynchronizing operations to all clients in order to achieve state convergence. Additionally the
IS3 Server provides an interface to the WHA Server to enable data access, session control andclient authentication. IS3 Server and Client are connected by a generic network interface whichreflects the communication scheme introduced in section 5.3.

IS3
ClientIS3
ClientSocketIS3
Network
Interface

WHA
Network
Interface

IS3
ServerIS3
ServerSocket

WHA
ClientIS3ServerSocketIS3
Surrogate
RuntimeEnvironment
WHA
Surrogate

IS3
Surrogate
Management
Interface

WHA
ServerFigure 6-1: Basic System Overview

If WHA Server and IS3 Server are physically separated and the geographic distance negatively
affects the latency of communication among both, a WHA Surrogate can be used to substitute thedirect access of WHA Server to IS3 Server. A WHA Surrogate is an active component,

86Instant Synchronization of States in Web Hypertext Applications

implementing the essential WHA logic for IS3. Although not illustrated in Figure 6-1, WHA
Surrogate and WHA Server can also maintain a proprietary communication channel. For safe
execution of WHA Surrogates, the IS3 Surrogate Runtime Environment (SRE) is introduced. The
WHA Server utilizes the IS3 Surrogate Management Interface to deploy WHA Surrogates andcontrol their life-cycle.
In the following sections the basic profile for the interfaces of IS3 is explained in detail. Theinterface models are therefore described abstractly, while not respecting peculiarities oftechnologies that may be used for a later implementation.

6.2

Scopes

The consistency/latency trade-off says: the amount of data that needs to be communicated toachieve state convergence is directly proportional to the transmission time. For the system
proposed here this consequently means there are a finite number of operations for each clientthat can be transmitted within the time Δ introduced in section 5.3 without making theoperation late. The number of operations depends on the application, but most likely increases
with the number of clients. If the application does not require all clients to share the entire stateat the same time, a kind of state masking is useful as shown by [56]. For this reason, the network
protocol here includes support for scopes to mask the shared state and communicate operations
that affect the state within currently relevant scope only.

Figure 6-2: State and Scopes

A scope refers to an addressable subset of the shared state. Any two scopes have to be disjoint.
In Figure 6-2 a state comprised of the six variables A-F and five scopes is depicted. In practice,scopes can refer to the pages of a document or the rooms in a game level. For the document
editor, only the currently viewed page may be relevant. For the gamer, perhaps only visible
objects in the same room are interesting. There is thus no need to copy the entire state to allclients.
Clients subscribe for scopes depending on the application context (e.g. currently documentpage), the server makes sure only operations are delivered to client which refer to the currently
relevant client scope. Respectively only subsets of the state at the client related to the client
scopes are kept up-to-date. if for example a client is subscribed to Scope2 of Figure 6-2 only, theclient does not recognize changes to variables A,C,D and F. However, clients are allowed to87

Instant Synchronization of States in Web Hypertext Application

subscribe to multiple and even all scopes. Changing the scopes requires the initial update of thestate subset referred to by the new scope. Scopes are predefined or can be declare at runtime.
The entire shared state has to be covered by scopes.
Efficient scoping requires a fine grained design of the state representation and respective
operations to modify the state. If the shared state cannot be segmented in terms of masks, one
global scope has to be defined.

6.3

Network Interface

For a straightforward realization as network protocol, the network interface is described on thebasis of messages. The communication scheme describes request and update messages. Bothmessage types are similarly structured in the sense that they contain session related informationsuch as the interval and a number of operations. The establishment and maintenance of thesession itself requires the exchange of a number of additional messages and related information.
Figure 6-3 therefore depicts a generic message format that reflects the needs of communication
scheme and session life-cycle management. The generic message contains one Head and zero or
more Parts.

Figure 6-3: Generic message format

As depicted in Figure 6-4, the Head begins with a Protocol Identifier (format and syntax are to be
defined on the level of protocol specification). The Message Type defines the meaning of themessage and tells the receiver which kind of Data Units it can expect as message payload.
Examples for message types are REQUEST and UPDATE.
The network interface is intended to support the multiple concurrent communication session on
the same underlying communication channel. In this case the transport address (host address
and process port) is not applicable for the unique identification of clients. In an IS3 session, aclient is identified by an Endpoint Identifier. This identifier has to be unique for each IS3 Server.
Clients must not join multiple sessions while using the same endpoint identifier. The endpoint
identifier is selected by the client. To ensure the selection is unique, a client could for example
combine physical address, location and time.
The field Interval Number contains the number of the interval in which the operations in thesame message should take effect. This number was introduced as symbol i in section 5.3.1. The
Last Interval Number contains the number of the last interval the message sending site received
a message from the message receiving site. For example, if the last message the server received
from a client contained the Interval Number 10, this number 10 has to be included in the field
Last Interval Number of the next message the server sends to the client.

88Instant Synchronization of States in Web Hypertext Applications

Figure 6-4: Fields in message HeadAll fields of the Head are marked as mandatory in Figure 6-4. However, since the communication
scheme requires that a client does not send a request before receiving an update, the Last
Interval Number could be implemented as an optional field for messages sent from client toserver. If, in contrast, clients estimate the time for sending the next message, e.g. based on theroundtrip of previous updates, the field is required.
Message Part
Part
Name

Data
Unit

*

*

Figure 6-5: Fields of Message Part

The message payload is segmented into zero or more Message Parts. As shown in Figure 6-5
each Message Part has a Part Name and groups all Data Units that have to be processed together.
The first part always contains all Data Units related to session maintenance. The remaining parts
reflect the scopes in the shared state. The segmentation of messages into parts is a necessary
preparation of an effective operation pipelining. Messages must not contain more than one
Message Part for the same scope.
The format of a Data Unit is depicted in Figure 6-6. The Data Unit is a universal and partiallycustomizable container for the communication of session parameters, state subsets andoperations. The Data Unit Type determines the semantic of the Data Unit. The basic set of session
related values for this field and their meaning is derived from the communication scheme andsummarized in Table 6-10. Types that refer to operations have to be defined with regard to theapplication and are not part of the interface definition. The field Data Unit Parameter may
appear zero or more times and realizes a list of parameters, which can be used to specify themeaning the Data Unit implied by its type in detail.

Figure 6-6: Fields in message Data Unit

The implementation of messages may vary depending on the underlying communication
channel. A direct implementation on a transport protocol could favor a binary message

89

Instant Synchronization of States in Web Hypertext Application

representation. An implementation based on an upper-layer text-based protocol could require amessage representation with markup languages. In either case the parallel transmission of
messages must be supported. Otherwise large messages could block the communication channel
and thus harm the timing of the communication scheme.
6.3.1

Session Participation

A session is initiated and terminated by the backend of a WHA through the server socket. A
session is persistent for its lifetime. The presence or absence of clients does not affect the stateof a session. Modifying the shared state requires clients to join a session and request changes by
issuing operations. Figure 6-7 depicts the message flows on a client participation request in caseof an error and in case of success.

Figure 6-7: Message flow for session participation

The client requests the participation in a session by sending a message of type JOIN, referred toas message a) in Figure 6-7. A join message contains at least one Message Part with two Data
Units as summarized in Table 6-1. The first Data Unit contains a reference to the session theclients intends to join. The second Data Unit names the scope the client subscribes for. Bothtypes of Data Units are mandatory for a JOIN message. A JOIN message can also contain morethan one scope subscription.
Constants are written in upper case in the table, variables in italics, custom constants in italics
upper case. Fields which can be ignored are marked with a hyphen. The formatting remains thesame for tables describing messages in the following sections.
Head

Message Part

Protocol Identifier
Message Type
Endpoint Identifier
Interval Number
Last Interval Number
Part Name
Data Unit
Data Unit

JOIN
client-identifier
Data Unit Type
Data Unit Parameter
Data Unit Type
Data Unit Parameter

SESSION-REFERENCE
session-identifier
SCOPE-SUBSCRIBE
scope-identifier

Table 6-1: Message a) - joining a session

The server can answer the client request to join a session either with a message of type ERROR
or with a message of type UPDATE. An error can occur if a client message is not well formed or90Instant Synchronization of States in Web Hypertext Applications

contains types of Data Units not allowed at this point of interaction. Another prevalent reason isthat the server does not know session or scope the client refers to as illustrated for example in
Table 6-2. If the server replies to a message of type JOIN with a message of type ERROR, theserver considers the client attempt to join the session as failed. The client has thus to issue
another message of type JOIN to reinitiate the procedure. Errors are categorized as critical or
non-critical. Critical errors implicitly disconnect the client from the session, non-critical errors
are supposed to be correctable without disconnection or only have an informatory character.
Critical errors are always sent with a message of type ERROR. Non-critical errors can also
appear in update messages.
Head

Message Part

Protocol Identifier
Message Type
Endpoint Identifier
Interval Number
Last Interval Number
Part Name
Data Unit

ERROR
client-identifier
Data Unit Type
Data Unit Parameter
Data Unit Parameter

CRITICAL-ERRORSESSION-UNKNOWN
session-identifier

Table 6-2: Message b) - error on joining a session

If the server accepts the client request to join a session, the server sends an UPDATE message tothe client. The first update after a client has joined a session must contain at least two Message
Parts. The first part has to contain session information, with at least a Data Unit containing thenumber of parallel pipelines. The Interval Number in the message head and the pipeline number
allow the client to calculate the interval for its first request message. The second Message Part
has the name of the subscribed scope and contains a copy of the state for the scope the client has
subscribed for.
Head

Message Part

Protocol Identifier
Message Type
Endpoint Identifier
Interval Number
Last Interval Number
Part Name
Data Unit
Data Unit
Data Unit
Data Unit

Message Part

Part Name
Data Unit

UPDATE
client-identifier
current-interval-number
Data Unit TypePIPELINE-COUNT
Data Unit Parameter
number-of-pipelines
Data Unit TypeINSTANT-CHECK-FUNCTION
Data Unit Parameter
function-representation
Data Unit TypeREGISTER-OPERATION
Data Unit Parameter
function-name
Data Unit Parameter
function-representation
Data Unit TypeINCLUSION-FUNCTION
Data Unit Parameter
function-representation
scope-identifier
Data Unit TypeSCOPE-INIT
Data Unit Parameter
state-representation

Table 6-3: Message c) - update on joining a session

91Instant Synchronization of States in Web Hypertext Application

An example is shown in Table 6-3. This additionally contains data units for the transport of aschema function, one operation function and the inclusion function to the client. Sessions are set
up at the server, but if the client asks to execute operations in operation mode 1), the client has
to be aware of the implementations for operation functions and the inclusion function. However,in an implementation of IS3 schema function, inclusion function and operation functions could
also be initialized in a different way. The message can contain more than one Message Part toinitialize a scoped state at the client, but it must not contain any operations.
To leave a session, a client sends a LEAVE message to the server. Since the Endpoint Identifier istied to a session, the server knows from which session the client has to be disconnected. No
Message Parts are required. Messages of type LEAVE must not contain any operation. An
example is given by Table 6-4. If the server wishes to disconnect a client without a client request,
the server sends a message of type ERROR that contains a Data Unit with the description for a
critical error.
Head

Protocol Identifier
Message Type
Endpoint Identifier
Interval Number
Last Interval Number

LEAVE
client-identifier
current-interval-number
last-interval-number

Table 6-4: Message d) - leaving a session

6.3.2

State Copies Maintenance

When a client joined a session, the client sends messages of type REQUEST containing
operations to modify the lead state, while the server replies with messages of type UPDATE
containing the effects of remote operations the client has to apply to its local copy of the state. As
explained in the communication scheme, an update message is not necessarily a direct reply tothe last request messages. Messages and thus operation are pipelined as depicted in Figure 6-8.

Figure 6-8: Operation exchange

A correct request message does not require any Message Parts. Such empty messages maintainthe heartbeat the server uses to determine client presence and latency. The example in Table 6-5
contains one Message Part with operations concerning the scope referred to by scope-identifier.
The Message Part contains one custom operation with a custom parameter. Operations and theirsemantic depend on the application, its state representation and use cases. Operations may also
have multiple parameters.

92

Instant Synchronization of States in Web Hypertext Applications

Head

Message Part

Protocol Identifier
Message Type
Endpoint Identifier
Interval Number
Last Interval Number
Part Name
Data Unit

REQUESTclient-identifier
current-interval-number + number-of-pipelines
current-interval-number
scope-identifier
Data Unit TypeCUSTOM-OPERATION
Data Unit Parametercustom-operation-parameter

Table 6-5: Message e) - requesting the application of operations to the lead state

Like the request message the update message does not have to contain any Message Parts andData Units. Nonetheless, empty update messages are required to maintain a proper connection
between client and server. For example, they indicate the beginning of the next interval and tell
the client about the last received request message. The update message shown in Table 6-6
contains one custom operation with two parameters.
Head

Message Part

Protocol Identifier
Message Type
Endpoint Identifier
Interval Number
Last Interval Number
Part Name
Data Unit

UPDATE
client-identifier
current-interval-number +1
current-interval-number + number-of-pipelines
scope-identifier
Data Unit TypeCUSTOM-OPERATION
Data Unit Parametercustom-operation-parameter-1
Data Unit Parametercustom-operation-parameter-2

Table 6-6: Message f) - updating a state copy

The association of Message Parts and scopes of the state can have a positive impact on theoverall system performance, not only with regard to the message size but also with regard tomessage processing. Figure 6-9 depicts an example of the positive effects scopes have inmessage processing. Usually operations contained in a message for interval i+1 are causallydependent on operations of a message for interval i. Thus, they must not be executed before allcausally preceding operations have been applied.
iInterval

i+1

i+2

Message 1

Pipeline 1

Scope: A

Scope: B

Scope: C

Message 2
Scope: A

Pipeline 2

Scope: B

Message 3
Scope: B

Pipeline 3

Operation on Time

Scope: C

Late Operation

Figure 6-9: Processing of late messages

93

Instant Synchronization of States in Web Hypertext Application

If the message size delays the processing of operations for interval i until interval i+1 theoperations for the later interval are delayed and the application blocks. Since scopes are disjoint,
the beginning of a new part in a message implies that all remaining operations in the message do
not causally depend on the operations of this message already processed. Accordingly,
operations of the next message that share the same scope as those operations already applied
from the first one can be applied too without delay. For transmission, the ordering of Message
Parts according to the data size of payload while starting with the shortest is reasonable.
6.3.3

Scope Subscription and Unsubscription

A client can subscribe for multiple scopes. As long as a client is not subscribed for a scope,messages for this client must not contain a Message Part for that scope. Also client messages
must not include a Message Part for scopes they have not subscribed for. The subscription for ascope is piggybacked on the regular request and update messages like depicted in Figure 6-10
and integrated in the session related Message Part.

Figure 6-10: Scope subscription

Analogue to the initial join messages, a request message has to contain a session related Message
Part with a Data Unit containing the name of the scope to subscribe for. A client can subscribe formultiple scopes at once. The example in Table 6-7 contains only one subscription. Additionallythe example includes an unsubscription, which is parameterized with the name of the scope theclient wishes to unsubscribe for. If the session related Message Part of a request contains an
unsubscription for a scope, the request must not contain any operations for this scope.
Head

Message Part

Protocol Identifier
Message Type
Endpoint Identifier
Interval Number
Last Interval Number
Part Name
Data Unit
Data Unit

REQUESTclient-identifier
current-interval-number + number-of-pipelines
current-interval-number
Data Unit TypeSCOPE-SUBSCRIBE
Data Unit Parameter
scope-identifier-2
Data Unit TypeSCOPE-UNSUBSCRIBE
Data Unit Parameter
scope-identifier

Table 6-7: Message g) – subscribing and unsubscribing a scope

An unsubscription is not acknowledged explicitly by the server. At the earliest with the interval
the request addresses, the server stops sending Message Parts for the unsubscribed scope. At
the latest when the client receives the acknowledgement for the request from the server

94

Instant Synchronization of States in Web Hypertext Applications(indicated by the interval number), the client can be sure to receive no further updates for theunsubscribed scope. A subscription is acknowledged with a Message Part for the newly
subscribed scope and a copy of the current lead state. A Message Part with a Data Unit for scope
initialization must not contain any operations.
Head

Message Part

Protocol Identifier
Message Type
Endpoint Identifier
Interval Number
Last Interval Number
Part Name
Data Unit

UPDATE
client-identifier
current-interval-number+1
current-interval-number+ number-of-pipelines
scope-identifier-2
Data Unit TypeSCOPE-INIT
Data Unit Parameter
state-representation

Table 6-8: Message f) - initializing a scope

6.3.4

Summary of Basic Profile

The preceding sections introduced the network interface along with a couple of examples forbasic use cases. The types for Message and Data Unit are derived from the basic profile of the
network interface, which is the minimal set of definitions required for an implementation of thecommunication scheme. Table 6-9and Table 6-10 summarize these types again.
Message Type

Utilization

Description

JOIN

Client to Server

Connect to a session, begin request/update cycle.

LEAVE

Client to Server

Leave a session, i.e. request the termination of the connection to
the session by the server.

REQUEST

Client to Server

Request operations and scope changes.

UPDATE

Server to Client

Deliver operation to the client in order to update the state copy.

ERROR

Server to Client

Notify the occurrence of a critical error and the termination of
the session connection by the server.

Table 6-9: Message types of basic network interface profile

Data Unit Type

Message Types

Ses. Rel. Description

SESSION-REFERENCE

JOIN

yes

Name the session to join.

SCOPE-SUBSCRIBE

JOIN, REQUEST

yes

Subscribe to a scope.

SCOPE-UNSUBSCRIBE

REQUESTyes

Unsubscribe from a scope.

SCOPE-INIT

UPDATEno

Initially set the state copy.

PIPELINE-COUNTUPDATE

yes

Number of intervals within one roundtrip.

INSTANT-CHECK-FUNCTION

UPDATE

yes

Representation of a schema function.

REGISTER-OPERATIONUPDATE

yes

Representation of operation function.

UNREGISTER-OPERATIONUPDATEyes

The operation not supported any longer.

INCLUSION-FUNCTION

UPDATE

yes

Representation of inclusion function.

CRITICAL-ERROR

ERROR

yes

Code and message of a critical error.

ERROR

UPDATE, ERROR

no

Code and message of an uncritical error.

Table 6-10: Data Unit types of basic network interface profile

95

Instant Synchronization of States in Web Hypertext Application

6.4

Client Interface

The Client Interface exposes the capabilities of the Network Interface to the application while
hiding special features of algorithm and network protocol. For example the pipelining is notmodeled on this interface. Instead an asynchronous notification mechanism is intended to
substitute the effects of pipelining for the application programmer. None of the functions in thisinterface is designed to be called synchronously. Whenever the processing time of a function callcannot be neglected, a callback function is used. Like the Network Interface the Client Interface
specified below only contains the minimal set of required functions to enable the realization of
an interactive application. Operations and their parameters have to be defined by the application
developer.
:

×(

×

→ ∅) → ∅ joins a running session on the server. In

connect(name, scope, callback) name is the identifier of the session, scope the name of the initialscope and callback a function expecting a session handle as parameter. The session handle is aclient-only reference to a session and has to be used in all following function calls on the samesession. The name can also include a reference to the network host of the server and thecorresponding process.
:→ ∅ closes the connection of a client to a session without stopping thesession. In disconnect(handle) handle is a reference of the session to terminate.
:( ∗ →

∗)

×

∗

→

is a generic function to obtain the subset of the state

representation at the client. In result:=read(extract, handle), extract is a custom function to get a
subset of the current state, handle is the session reference and result is the result of executing
extract in the current state. The function extract could also be substituted by a name for an
addressable subset in the state, but for now a function provides the more flexible solution.
:

×

×

→

executes an operation on the state. In

instant:=apply(operation, parameter, handle) operation is the name of the function to call withparameter on the state. The result instant determines if the next call of read on the modifiedstate would already return the changes (true) or if the operation takes effect later (false). The
return value depends on the operation mode and the schema defined in the system
configuration.
: ( ∗→

∗)

×

→∅ ×

→ ∅ allows subscription for changes in the state.

In listen(callback, handle) the function callback takes an extract function and a handle of thesession the state change occurred in. The extract function serves as filter for a call of read andthus determines where in the state the change appeared. Again the extract function could also be
replaced by an address to a subset of the state.
:

×(

×

×

→ ∅) ×→∅subscribestheclient to a scope. In subscribe( scope, callback, handle) scope determines the name of the scope tosubscribe for, the function callback is invoked when the state copy for the scope is finally96

Instant Synchronization of States in Web Hypertext Applications

initialized at the client or if an error occurs. The callback therefore gets the scope name, a flagthat indicates success or error and the session handle again. The parameter handle is the session
handle.
:×→ ∅ removes the subscription of a client for a scope. In

unsubscribe( scope, handle) the literal scope represents the scope name, while handle is thesession handle.
:(×→ ∅) → ∅ supports the subscription for error notifications. In

error(callback, handle) the function callback is invoked with error message and session handle
whenever the client experiences an error. The parameter handle is the session handle.

Figure 6-11: Example of the interplay between network and client interface

Figure 6-11 shows an example for the interplay of function calls on the client interface andmessages on the network interface. The interval of updates also determines when changes to thestate are cascaded to the WHA Client.

6.5

Server Interface

The Server Interface is the main control point for the IS3 systems. Since sessions are notinitiated by the clients, the Server Interface is the only tool to setup and maintain sessions.
Additionally, functions for the content-wise control of sessions are included. These functions
enable application logic in the WHA Server to influence the development of the state. The ServerInterface is designed to connect WHA Server and IS3 Server directly, i.e. not through a link
suffering from communication latency. For that reason the processing time of all functions is
supposed to be negligible and the interface has to be designed for synchronous function calls. Ifneither bandwidth nor latency can be guaranteed for the link between WHA Server and IS3
Server, a WHA Surrogate has to be used. The WHA Surrogate accesses the IS3 Server via thesame interface.
:→creates a new session, but does not open it for clients to join. In

handle:=create(name), name is the session reference clients will use to address a session when
joining and handle is an internal session identifier the application has to use for all subsequentfunction calls to the same session.
:×( ∗ →∗)×→ ∅ adds a scope for the state. In scope(name, filter,

handle) the parameter name represents the name of the scope and the function filter a mapping

97

Instant Synchronization of States in Web Hypertext Applicationfrom the entire state to a subset of the state. Multiple scopes can be configured for each session.
The parameter handle contains the session handle.
:∗×→ ∅ sets the initial state for a session. In load(state, handle) the value of stateis the representation of a state. The parameter handle contains the session handle.
:

×

×

→

registers an operation function to asession. In a call success:=register(operation, function, handle) operation is the name of theoperation to be used when referring to the function, function is any function in terms of
Definition 2 and handle is the session handle. The return value success determines if theoperation was registerd successfully (true). The registration fails of no inclusions have been
installed for the operation to register. This function has to be called separately for all operations
to be installed.
:

×(

×

→ ∅) ×→ ∅ uninstallsanoperationfunction from a session. In unregister(operation, callback, handle) the parameter operation
contains the name of the operation not to be supported longer, the function callback is invokedwhen all connected clients received the unregister. The parameter handle contains the session
handle. A call of nooperation also removes the corresponding inclusions and schema check for
instant application.
× (

:

)×

→

→ ∅ sets the schema function instant,which determines whether an operation can be applied to a state copy immediately or has to besent to the server first. In instant(operation, check, handle), operation is the name of theoperation to perform checks on. The function check finally expects the operation parameters anddetects if the operation can be applied instantly (true) or not (false). For the check function theoperation name is constant. The parameter handle contains the session handle. The function has
to be called for any operation in the session to check.
:

×

×(

×

→

×

)×

→ ∅ sets the inclusion function for a session. In inclusion(operation1,operation2, include,
handle) the literals operation1 and operation2 contain the names of operations the inclusion
applies to. The function include represents the operation inclusion function, while the operation
name are supposed to be constant in this function. The parameter handle contains the session
handle. The inclusion function has to be called as many times as there are combinations ofoperations. Inclusions have to be set up before operations are registered.
: ((

×

)×(

×

)→

)×

→∅

sets the function to check whether two operation invocations are competing or not. In
competing(compete, handle) the function compete takes two operation invocations and checks
them for a conflict. The parameter handle contains the session handle.
:→

has to be called when the configuration of a session is setup properly.

In success:=open(handle) handle names the session to be opened. The result success determines

98Instant Synchronization of States in Web Hypertext Applications

whether the session has been opened or not. If a session could not be opened no operation isregistered.
:→ ∅ terminates a session. Calling terminate(handle) results in thetermination of the session referred to with handle.
In addition to the above session control functions apply, read and listen, as defined on the Client
Interface are also available on the Server Interface, with the little difference that calling apply at
the server always returns true. This is because the IS3 Server does not maintain a state copy for
the WHA Server, instead operation are directly applied to the lead state. Operations on thisinterface are thus intentionally out of synchronization with the clients. If the WHA sever has toact as state controlling instance (e.g. referee) between the clients, the fast link is mandatory. If
the Server Interface cannot be implemented as local interface for any reason, remote evaluation
concepts such as robots are recommended to ensure fast responses to client operations onbehalf of the application operator.

6.6

Surrogate Management Interface

The Surrogate Management Interface enables a WHA Server to install and manage surrogates in
the IS3 SRE and is thus directly linked to the IS3 Server. A WHA Surrogate can handle multiple
IS3 sessions in parallel. A limitation of resource usage on the host system is recommended aswell as a clear separation of the execution scopes (sandboxing). At least the following functions
should be supported by the management interface.
× (:→ ∅) → ∅ deploys a WHA Surrogate to the IS3 SRE. In

deploy(surrogate, callback) the parameter surrogate represents the executable code base of the
WHA Surrogate. When a surrogate has been deployed successfully, the function callback is
invoked with the handle of the WHA Surrogate instance as parameter.
×(:→ ∅) → ∅ removes a WHA Surrogate from the IS3 SRE, after

stopping the instance if it is running. In undeploy(handle, callback), handle refers to the instanceto be stopped and removed. The function callback is invoked when the surrogate was finally
undeployed. The function takes as parameter a literal with a status report.
:×(→ ∅) → ∅ starts a WHA surrogate on the IS3 SRE. In start(handle,

callback) handle names the instance to start. The function callback is invoked when the start
procedure was completed and takes as parameter the status of the instance or information
about errors while starting.
:×(→ ∅) → ∅ stops a WHA Surrogate on the IS3 SRE. In stop(handle,

callback) handle names the instance to be stopped. The function callback is invoked when thestop procedure was completed and takes as parameter the status of the instance or information
about errors while stopping.

99

Instant Synchronization of States in Web Hypertext Application:
handle.

100→

can be used to obtain the status of any deployed instance by its

Instant Synchronization of States in Web Hypertext Applications

7 Web Object State Model
The IS3 system is defined to support all representations chosen by application developers for theshared state. The web object state model is a flexible state representation, tailored to the standard
tree structure used in web hypertext applications. The following sections introduce the state
representation, the basic operations to modify the state and the inclusion function for operationaltransformation required for the state objects.

7.1

State Representation

Document Object Model and non-cyclic ECMA object notation both utilize the leaf tree as central
structure for non-primitive data. While leaves in the DOM are text nodes, nodes in ECMA object
model are primitive data types. The web object state model generalizes leaf nodes as literals.
Labeled edges connect a node with its child nodes. Each node is either a leaf or has at least one
child node. Each leaf is addressable by a path which is comprised of the sequence of labels fromthe root node to itself. Leaf2 in Figure 7-1a) is addressable by the sequence label1/label4/label6.

Figure 7-1: Partially ordered tree

In contrast to the DOM the ECMA Script object model is only partially ordered. In the DOM thechild nodes of the same parent are addressed by a zero-initialized numeric offset and thus havean explicit order. If the tree in Figure 7-1a) were a DOM, Leaf2 would need to be addressed by
0/1/0. The ECMA script object model allows string literals as alternative to numeric offsets. An
example is given in Figure 7-1a). Leaf2 is addressed with a/2/d. Nonetheless the usage ofnumeric names allows an ordering of child nodes if required. For example, the node a/2 is said
to be positioned behind a/1.
Since the DOM model is a subset of the ECMA Script object model, the web object state model
follows the latter and implicitly assumes an order for child nodes connected with numericallylabeled edges to the same parent node.

101

Instant Synchronization of States in Web Hypertext Application

The leaf nodes are the relevant ones in the tree. The state representation of the web object statemodel is accordingly tailored to the leaf nodes. Instead of mapping the whole tree, the state
representation is comprised of paths, values and their relations as defined in the following.
Definition 7-1: Web Object State

The Web Object State

=<

ℎ,

,

> is a data structure containing the set ofpaths, the set of values and a function mapping paths to values. The set of paths is defined as theset of vectors wherein the components of each vector are literal labels. A literal is any numericor alphanumeric representation. ( ) is the power set of any set S.
ℎ ∈

ℎ∗ )

(

…

ℎ∗ =

,…,

,…,

∈

…
The set⊆is the set of values reachable by paths. The subjective function:ℎ →is a mapping of paths to values, i.e. all paths in the tree pointing toa leaf node.
For instance the WOS of the tree depicted in Figure 7-1b) would be represented as follows:
ℎ
=〈

1

, 2 ,

, {ℎ

,

, 100},

,

=
,

( )≝

=

100,

=

In addition to the state representation, the following tool functions

ℎ:

:

7.2

→

1
2 〉

→

ℎ and

are introduced, which return the sets of paths and values for a WOS.

Operations to Modify the StateAs addition to the state representation, a minimal set of functions is defined on the WOS
representation for later utilization within state modifying operations. The functions are focusedon the concept of the partially ordered tree. The core functions support the setting, clearing andrewriting of path-value relations. The combined utilization of core functions results in a set offunctions more strongly tailored to the modification of trees.
Definition 7-2: Set Path-Value Relation

The function

:

×

ℎ∗ ×

→

is the basic function to establish arelation between path and value in a WOS instance. The function is defined for four cases.
i) If neither the new path nor the new value is element in the respective set of the WOS, theelements are added to the sets and the function lookup is extended. ii) If the value already102

Instant Synchronization of States in Web Hypertext Applications

exists in the set of values, the new path is added to the set of paths and the lookup function
is extended. iii) If the path already exists, the mapping in the lookup is changed, the newvalue is added to the set of values and the previously related value removed if no other
path is pointing to this value. iv) If path and value to be set already exist, the function
lookup is redefined to map path to value and the value formerly mapped by the path isremoved if no other path maps to it.
( , , )ℎ ∪ { },ℎ ∪ { },
ℎ ,
,
〈
ℎ ,
,
〈

≝

〈

〈

with

=(

and

=

∪ { },,〉,∈〉,∪ { })/{

〉,
∉
ℎ ∧ ∉
〉,
∉
ℎ ∧ ∈
( )=
( )
ℎ ∧∄ ∈
∈
ℎ ∧ ∈
∧
( )≠
( )} and

( )≝

∄ ∈
,

( )=

( )} ,

⁄{

,

=
( ),

The tree represented by the set of paths is restricted in the sense that leaf nodes must nothave child nodes. For that reason an additional precondition is introduced for the set
function.
Precondition: ∄ ∈ℎ( , | |) =An example for the utilization of the third case of the set function is depicted in Figure 7-2 for theabove example. The right-hand part of the figure would result from the left-hand part on,

applying, 200 .

Figure 7-2: Example for (re-)setting a path-value relation
Definition 7-3: Unset Path-Value Relation

The function

:

×

ℎ∗ →

is the basic function to remove a relation

between path and value from a WOS instance. For this purpose the function removes the
mapping from the lookup function, the path from the set of paths and the value from theset of values, if no other paths refers to the same value.

103

Instant Synchronization of States in Web Hypertext Application( , )≝〈ℎ / { },〈
ℎ / { },
with

〉,
〉,

,
,
/{

=

∈
∈

( )=
( )=

ℎ ∧∄ ∈ℎ ∧∃ ∈( )} and

,

( )≝

( )
( )

=
( ),

The unset function can be used to prune branches. An example of the utilization of the unset
function is depicted in Figure 7-3. The right-hand part of the figure would result in the left-handpart after applying:,

Figure 7-3: Unset path-value relation
Definition 7-4: Rewrite Path-Value Relation

The function

:

ℎ∗ ×

×

ℎ∗ →

is the third and last essential corefunction that consequently combines set and unset function to rewrite a path and its
mapping to a value.
( , , )≝

, ,

( ) ,

The core functions represent the transformations essential to create any complex function.
However, they are not suited for transformation on the WOS that follow the semantic of partiallyordered trees. In fact the core functions do not respect any order in the paths at all. The shiftfunction as summarized in Algorithm 7-1, is used to support not only the assignment of names
and values, but also insertions in a sequence of ordered nodes with the same parent node. The
shift function is defined with the help of the vector functions ℎ
:

×

ℎ∗ →

ℎ∗ , and ∘:

ℎ∗ ×

ℎ∗ →

:

ℎ∗ ×

→

ℎ∗ ,

ℎ∗ , where head(p, x) returns the x

first components of p as vector, tail(x, p) returns the last x components of p, and∘returns a

vector of length |p| + |q| with the components of both, beginning with those of p. Additionally the
supportfunctions
∗

104

: (

ℎ∗ ) ×

ℎ∗ →

(

ℎ∗ )

and

:

ℎ∗ ×

→

are utilized. The function filter(P, p) returns the set of all elements in set P which begin

Instant Synchronization of States in Web Hypertext Applications

with p. The function sort(P, c) returns the a list of all elements in P ordered by component c
starting with the lowest value and ending with the highest.
1

shift: WOS × Path × Integer → WOS

2

shift(S, p, k) := Snew where

3

Snew = S4

if |p|>0 then5paths = sort(filter(PathS, head(p,|p|-1)), |p|-1)

6

if k > 0 then7

for i = |paths|-1 to 0 step -1

8

if numeric(paths[i][ |p|-1]) and paths[i][ |p|-1] ≥ p[|p|-1] then9

Snew= rewrite(Snew, paths[i], head(paths[i],|p|-1)∘(paths[i] [|p|-1] + k)∘tail(|p|, paths[i]))

10

endif

11

endfor12 else13

for i = 0 to |paths|-1 step 1

14

if numeric(paths[i][ |p|-1]) and paths[i][ |p|-1] ≥ p[|p|-1] then15

Snew= rewrite(Snew, paths[i], head(paths[i],|p|-1)∘(paths[i] [|p|-1] + k)∘tail(|p|, paths[i]))

16

endif

17

endfor18 endif19 endif
Algorithm 7-1: Shift function

The shift function implicitly assumes the label p[|p|-1] to be a numeric literal, so that it can bechanged in its value by adding k. The path denoted by p is partial in the sense that it does notpoint to a leaf node. The precondition |p| > 0 has to be fulfilled, otherwise shift. Figure 7-4
depicts how the shift function changes the state. The right-hand side of the figure represents thestate after applying ℎ,2, 1 , while example2 is the representation of the left-

hand side of the figure.
The shift function utilizes the rewrite function to increase or decrease depending on k, the label
values of numerically labeled edges to nodes of the same parent. To avoid overwriting of values
and the loss of data, Algorithm 7-1 switches the end from which to start the shifting in line 6. Thelines 7-11 and 13-17 are almost identical. Only the initialization of the loop differs according to
the shifting direction. The function:→

checks if a literal is numeric(true) or alphanumeric (false).

105

Instant Synchronization of States in Web Hypertext Application

Figure 7-4: Shifting nodes

The function set and unset are appropriate and create branches in the tree structure of the WOS.
With the help of the shift functions, the two functions can be extended to respect an ordering
among child nodes of the same parent node. The resulting functions are accordingly named
insert and truncate.
Definition 7-5: Insert and Truncate

Thefunctions
:

×

ℎ∗ ×

:

×

ℎ×

ℎ→

ℎ∗ ×

→

and

the

function

combine shift function, set and unset function to

enable the basic insertion of nodes into ordered sequences or the removal of nodes while
restoring the continuity of the sequence.
( ,

, )=

,
( ,

,

(S,

( ℎ

)= ℎ

, 1),

∘

( ,

),

, )
, −1

A path can contain several numeric labels. To indicate on which level to shift, the complete
path to a leaf node is separated into two parts. The first part phead points to the level to shift
to, the second part ptail names the rest of the path. The composition of both parts point tothe value.
Precondition:| − 1])[|(

The function unsetmultiple is a helper function and defined as follows:
Definition 7-6: Unset Multiple Path-Value Relations

The function

:

ℎ∗ →

×

removes path value relations from S for

all paths which begin with p.
(( , )=
ℎ

106

∈

(

ℎ , )

( , ), ),,(ℎ , ) ≠ {}

Instant Synchronization of States in Web Hypertext Applications

While rewrite, shift andare introduced for the seamless definition of all functions

as well as their parameters and semantics, the set of finally relevant functions for thecommunication of state changes contains only the functions set, unset, insert and truncate.

7.3

Inclusion Function

With state representation and the functions to modify the state, the inclusion function for
operation transformation can be defined, which also depends on the application context. The
inclusion function has the signature: ( ∗ × ∗ ) × ( ∗ × ∗ ) → ( ∗ × ∗ ). For better
readability Table 7-1 summarizes all the cases required for the realization of the function on the
WOS model. The actual state to which an operation shall later be applied to is determined
implicitly by the session and for this reason is not listed among the function parameters. If an
operation becomes obsolete, for example because the path it refers to does not longer exist, theoperation is refused and its place in the operation queue overwritten with an empty operation
denoted by the symbol ε.
Reference

Operation tooperationtransform

set, (p1, v1)

set, (p2,v2)

Resulting operation
set, (p2,v2); if p2 ≠ p1
set, (p2, v2); if p2 = p1 and v2 > v1
set, (p2, v1); if p2 = p1 and v1 ≥ v2

set, (p1,v1)

unset, (p2)ε; if p1 = p2

set, (p1,v1)

insert, (h2, t2, v2)

insert, (h2, t2, v2)set, (p1,v1)

truncate, (h2, t2)

truncate, (h2, t2)

unset, (p1)unset, (p2)unset, (p2); if p1 ≠ p2

unset, (p2); else

ε; elseunset, (p1)set, (p2,v2)

set, (p2,v2)

unset, (p1)insert, (h2, t2, v2)

insert, (h2, t2, v2)

unset, (p1)truncate, (h2, t2)

truncate, (h2, t2)

insert, (h1, t1, v1)

set, (p2,v2)

set,(head(p2,|h1|) ∘ (p2[|h1|-1]+1) ∘ tail(|h1|,p2),v2);
if head(h1,|h1|-1) = head(p2,|h1|-1)∧ numeric(p2[|h1|-1])∧ p2[|h1|-1] ≥ h1[|h1|-1]
set, (p2,v2); else

insert, (h1, t1, v1)

unset, (p2)unset,(head(p2,|h1|) ∘ (p2[|h1|-1]+1) ∘ tail(|h1|,p2));
if head(h1,|h1|-1) = head(p2,|h1|-1)∧ numeric(p2[|h1|-1])∧ p2[|h1|-1] ≥ h1[|h1|-1]
unset, (p2); else

insert, (h1, t1, v1)

insert, (h2, t2, v2)

insert,(head(p2,|h1|) ∘ (p2[|h1|-1]+1) ∘ tail(|h1|,h2), t2, v2);
if head(h1,|h1|-1) = head(h2,|h1|-1)∧ numeric(h2[|h1|-1])∧ h2[|h1|-1] ≥ h1[|h1|-1]
insert, (h2, t2, v2); else

107Instant Synchronization of States in Web Hypertext Application

insert, (h1, t1, v1)

truncate, (h2, t2)

truncate,(head(p2,|h1|) ∘ (p2[|h1|-1]+1) ∘ tail(|h1|,h2), t2);
if head(h1,|h1|-1) = head(h2,|h1|-1)∧ numeric(h2[|h1|-1])∧ h2[|h1|-1] ≥ h1[|h1|-1]
truncate, (h2, t2); else

truncate, (h1, t1)

set, (p2,v2)

ε; if h1 ∘ t1 = p2
set,(head(p2,|h1|) ∘ (p2[|h1|-1]-1) ∘ tail(|h1|,p2),v2);
if head(h1,|h1|-1) = head(p2,|h1|-1)∧ numeric(p2[|h1|-1])∧ p2[|h1|-1] ≥ h1[|h1|-1]
set, (p2,v2);else

truncate, (h1, t1)

unset, (p2)ε; if h1 ∘ t1 = p2
unset,(head(p2,|h1|) ∘ (p2[|h1|-1]-1) ∘ tail(|h1|,p2));
if head(h1,|h1|-1) = head(p2,|h1|-1)∧ numeric(p2[|h1|-1])∧ p2[|h1|-1] ≥ h1[|h1|-1]
unset, (p2); else

truncate, (h1, t1)

insert, (h2, t2, v2)

insert,(head(p2,|h1|) ∘ (p2[|h1|-1]-1) ∘ tail(|h1|,h2), t2, v2);
if head(h1,|h1|-1) = head(h2,|h1|-1)∧ numeric(h2[|h1|-1])∧ h2[|h1|-1] ≥ h1[|h1|-1]
insert, (h2, t2, v2); else

truncate, (h1, t1)

truncate, (h2, t2)ε; if h1 ∘ t1 = h2 ∘ t2
truncate,(head(p2,|h1|) ∘ (p2[|h1|-1]-1) ∘ tail(|h1|,h2), t2);
if head(h1,|h1|-1) = head(h2,|h1|-1)∧ numeric(h2[|h1|-1])∧ h2[|h1|-1] ≥ h1[|h1|-1]
truncate, (h2, t2); else

Table 7-1: Case switch for inclusion function on WOS

The inclusion function is designed keep data in case of conflicting delete and write operations, aswell as to avoid partial rollbacks. For example, if a set and an unset operation refer to the same
path, the unset most likely happened without awareness of the new value to be set. Accordingly
the inclusion function makes sure the converged state contains the new value for the pathinstead of none. If an unset and a truncate refer to the same path, the truncate is always chosen,because the unset is part of the definition of the truncate function.

7.4

Pseudo Random Tie-Breaking Method for the Inclusion Function

Section 5.4.2 concludes with a discussion of fair tie-breaking methods. If a single decision isconsidered in isolation, either a rejection of all competing operations or the random selection ofa winner are fair alternatives. In case a decision is needed recurrently between operations fromthe same origin, a random distribution of success between the origins has to be granted.
The WOS tie-breaking rule bases on the operation value, i.e. the value to be set or inserted. The
operation with the greater value is always preferred. Unless such a behavior is explicitly

108Instant Synchronization of States in Web Hypertext Applications

required by an application (e.g. auction platform) the tie-breaking rule cannot be consideredfair. For that reason, the inclusion function is extended with an optional pseudo-random tiebreaking method. Random decision making raises two problems: i) clients and server
nonetheless have to be able to come to the same decision, because both perform inclusions andii) an even distribution of success among all origins has to be guaranteed, but the inclusion
function only sees two operations from different origins on each execution.
Problem i) can be solved with a pseudo-random number generator (e.g. Linear Congruential
Generator), which recursively creates pseudo-random numbers based on a seed value. Eachtransformation function is instantiated from the current bucket interval index i. The index canserve as common seed for all sites to ensure that equal sequences of pseudo-random numbers
are generated. The consistency of the generated sequences is the basis for deterministic decision
making.
A solution for problem ii) requires the inclusion function to be aware of the operation origins.
Therefore, each operation originator (i.e. endpoint) requires a unique name. The origin names
are selected from a finite name space Q and are sortable. Any sorted list of origin names is totallyordered. The origin name is added as parameter to each operation. The inclusion function
derives the priority of an operation from its origin name by the use of the associative array
priorityi. Thus, if the function:

the origin name and→ returns the parameter of an operation with
(

) >

(

) the operation of

Client1 is preferred over the operation of Client2. The associative array priorityi is prepared on
the instantiation of the inclusion function for bucket interval i. One possible approach for the
instantiation is presented in Algorithm 7-2:
12
3
4

Rn = randomlist(i, |Q|)for k = 0 to |Rn|priorityi[Ln[k]] = Rn[k]endforAlgorithm 7-2: Initialization of the priority hash array

The function:ℕ × ℕ →uses the random number generator to create a list of| | pseudo-random numbers starting from i as seed. This list has to contain each number x with0 ≤< | | exactly once. Ln is an ordered list of all elements in Q.

A weak point of this approach is the obvious predictability of the priorities for each interval
number if the origin names are known. Two preventive options to ensure fairness are to run
only in operation mode (1) and to obscure origin names by interval–related aliases with equal
priorities in the version of the inclusion function used at the server.

109

Instant Synchronization of States in Web Hypertext Application

8 The Pulsar System
IS3 describes the recommended system architecture, but is not a software blueprint itself. This
chapter describes the design of the Pulsar System, an IS3 implementation, with specifications forclient, server and network interfaces.

8.1

Overview

The Pulsar system is a full implementation of the IS3 reference architecture, designed forexperimental evaluation of IS3 and the realization of a case study to be introduced in chapter 10.
As intended by IS3, Pulsar supports all state models that can be implemented in accordance withthe requirements and conditions defined in chapter 5. The Pulsar architecture is not designed tosupport one state model only. However, the Web Object State Model (WOS) is implemented as
one possible configuration for the Pulsar system and is additionally reflected in the Application
Programmer Interface (API).
Pulsar Client

Client Session
Management

Server
Adapter1
Server
Adaptern

Pulsar Server
E1

En

ClientController1
ClientControllern
ClientControllern+1

A
WHA Client

ServerSessionManagement

D
Robot
EngineC

B

WHA Server

Figure 8-1: Pulsar system overview

Figure 8-1 depicts all components of the Pulsar implementation and their public interfaces. The
main components of the Pulsar implementation are Pulsar client and server. The Pulsar client
extends the WHA client with means to access a shared state that reflects modifications instantly.
The WHA client accesses Pulsar through the client interface A. The Pulsar server implements theshared memory by maintaining multiple sessions, processing operations of different client andreflecting these operations to the client state copies. The Pulsar server additionally includes a
Robot Engine, which provides application framework and runtime environment for small,autonomous components provided by the WHA operator, so called robots. Robots interface thePulsar server via a low delay link and have privileged access to session state and operation
stream. For example, the WHA operator can provide robots to add value to the interaction ofclients or enforce rules on the operation stream and the state. The Pulsar System is designed

110Instant Synchronization of States in Web Hypertext Applications

with the assumption that Pulsar server and WHA server are physically separated andcommunicate via a non-negligible geographic distance. Robots are thus a suitable instrument tocustomize state and session without inducing extra delays. The implementation of the Robot
Environment [90] is provided by Stanley Schragl and is therefore not documented here. The
Pulsar server is accessed through the interfaces B, C and D, where B corresponds to the IS3
server interface, C enables deployment and life-cycle control of robots, and D the access ofrobots to the session management in the server core. Pulsar client and server are connected via
network interfaces E1-En.

8.2

Network Interfaces

8.2.1

Text Interface

The text interface is the default network interface of the Pulsar implementation. The name ischosen for the text-based representation of messages as enabled by the utilized application
protocols. While this work is conducted, first standard drafts and implementations for the
WebSocket appear. Originally the text interface is based on long-polling, but in the final iterationof the Pulsar system documented here a hybrid version based on XHR and the most recent
WebSocket draft is utilized. For user agents that do not yet support the WebSocket API, a workaround with Flash is utilized [91].
The types of message exchanged by Pulsar client and server are taken from the IS3 network
interface recommendation introduced in section 6.3. Except for the message parts, the message
structure is mostly adopted from IS3 and mapped to a text representation in JSON [39]. Fields
that could be mapped to the underlying protocols more efficiently where extracted. In the hybrid
approach session control messages and state control messages are separated. Messages of thetype JOIN, LEAVE, SUBSCRIBE and UNSUBSCRIBE are transported via HTTP requests of the type
POST. In contrast to the IS3 suggestions, endpoint identifier, session identifier and message type
are therefore encoded in the path of the server URL and not as fields of the message in therequest body. Scope names for subscriptions and unsubscriptions are also moved to the URL andappended as query string. This way, the request body does not have to contain any data at all.
The responses contain the fields which, according to the IS3 network interface, should be
included with an UPDATE message.
When a client joins a session and client and server do not yet maintain a WebSocket connection,
the client has to open such a connection by issuing an HTTP request with a protocol upgrade. As
soon as the connection is provided, the server initiates the pipe-lining scheme and starts sending
messages of the type UPDATE to the client as depicted in Figure 8-2. The client has to reply
immediately with a REQUEST message to each UPDATE message. As long as a client has joined asession, but no WebSocket connection is available, the server buffers UPDATE messages.
Buffered messages are released in the order they were buffered when the connection wasestablished. Before the last buffered UPDATE is delivered no current UPDATE is sent. Since111

Instant Synchronization of States in Web Hypertext Applicationbuffered UPDATE message do not refer to the current bucket interval, the client must not reply
to them with a REQUEST message. For this reason previously buffered messages are marked
with a “patch” flag to indicate that they only help the client to update the state representation.
The same procedure is applied if the WebSocket connection is unintentionally intermitted. To
leave a session, the client sends the respective message via XHR. If the session was the lastsession the client maintained with the server the client is supposed to close the WebSocket
connection too. Analogue to the LEAVE message in Figure 8-2, a client can subscribe andunsubcribe scopes and join further sessions while the WebSocket connection is open. Messages
on HTTP and WebSocket are synchronized by the bucket interval of a session.

Figure 8-2: Connection handling in the text-based network interface

The hybrid approach was chosen with respect to the size of initialization messages. The
response to an initialization message contains state representations and JS code for theconfiguration functions. If the state representation belongs to a text resource, for instance ashared document with 200 pages, the WebSocket connection would be busy as long the
document is transferred to the client. Controlling the session via HTTP has the advantage thatthe control mechanisms keep response even when the WebSocket connection is blocked or busy
and vice versa. The schemes of messages are summarized in Annex A.
8.2.2

Binary Interface

For the effective utilization of network capabilities in experimental evaluation the IS3 network
interface is also implemented in a binary version for Pulsar. This version, called RTSYNC, isdesigned for direct usage with the Universal Datagram Protocol (UDP), but still uses theTransport Control Protocol (TCP) as fallback. Basically, all operations for or from a client for one
interval are put into one UDP packet for delivery. To avoid packet dropping or fragmentation thepacket size must not exceed 4096 byte, while 1024 byte is the recommended maximum size. The
binary interface assumes compact representations of state and operations, but therefore
operates easily at intervals below 50ms. However, RTSYNC may not be suited for applications
that require the server to send updates with an average data rate greater than the preferred
datagram size.

112

Instant Synchronization of States in Web Hypertext Applications

Figure 8-3: RTSYNC message for UDP PDUs

An RTSYNC message for a UDP packet comprises a Head and multiple Data Units as depicted in
Figure 8-3. The head of a pulsar message, as depicted in Figure 8-4, is defined in accordance with
the IS3 message head definition. Only the meaning of the Last Message Interval field differs
slightly. Since a UDP datagram can get lost, the field does not contain the interval of the lastreceived message, but rather the interval of the last message received before loss occurred. The
Reserved field is a placeholder to obtain a multiple of 8 bits.

Figure 8-4: RTSYNC message head

In contrast to the IS3 interface definition, RTSYNC does not subdivide message explicitly inparts. The session related part is rather represented by specially flagged Data Units, called Meta
Data Units. If the Type Flag depicted in Figure 8-5 is not set, the Data Unit contains meta
information about the connection. The length of the Value field is fixed and defined by the Unit
Code. A complete list of predefined Unit Codes is appended in Annex B. The RTSYNC message
begins with Meta Data Units and is followed by Action Data Units. The latter are characterized bya number of variable-length fields, which are for example used to map operation parameters.

Figure 8-5: RTSYNC message data units

Each field value begins with a Field Length. The Field Length has a minimum length of one byte.
If the first bit is set, the next byte excluding its first bit is also used to represent the field length.
If the first bit of the second byte is also set, additionally the next byte is included and so on. The
seven remaining bits of each byte are interpreted as one continuous sequence to obtain theactual length of the Field Data. The encoding is big-endian.

113

Instant Synchronization of States in Web Hypertext Application

Figure 8-6: RTSYNC message variable-length field coding

All Action Data Unit are grouped by scope and sorted ascending by group size in an RTSYNC
message. Although sorting does not have a serious impact within an UDP datagram, it has an
impact on the performance in TCP breakout transmission. A serious problem in UDP
transmission is loss. Figure 8-7 shows the behavior of client and server if an update is lost. The
client recognizes loss when receiving the first successfully transmitted update after one orseveral losses by the discontinuity of Target Interval numbers in the message header. The client
notifies the server implicitly by not increasing the value of the Last Message Interval header of its
next request. The server has to retransmit the lost update immediately. For this purpose theserver should store a message provided it was acknowledged by the client.
Client detects loss
REQUEST

RTSYNC Client

REQUEST

REQUEST

X LossUPDATERTSYNC Server
UPDATEUPDATEUPDATEUPDATE UPDATE(regular)(old)Server detects loss

Figure 8-7: RTSYNC lost update

The client must not apply any out of order operations to maintain causal order. Thus, basicallythe client has to wait with the application of operation from the server until all lost messages
have been retransmitted and received successfully. To minimize the need for strict blocking, thescopes are utilized. The scopes of the state are disjoint. Accordingly, two operations of different
scopes cannot have a causal relation. If the client knows for which scopes operations were lost,
operations of the message following a lost one could be applied. For this purpose, an RTSYNC
updates can include several Meta Data Units with the hash keys of the scopes covered by the
directly preceding update.
A lost request is first anticipated by the server and signalized with the next update to the client.
Like the server, the client retransmits lost requests immediately as depicted in Figure 8-8. The
server does not block when a request is lost, instead the server treats the loss as if the client had
sent a message without operations. When the late operations are received they are still
respected by the server, but their effect is delayed.

114

Instant Synchronization of States in Web Hypertext Applications

Figure 8-8: RTSYNC lost request

For the server, late and lost requests are difficult to distinguish. The server has to assume a∆message is lost if it has not yet been received at . To minimize the confusion of loss and lateness,the duration T of the interval is adapted dynamically. The initial value, the so called maximum
interval length, is successively shortened to a safe interval that still respects maximum jitter
values. For the calculation, the roundtrip time of request and update is continuously measured
for all clients. If no safe interval length less than the maximum interval length is found for aclient, the client is disconnected. The runtime adaptation of play-out delay Δ optimizes the user
experienced system behavior. A slow adaptation, as depicted in Figure 8-9, ensures that
potential dead reckoning procedures applied on top of Pulsar have sufficient time for adaptation
too.
REQUEST

REQUEST

REQUEST

REQUEST

REQUEST

UPDATEUPDATERTSYNC Client

RTSYNC Server
UPDATEUPDATEUPDATE∆StartUPDATE∆End

Figure 8-9: RTSYNC interval length adaptation

The limitation of the message size is a problem if a client subscribes for a new scope, such as
during session initialization. In this case a serialized subset of the state has to be sent to theclient. For this purpose RTSYNC supports a TCP breakout. If the server determines that theserialization of the state exceeds the maximum length of a message, an Action Data Unit is added
to the message instead with a breakout instruction, host name, port and the number of Data
Units. On receiving the breakout instruction, the client has to temporarily open a TCP connection
to the given host and port and resend the header of the message the server answered with the
breakout. The server has to reply with an RTSYNC update and the number of previously

115

Instant Synchronization of States in Web Hypertext Application

announced Data Units. Afterwards the client terminates the TCP connection. The message flow is
depicted in Figure 8-10.

Figure 8-10: RTSYNC TCP breakout

8.3

Server

The Pulsar sever is implemented in Java and can maintain multiple sessions in parallel and is
structured accordingly. Each session is controlled by a corresponding session controller thatprocesses the operations connected clients, i.e. transforms them and applies them to the leadstate assigned with a session. Additionally the controller manages all users participating in asession as well as their subscriptions for scopes.

...
Figure 8-11: Pulsar server overview

Since Pulsar supports multiple client interfaces, client operations for the same session can bereceived on any of these interfaces. For this reason each session controller is associated with abucket bus. The bucket bus supports bidirectional communication of operations between asession controller and multiple client controllers. Following the interval-based communication
scheme, all operations of the same interval are collected in the same bucket. The bucket bus
serves buckets of incoming operations in a queue, while the head element of the queue is the116Instant Synchronization of States in Web Hypertext Applications

bucket for the next interval. The session controller manages the timing of dequeuing andreleasing processed buckets to the client controllers. The client controllers receive and parse
messages via the network interfaces from the clients and pass them on to the message bus. They
also obtain the ready processed bucket from the busses and serialize and send the transformed
operations to the clients. The organization of the basic server element session, session
controller, bucket bus and client controller is depicted in Figure 8-11. The following sections
introduce the core data structures and system components as well as their interworking.
8.3.1

Data Structures

All components of the Pulsar server are designed for the parsing, serialization, forwarding andprocessing of state modifying operations. For the realization these operations are organized in
two container structures, the Load and the Bucket. The Load container represents the list ofoperations per interval and client. Thus, all operations sent within the same interval by the sameclient are collected in the same Load container in causal order. All operations that have to besent for one interval to a client are also collected in one Load container in causal order. The
causal order is derived from the state Reference if it was changed during processing. All Loads
provided by clients for one interval and all Loads to be sent to clients in one interval arecollected in Bucket containers. The Loads of the different clients within one bucket are ordered.
This order may vary from interval to interval, i.e. the order with respect to the sender. However,for one interval the order, once determined at the server, must not change within server or atany client.
Load

Bucket1+getInterval() : Integer+addLoad(in load : Load)+getLoad(in index : Integer) : Load+size() : Integer+clear()*+getEndpointIdentifier() : String+setEndpointIdentifier(in identifier : String)+getOperation(in index : Integer) : Operation+addOperation(in operation : Operation)+size() : Integer+clear()1*
Operation

Reference+getServer() : Integer+getClient() : Integer+setServer(in value : Integer)+setClient(in value : Integer)11+getReference() : Reference+getFunctionName() : String+getParameters() : List<String>+setParameters(in params : List<String>)+setFunctionName(in name : String)+setReference(in ref : Reference)

Figure 8-12: UML class diagram for sata structures in Pulsar server realization

8.3.2

Session Management

The core of the Pulsar server implementation, as depicted in Figure 8-13, is represented by theabove introduced SessionController, the SessionBucketBus, the ClientController, and an additional
SystemController. All these components follow a bipartite interface concept of basic andextended interfaces. The system view granted by basic interfaces is intended for clients and their

117

Instant Synchronization of States in Web Hypertext Applicationdelegate, the ClientController. The system view granted by the extended interfaces addresses
management access, such as required by the WHA Server. The SystemController is the central
entry point to create, control and shutdown sessions. This controller is configured by the
SystemConfiguration, which basically contains a list of ClientControllers. The actual access tosession state and management data is provided by the SessionController.

Figure 8-13: UML class diagram for Pulsar server core components

Each

SessionController

is

also

associated

with

an

OperationTransformer.

The

OperationTransformer processes the inclusion of client operations and temporarily stores thetransformation results. The result of each transformation has to be stored in case a client load is
received that is still concurrent with the results of the previous transformation. This load would
require transformation into the current state before it could be transformed against concurrent
loads. Actually, if the pipeline depth of the communication scheme is greater than zero this is the118Instant Synchronization of States in Web Hypertext Applications

default case for all loads. Like the SessionBucketBus the OperationTansformer organizes
processed buckets of outgoing operations in a queue. The SessionController reads from thisqueue whenever the time is due to provide the clients with the operations for the next interval.
8.3.3

Custom Configuration

When a new session is created, an appropriate configuration has to be provided that defines theparameters for system operation. The most important elements of the system configuration are
the various functions for modifying states and transforming operations. These functions areprovidedduringthecreationofasessionwith

theSessionConfiguration.

Each

SessionConfiguration is associated with a list of Scope instances. The Scope component manages
client subscriptions to scopes in the state and provides a function to check if an operation affects
a scope of the state or not. This check has to be implemented as OperationFilter The Session
serves at runtime as door to SessionConfiguration and Resource for the SessionController.
Additionally it manages the current list of clients connected to a session.

Figure 8-14: UML class diagram of custom session configuration

119

Instant Synchronization of States in Web Hypertext Application

Pulsar is designed independently of state representation and operation functions. Appropriate
implementations have to be provided with the session configuration. For the utilization in a
WHA setup, these implementations have to be represented in ECMA 262 [92] compliant syntax.
During session initialization, the functions can thus be marshaled to the clients and executedwithout further translation or interpretation. Within the Pulsar server, the functions are
represented as strings. When a session is created these functions are interpreted and checked
for correctness. If their correctness is proven they are compiled for later usage. Just-in-timecompilation prevents the server from interpreting the function each time they have to be called.
The server expects the strings to contain JS functions implementing the interfaces listed below.
The listings are given in WebIDL syntax [93]. If the functions and entities in the strings returnedby the corresponding configuration methods do not match the interfaces, a session will not becreated. The interface of an operation described in Interface 8-1 is not utilized by the server
implementation directly, but by the server to make sure that any operation will match thesignature.
[NoInterfaceObject]interface Operation {attribute DOMString type;attribute DOMString[] parametersattribute DOMString origin}
Interface 8-1: Operation

A state representation is provided as the Resource depicted in Figure 8-14. The code of the
returned string has to be a function call (e.g. a closure), which returns an implementation forInterface 8-2. At the client, this entity is used to optimistically update a representation of theresource state (i.e. a replication) and read locally from this state.
interface Respresentation {DOMString read(DOMString name);
void apply(in Operation op);void addSubset(DOMString scope, DOMString representation);};Interface 8-2: Handle to a copy of the resource state

The three parts of the session configuration provided by the methods getInclusionFunction,
getCompetingFunction and getInstantFilter documented in Figure 8-14 have to match thesignatures summarized in Interface 8-3, Interface 8-4 and Interface 8-5. Again the code returnedby the methods has to implement a function call statement which returns, once executed, afunction with the required interface.

120

Instant Synchronization of States in Web Hypertext Applications

interface Inclusion{Operation transform(Operation op1, Operation op2);}
Interface 8-3: Inclusion function

interface Competition{boolean competing(Operation op1, Operation op2);}
Interface 8-4: Function to analyze relation of two operations

interface Instant{boolean instant(Operation op);}Interface 8-5: Schema function to check of an operation can be applied instantly

8.3.4

Component Interworking

A Pulsar session is created with the help of the SystemController. The SystemController createsa SessionController, a SessionBucketBus and assigns the bus to all ClientControllers. Also via the
SystemController a ClientController can obtain any SessionController by citing the name of thesession. The session name can be chosen free, but must be unique on the server. A
ClientController requires access to the SessionController to add new clients to a Session andforward their subscriptions to Scopes as depicted in Figure 8-15.

Figure 8-15: Simplified UML sequence diagram for session initialization

121

Instant Synchronization of States in Web Hypertext Application

The regular interworking of the core components is depicted in Figure 8-16. When a
ClientController receives a Load of operations from a client, the controller looks up the
SessionBucketBus for the corresponding Session and the Bucket for the corresponding interval.
The Load is added to the Bucket. This process may be repeated for one Bucket until each client
on a session has delivered its Load. The Bucket remains in the queue of the bus until its interval
is due for processing. At this time the SessionController dequeues the Bucket and forwards it fortransformation to the OperationTransformer. The OperationTransformer retrieves all Loads,
transforms them and enqueues the Bucket with the results again until the SessionController
decides to forward the Bucket to the clients. Usually a Bucket is immediately released to the
ClientControllers without further queuing.

Figure 8-16: Simplified UML sequence diagram for regular component interworking in Pulsar server

122

Instant Synchronization of States in Web Hypertext Applications

8.4

Client

The Pulsar client realizes the minimal stub of the Pulsar system required in the application
model of the WHA client. This stub comprises three major components, Controller, Session andServer Adapter as depicted in Figure 8-17. The Server Adapter is the gatekeeper to the Pulsar
Server. Corresponding to the network interfaces, two Server Adapters are implemented for
Pulsar, one for text-based messages and one for binary messages. The adapter used has to be
determined when a WHA client joins a session. One client must not be connected to the samesession via two or more Server Adapters, but each Server Adapter can serve several session
connections. The Session component maintains the state and processes operations, i.e.
transforms them against local, concurrent operations. In contrast to the server algorithm, theclient-side transformation is a simple, sequential inclusion as explained in section 5.6. The
Pulsar client can maintain multiple connections to sessions in parallel. These connections may
share the same Server Adapters. The Controller manages the sessions per endpoint. Each WHA
client may define multiple endpoints, e.g. for different widgets. Controller, Sessions and state
representations are accessed through the Pulsar Application Programmer Interface (API). In thefollowing sections the design of session management is described in detail, as well as the API toaccess a session in Pulsar. For this version of Pulsar, two Server Adapters are implemented, one
for the text-based network interface and one for the binary network interface. While the first
Server Adapter simply bases on a single JS prototype, the realization of the binary interface withbrowser extensions comprises a number of classes for different execution contexts. Therefore,
the implementation of the Server Adapter for the binary network interface, also called RTSYNC
Server Adapter, is explicitly described in section 8.4.2.

Figure 8-17: Overview of Pulsar client architecture

8.4.1

Session Management

The implementation of the session management comprises a number of JS prototypes, forsimplicity summarized as classes on the UML diagram in Figure 8-18. The entrance to thesession management is the SystemController. The EndpointController provides functionality to123Instant Synchronization of States in Web Hypertext Application

join sessions and manage all open sessions. One client can represent multiple endpoints. This
peculiarity of the design addresses mashed web pages and portals that integrate third party
content. Each EndpointController is associated with a number of ServerAdapters. The
ServerAdapter has to implement the communication scheme, i.e. generation, parsing andprocessing of messages exchanged between client and server. From the viewpoint of the Session,
the ServerAdapter hides the bucket-based transmission of operations. In contrast, apublish/subscribe methodology is provided to the Session. The Session represents the delegate
between ServerAdapter, State and WHA client. It makes sure operations are not only applied to
the local copy of the resource state reflected in the Replica, but also sent to the server. Moreover,
operations received from the server are transformed against local, concurrent operations by the
Session if required.
client::SessionConfiguration+transform(in op1 : Operation, in op2 : Operation) : Operation+instant(in op : Operation) : Boolean+competing(in op1 : Operation, in op2 : Operation) : Boolean
11client::Session

client::Representation
1

1+apply(in op : Operation)+read(in name : String) : String+addSubset(in state : String)*+apply(in operation : Operation) : Boolean+read(in name : String) : String+getId() : String+subscribe(in scopes : List<String>, in listener : SubscribeListener)+unsubscribe(in scopes : List<String>, in listener : SubscribeListener)#setServerAdapter(in adapter : ServerAdapter)*1client::ServerAdapter

1client::EndpointController+join(in session : String, in adapter : String) : Session+leave(in session : String)1*+join(in session : String, in scope : String)+leave(in session : String)+request(in session : String, in operation : Operation)+subscribe(in session : String, in scope : String)+unsubscribe(in scope : String)+onUpdate(in session : String, in callback : ReleaseListener)+onInit(in session : String, in listener : InitListener)+onSubscribe(in session : String, in scopes : List<String>, in listener : SubscribeListener)+onUnsubscribe(in session : String, in scopes : List<String>, in listener : SubscribeListener)

Figure 8-18: UML class diagram of client session management

The SessionConfiguration is a container for all functions provided during session initialization.
The functions are assigned at runtime to the SessionConfiguration instance associated with a
Session. Also the Replica is instantiated from the state representation obtained from the server
during initialization. The initialization process is depicted in Figure 8-19. When a WHA clientjoins a session, not only the session name has to be provided but also the ServerAdapter to be
used for the connection. The SystemController creates a new session and registers theServerAdapter to the session. On creation, the session subscribes at the ServerAdapter for various
events, such as the provision of the session configuration by the server, the reception ofoperations or the availability of the current state for a recently subscribed scope. If callbacks for
all possibly relevant events are subscribed, the Session instance initiates the join. Joining a124

Instant Synchronization of States in Web Hypertext Applications

session already requires naming at least one scope. In the Pulsar implementation a fixed initialscope called global is introduced.

Figure 8-19: UML sequence diagram of client session setup

8.4.2

RTSYNC Server Adapter

The RTSYNC Server Adapter is implemented for the WHA client application model. Processing ofbinary messages and access to the network interface of the user agent host are not supported in
the standardized JavaScript Runtime Environment (JSRE). For this reason parts of the RTSYNC
Server Adapter must be realized in the form of a Web Browser extension or plug-in. The Server
Adapter interacts with the Pulsar server and maintains the state of all sessions. Additionally it
realizes the interface to the client session management.

Figure 8-20: RTSYNC Server Adapter Overview

Figure 8-20 shows the reference architecture of the client component, including the two major
subsystems Synchronization Service and Synchronization Endpoint. The central Synchronization
Service communicates with the server. It receives incoming messages, parses them partially anddelivers them to the corresponding endpoints. For each synchronization connection, a separate
Synchronization Endpoint object is created. Endpoints maintain the session state. Incoming
update messages are parsed and forwarded to the session management. All modifications to the125Instant Synchronization of States in Web Hypertext Application

state during one interval are collected as load for the same bucket. At the end of an interval,
requests are summarized and issued to the server.
The need for a Web Browser extension and the very different extension interfaces of the various
products makes it necessary to either implement an extension for each product or to support
one product only. Since the RTSYNC network interface was primarily realized for theexperimental validation of an efficient IS3 realization, the second option was chosen here. The
RTSYNC Server Adapter is implemented for the Mozilla Firefox Web Browser (Firefox). In
addition to the legacy Netscape Plugin Application Programming Interface (NPAPI) Firefox
supports proprietary browser extensions. In contrast to common plug-ins, an extension canaccess a multitude of browser subsystems and is also the primary means for extending thebrowser core functionality.
For the interaction between the diverse subsystems the Cross Platform Component Object
Model (XPCOM) is utilized. XPCOM is a cross platform component model from Mozilla, similar to
the Common Object Request Broker Architecture (CORBA) or Microsoft Component Object
Model (COM). The functionality of the Mozilla platform is organized in a number of individualcomponents, which are easily reusable. Components may be developed in multiple programming
languages and are accessed through properly defined interfaces. This interoperability ofcomponents with code bases in different languages also enables extensions to access eachcomponent of the Browser from JS code if the required permissions are granted.
Since many internal components of Firefox are implemented with JS, the JSRE distinguishes
privileged code from unprivileged code. Depending on the context of the code, it is executed withdifferent rights. Privileged code and unprivileged codes are summarized in two code contexts,
Chrome and Content. Browser internal code is executed in the Chrome context. Execution of thiscode is considered safe without limiting privileges. Web site embedded scripts, or separate
script content, loaded from external sources is considered unsafe and potentially dangerous.
This kind of code is executed with limited privileges, i.e. in the code context Content.
The support of Firefox for cross-language realization of extensions allows implementation of the
RTSYNC Server Adapter in C++ and JS. The Synchronization Service is implemented in C++ forfast message parsing and the support for network communication. The service is a singleton
responsible for the multiplexing of messages, allowing multiple synchronization connections toshare a single datagram socket. Particular tasks of the service are organized in runnable classes
to enable straightforward dispatching to other threads. These tasks include listening on a UDP
socket for incoming messages, processing update messages (also called sync messages in theimplementation) by parsing their header, and dispatching them by means of the Endpoint
Identifier in the header to their destination Synchronization Endpoint. Additionally, request
messages are constructed from client synchronization requests and sent to the server. If an
update contains a breakout instruction, the Synchronization service also establishes therequired TCP connection.

126

Instant Synchronization of States in Web Hypertext Applications

Figure 8-21: UML diagram of synchronization endpoint in the RTSYNC server adapter

127

Instant Synchronization of States in Web Hypertext Application

The implementation of the Synchronization Endpoint is separated in two distinct components
connected through XPCOM, SyncEndpoint and PulsarConnection depicted in Figure 8-21. The
separation helps to optimize networking and message processing on the one hand, and dataexchange to the WHA client execution environment (i.e. JSRE for Content code context) on theother.
The SyncEndpoint connection to the Synchronization Service is implemented entirely in C++ tosatisfy performance requirements. It benefits from the fast execution of compiled code. Thus,
this component should manage as many tasks as possible and is responsible for all performance
dependent tasks, such as processing and parsing of messages. Requests are stored in this partand request messages are constructed and dispatched when update messages are received. The
incoming state updates are passed to the JavaScript component, which realizes the connection to
the session management. Timers help to determine message loss and anticipate the moment of
the next update from the server. The PulsarConnection implements the functionality required by
the Session component in the session management, such as event subscription, scope
subscription and session setup. Moreover, operations are encoded to and decoded from anappropriate JavaScript representation by this component.

Figure 8-22: Rough UML sequence diagram of RTSYNC client component interaction

The interaction between components is described by means of typical processes. Figure 8-22
depicts a sequence diagram for the interaction of components. Two parallel processes areillustrated: i) an operation request resulting from a user input in the WHA client, ii) an incoming
message from the server.

128

Instant Sy
ynchronizatio
on of States inn Web Hyperrtext Applicattions

The userurequest is reported
d to PulsarC
Connection anda passed tot the C++ SyyncEndpoint. The latterr
collects all operaation requessts and stores them unttil the next updateuis received fromm the server..
iup
pdate messaage from thee server is partiallypparsed and forw
warded to thet targetedd
The incoming
endp
point. In the SyncEndpo
oint, the meessage head is processeed and the mmessage rep
plied with arequest messagee, which is immediately
y passed bacck to the SyncService. T
Then the meessage bodyyis paarsed and forwardedft the PulsaarConnectio
toon. Finally thet
Sessionn is notified
d through apreviiously subsccribed operaation callbacck function.
The interfaceibeetween C++ and JS partts of the Sy
ynchronizatiion Endpoin
nt is also the boundaryybetw
ween the twoo code conttexts. The MozillaM
deveelopment teaam recomm
mends the utilization off
DOM
M events forr communiccation acrosss code contexts. Chrom
me code su
ubscribes for a specificc
DOM
M event and is
i notified ono events raised by codee in the context Conten
nt. To raise ana event theeDOM
M has to be changed,ci.e. the actual datadto be passedpfrom one context to the otheer has to bee
addeed to the DOM
M.

Figuree 8-23: Commu
unication acrooss code contexxts, DOM vs. XPCOM
X

In ann experimen
ntal evaluatiion, the DOM
M based com
mmunicatioon across co
ode contextss was founddto bee significantlly slower thhan direct XP
PCOM calls, as shown inn Figure 8-23. The graph visualizess
the delaysdfor 100 to 100 sub
bsequent fun
nction calls. While the delay for plaiin JS functio
on calls (lineewith diamonds)) always remains below 1ms, thee two crosss context caalling technniques needdsubsttantially moore time inncreasing lin
nearly withh the number of calls. However, thet XPCOM
M
approach (line withw
trianglles) appearss to be mucch faster thaan the DOM
M based app
proach (linee

1299Instant Synchronization of States in Web Hypertext Application

with squares), which needs roughly 2.5ms for a single function call. For this reason the XPCOM
approach is favored over the DOM approach and utilized for implementation.
8.4.3

Application Programmer Interface

At the client, application engineers access Pulsar through the Pulsar Application Programmer
Interface (API). The API provides access to all Pulsar functions, but hides the complexity of theimplementation from the engineer. The starting point of the API is a global object called P4. Thisobject is made available by JS libraries which have to be included by the parent HTML document.
The interface outline is described with an ECMAScript Binding for the Interface Definition
Language in Interface 8-6.
[NoInterfaceObject]interface ServerAdapter {}[ImplicitThis]
interface P4 {Controller
controller (DOMString endpointId);
void
attachAdapter (DOMString adapterName, ServerAdapter adapter);}Interface 8-6: API – global access object

The object supports the following functions:controller

A factory function that returns an instance of a system controller from thememory or creates a new one if no controller with the passed endpoint
identifier has been requested before.

attachAdapter

Registers a server adapter to Pulsar. Adapters are registered to a unique name.
The adapter name is later required to assigned session to a server adapter.

The controller enables application engineers to control the connection of an endpoint tosessions. An outline of the controller interface is provided in Interface 8-7.
The functions are described in the following:join

Tells an endpoint to join another session. In addition to the session identifier, theserver adapter to use and the scopes to subscribe to have to be passed. The function is
asynchronous. Accordingly, callback functions have to be provided for both, success ofjoining the session or failure.

leave

Tells an endpoint to leave a session. Also this function is asynchronous. Callback
functions have to be provided to obtain the results of the procedure.

session A delegate function to access a session once it is available, i.e. joining the session was
successful.

130Instant Synchronization of States in Web Hypertext Applications[Callback]interface SessionCallback {void done(Session session);};[Callback]interface ErrorCallback {void notify([AllowAny] DOMString message);};interface Controller {void join (DOMString sessionId, DOMString adapterName, DOMString [] scopes,
SessionCallback success, ErrorCallback error)(DOMString sessionId,
void leave
SessionCallback success, ErrorCallback error)
Session session (sessionId);}
Interface 8-7: API - session controller

Finally, the session interface and the interfaces of all required callback functions are outlined inInterface 8-8.
[Callback]interface UpdateCallback {void update(Operation[] scopes);};[Callback]interface SubscriptionCallback {void done(DOMString[] scopes);};interface Session {boolean apply (DOMString type, DOMString[] params);
object read (DOMString name, any... option);
attribute UpdateCallback onupdate;
attribute UpdateCallback onbeforeupdate;
attribute ErrorCallback onerror;
void subscribe (DOMString[] scopes,
SubscriptionCallback success, ErrorCallback error);(DOMString[] scopes,
void unsubscribe
SubscriptionCallback success, ErrorCallback error);
DOMString getId();}
Interface 8-8: API - session interface

131Instant Synchronization of States in Web Hypertext Application

The functions of the session interface are summarized below:
apply

Is used to apply an operation to the shared state. The function takes theoperation type and the parameters of the operation.

read

Returns a subset of the shared state, depending on the implementation
provided in the configuration of the Pulsar session. Options are also passed on
to the JS implementation of State.

subscribe

Is used to subscribe one or more new scopes. The subscription is performed
asynchronously to obtain the subscription result callback functions whichhave to be provided. If a scope was already subscribed or could not be
subscribed for some reason (except an error), this scope is not included in thelist passed to the callback.

unsubscribe

Removes a subscription for one or more scopes. Again the list of scopes
passed to the callback reflects only the successful unsubscriptions.

getId

Returns the identifier of the current session.

onupdate

Is a session-wide callback handler for state updates. The function can beprovided by application engineers to process notifications when and which
updates have been performed.

onbeforeupdate

Is similar to onupdate, but called before the updates take effect in the state.

onerrorIs a session-wide callback handler for errors. The function is called when anerror occurs that does not result from calling one of the above functions, forexample a connection loss.

132

Instant Synchronization of States in Web Hypertext Applications

9 Evaluation and Benchmark
IS3 combines known concepts for the realization of interactive real-time applications. While therelated work analysis revealed the novelty of the combination, the constituting algorithms base on
previous findings. Thus, a quantitative comparison of the solution as a whole to related solutions is
not feasible. A quantitative comparison on the algorithmic level would not result in any new
findings. This chapter instead documents the results of evaluation and benchmark tests with the
Pulsar implementation. The tests demonstrate the appropriateness of the algorithms selected for
IS3, confirm complexity expectations and provide basic performance figures for futurecomparisons.

9.1

System Evaluation

The aim of system evaluation test is to confirm the correct implementation of the pipelining
algorithm introduced in section 5.3.1, and to demonstrate the appropriateness of the pipelining
algorithm to achieve fairness in face of delay prone networks.
9.1.1

Setup of Test Environment

The evaluation tests are conducted for a small distributed testbed. The setup, shown in Figure
9-1, comprises five computers connected through an exclusive, local area network based on
Gigabit Ethernet (the figure shows the logical connections).

ClientHost 2
ClientHost 1

Emulator
Host

ServerHost
ClientHost 3Figure 9-1: Setup of test environment

The application run by the Emulator Host works basically like a repeater on the link between
Client Host 1 and Server Host. In addition to forwarding packets, this application can induce
network characteristics common for wide-area network connections, such as packet delay,
packet delay jitter, and packet loss. The characteristics are configured through a SOAP interface
per flow and enforced by netem [94], an established network emulation software for Linuxsystems. For example the network characteristics emulator allows configuring the delay of eachpacket of a specific transport connection from an application on Client Host 1 to an applicationon the Server Host. For the communicating applications, the network emulator is completely

133

Instant Synchronization of States in Web Hypertext Applicationtransparent. They only experience the induced packet characteristics. Table 9-1 summarizes thetest bed components and their characteristics. The distributed setup is chosen to bypass
scheduling mechanisms of operation systems and virtual machines, as well as to obtain results
which present the performance of the logical components in isolation. The user agent is Mozilla
Firefox 3.0.1.
MachineServer Host
Client Host 1
Client Host 2
Client Host 3
Emulator
Host

Configuration
Hosting the Pulsar server and a Web server; Running Windows Server 2008 64bit; 8GB of
RAM, Intel Xeon 2GHz quad core CPU, and two network adapters.
Hosting WHA Clients; Running Windows XP 32bit with 2GB of RAM, and AMD Athlon 64
2.2GHz CPU.
Hosting WHA Clients; Running Windows Vista 32bit; 2GB of RAM, and Intel Core 2 Duo
2.4GHz dual core CPU.
Hosting WHA Clients; Running Windows XP 32bit with 2GB of RAM, and Intel Pentium 4
2.8GHz CPU.
Shaping network traffic. Running Ubuntu Linux 9.04 32bit; 1GB of RAM, Pentium 4 3,2GHz
CPU, and two network adapters.

Table 9-1: Configuration of testbed machines.

9.1.2

Test Procedure

For the system evaluation, a simple web application based on Pulsar is realized. To investigate
the impact of network characteristics as directly as possible, the binary network interface ofPulsar is chosen for the tests. The qualitative difference to comet techniques is shown in [95].
The test application shares one object between all clients. Object modifications are exchanged inoperation mode (1) - continuous convergence and effect simultaneity. WOS is used as statemodel. For the WOS inclusion function, the pseudo-random tie-breaking method described in
section 7.4 is activated.

Figure 9-2: Evaluation web application deployed to the testbed (logical setup)

The test application implements two client types, an active client and a reactive client. An active
client (also called master) issues operations. A reactive client (also called slave) only responds tooperations by creating its own operation for each one received. Figure 9-2 shows the web
application deployed to the testbed. Each machine runs exactly one client in this setup. The
actual test procedure is summarized in the following:134

Instant Synchronization of States in Web Hypertext Applications

1. The master starts the test procedure by issuing one operation on the shared object. The
time Tissue is recorded.
2. All clients receive an operation from the server reflecting the operation of the master.
The master itself notes the time Teffect and calculates the interval taction := Teffect - Tissue.
3. As soon as a slave receives the operation, it updates the shared object by writing aunique identifier to the shared object with an operation of type set. Since all slaves
receive the operation in the same interval, the resulting set operations are competing.
Only one of the slave requests can succeed.
4. The server processes the operations and sends updates to all clients. The master logs
which slave request has been successful. Additionally, the master records the time
Tfeedback. and calculates the interval treaction := Tfeedback – TeffectDuring the tests the time is taken in Pulsar client directly, as well as with the open packet sniffer
Wireshark [96]. A sequence diagram visualizing the procedure is shown in Figure 9-3. For
simplicity, only the master client and one slave are depicted. In practice two or more slave
clients join the same session, as shown in Figure 9-2.
The binary Pulsar network interface supports an automatic adaptation of the bucket interval
duration T introduced in section 5.3.1. The minimum interval duration is set to 20ms to avoid
overload on the client machines distorting the results. The maximum interval duration is set to120ms. The pipeline depth is set to a = 1, thus the play-out delay is Δ= aT = T. The test
application is configured to repeat each test 1000 times. The average values of the results should
be statistically meaningful.
treaction

tactionMasterClientOactionOreaction

Slave
ClientR

U

R

U

Server∆Figure 9-3: Sequence diagram of test procedure

9.1.3

Testing Interaction Delay

Interactions in IS3 base on mutual write operations to objects. The period which elapses
between a write operation of one user and the play-out of a write operation reflecting a
response from another user is called interaction delay. The interaction delay is defined as
tinteraction := taction + treaction. As suggested by Figure 9-3 the time span taction is defined by taction := Δ +135

Instant Synchronization of States in Web Hypertext Application

tx. The constant Δ is the play-out delay introduced in section 5.3.1. The variable tx represents theinterval between the moment a user issues an operation Oaction, above also called Tissue, and themoment of transmission with a request message. In the test application operations areautomatically issued at random times by the master client. The time span taction is referred to assynchronization delay in the following.
Proposition
The results are average values based on a large number of records. It is assumed that tx
approximates to its probabilistically expected value∆( ) = . The average value forsynchronization delay is thus taction = 1.5 Δ.
A user can react to Oaction as soon as the operation effect is played out. Analogously the slave
client responds to a received operation immediately with an operation Oreaction. The reception ofan update message is also the beginning of a new interval at the client. Thus the client has to
wait for the end of the interval and the next update message from the server to deliver Oreaction
with a request message. Since the pipeline depth is a=1, the idle time is Δ. The operation isprocessed by the server and reaches the originator of Oaction at the beginning of the next interval.
This means treaction := 2Δ and thus the average value of tinteraction=1.5 Δ+ 2 Δ=3.5Δ.
It is assumed that packet loss, packet delay and packet delay jitter are negligible. All packets andthus messages and operations are on time. The time points are recorded for an interaction
between two clients, one slave and one master. The second slave introduced in the description oftest procedure is inactive.
9.1.4

Results of Interaction Delay Test

The measurement results for the synchronization delay are depicted in Figure 9-4. During themeasurements the play-out delay Δ is increased in steps of 10ms. The values for thesynchronization delay are mapped to the corresponding play-out delay. The figure contains fourgraphs, i) the highest individual value measured throughout the test runs (upper end of errorbar), ii) the average value over all test runs, iii) the lowest individual value measured throughthe test runs (lower end of error bar) and iv) the expected value for the mean over all test runs.
The mean of the recorded values matches the expectations for the synchronization delays. The
negative variation of individually measured values can be explained with the randomly assigned
value for tx,which causes taction to vary in the range 2Δ ≥ taction ≥ Δ. Thus, the lowest individual
value that can be found theoretically during the test runs is taction = Δ. The measurements confirm
this expectation in practice. The positive variance of individually measured values significantly
exceed the expected maximum value taction = 2Δ. The values greater than the expected maximum
value occur with a frequency that has a negligible impact on the average value. These outliers
can be explained with load peaks at the client machines, e.g. caused by garbage collection
mechanisms of user agents.

136

Instant Synchronization of States in Web Hypertext Applications

Synchronization Delay (in ms)

350.00
Average

300.00Maximum positive and negative deviation
250.00

Expected

200.00150.00100.00
50.00
0.00
20.00

30.00

40.00

50.00

60.00

70.00

80.00

90.00

100.00110.00120.00Configured play-out delay ∆ (in ms)

Figure 9-4: Measurement results for the synchronization delay with minimum and maximum deviation

The measurement results for the interaction delay are depicted in Figure 9-5, which again
contains four graphs, i) the highest individual value the interaction delay throughout the test
runs, ii) the average value over all test runs, iii) the lowest individual value of the test runs, andiv) the expected value of the interaction delay for the average over all test runs.
700.00
Average

Interaction Delay (in ms)

600.00Maximum positive and negative deviation
Expected

500.00400.00300.00200.00100.00
0.00
20.00

30.00

40.00

50.00

60.00

70.00

80.00

90.00

100.00110.00120.00Configured play-out delay ∆ (in ms)

Figure 9-5: Measurement results for the interaction delay with minimum and maximum deviation

The average values match the expected values for the interaction delay. The negative variance ofthe measured values is again explainable with tx.Individual values of the interaction delay can befound in the range 4Δ ≥ tinteraction ≥ 3Δ. The positive variance again reflects a number of outliers
that do not appear frequently enough to have an impact on the average values.
The measurements of synchronization and interaction delay indirectly confirm the reaction
delay treaction of IS3 with treaction = 2Δ. As long as the play-out delay Δ is less than 150ms a
reasonably natural presentation of human interactions is given.

137

Instant Synchronization of States in Web Hypertext Application

9.1.5

Testing Fairness of Conflict Resolution

An important criterion for the design of IS3 is to support competing interactions, i.e. guarantee
fairness. Fairness not only means to replay operation effects simultaneously, but also to processcompeting operations independently from network characteristics. As introduced in section
9.1.2, the test procedure is explicitly designed to provoke competing operations of slave clients,
i.e. concurrent write operations of different values to the same object. A modified WOS inclusion
function ensures a random distribution of success at the server as long as the concurrent
operations are received on time. Success means the object finally has the value intended by aclient operation. With two slave clients, a resulting success rate of 50% is expected per slave. A
deviation of less than ±2.5% is assumed to be tolerable. The mean of the individual success rate rof each client (i.e. write success across all iterations) thus has to be within the range 52.5% ≥ r ≥47.5% to be considered fair.
Proposition
Packet delay tdelay does not affect fairness as long as the overall time for request message∆

transport does not exceed . Since the network interface used for the tests sends each message
with a single datagram, the time for message transport is mainly comprised of tdelay and a∆negligible message processing time. If a request message is on time, i.e.

< , the enclosed

operations are on time. Competing operations received on time are treated equally in conflict
resolution. Consequently, an even distribution of operation success among the slave clients is
expected. Also packet delay jitter does not affect fairness as long as

+

<

∆

for any

variation tjitter from the average delay. In the test procedure, late request messages and theiroperations are ignored by the server. In this case, the originating client is in an inferior position.
A different behavior is observable when packets are lost. Although the network interface used in
the tests retransmits a lost message and thus the lost datagram, the retransmitted message isinevitably late. Consequently, the success rate of a client should decrease when message loss
increases.
The binary network interface used for the tests supports an automatic adaptation of the bucket
interval length T per session. With every late message, the play-out delay Δ is increased by 20ms∆

and T is increased by . Since the pipeline depth for the tests is a=1, T is increased in steps of
20ms up to a predefined maximum interval length of 100ms. The initial interval length is 20ms.
9.1.6

Results of Fairness Test

For the measurements in the fairness tests, packet delay, packet delay jitter and packet loss wereartificially generated by the network characteristics emulator. The datagrams and thus themessages sent by the slave client on Client Host 1 are exposed to the generated network
characteristics.

138

Instant Synchronization of States in Web Hypertext Applications

Figure 9-6 depicts the success rate of the client with delay prone connection to the server. The
test is repeated with different packet delays. For each tested packet delay, the success rate of theclient is within the expected range. The measurements do not indicate any correlation of packet
delay and success rate. The automatic adaptation of the interval duration T ensures that after at
most three late messages, all artificially delayed messages are on time. Operations of these threelate messages are rejected. An effect on fairness is not observable since the test was conductedSucccess Rate (in %)with 1000 iterations on the same session.
53.00
52.00
51.00

52.37
Success Rate
50.45

50.00

51.55

51.01

50.75

50.50

49.85
48.81

49.00

51.20
49.40

49.05

48.35

48.00
47.00
46.00
5.00

10.00

15.00

20.00

25.00

30.00

35.00

40.00

45.00

50.00

55.00

60.00

Packet Delay (in ms)

Figure 9-6: Success rate of a client with delay prone connection

Figure 9-7 depicts the success rate of a client with packet delay jitter prone connection to theserver. For the measurements, a constant delay of 50ms was chosen for each message, while thedelay jitter varied randomly between 0ms and 40ms. The measurement results show that packet
delay jitter has not significantly impacted on the success rate in the scenario. The automatic
adaptation of the interval duration T ensures a save interval duration is reached at the latest
after four late messages. In contrast to the above discussed measurements for packet delay, theadaptation is not terminated after a number of heading test runs. Since messages are exposed to

Succcess Rate (in %)varying delays, late messages are not necessarily consecutive.
52.00

51.65

Success Rate

51.50
51.00

50.85

50.75
50.35

50.50

49.90

50.00
49.50
49.00
0.00

10.00

20.00

30.00

40.00

Packet Delay Jitter (in ms)

Figure 9-7: Success rate of a client with jitter prone connection

As depicted in Figure 9-8, packet loss clearly decreases the success rate of the affected client.
The success rate is measured as the probability of losing individual packets increases. For
example, with a loss probability of 50% in roughly half of the 1000 test runs operations of theaffected client are late. The success rate for about 500 timely operations remains about 50%.
The total success rate thus decreases to 25%. The client is obviously in an inferior position. The
measured values beyond 30% loss rate appear to be slightly irregular. For those values, the139Instant Synchronization of States in Web Hypertext Application

actual number of test runs is partially less than planned. Due to the large number of lost

Succcess Rate (in %)messages the client implementation occasionally skipped test runs.
60.00

50.75

50.00

45.51

Success Rate
43.12

40.00

41.47

39.17

38.72

34.55

30.00

31.19

30.43
23.58

26.22

45.00

50.00

20.00
10.00
0.00
0.00

5.00

10.00

15.00

20.00

25.00

30.00

35.00

40.00

Probability of Packet Loss (in %)Figure 9-8: Success rate of a client with loss prone connection

Although the measurements are conducted with the binary implementation of the Pulsar
network interface and thus a datagram based connection, the measurement results are also of
significance for the text based network interface. Although the impact of packet delay and packet
delay jitter is not as direct in TCP based connections (e.g. HTTP, WebSockets) as in UDP based
connections, both phenomena have a comparable effect on the transmitted data stream and will
influence the transport time of messages. The same is true for packet loss. A detectable side
effect of TCP retransmission is a lag in the data flow. A countermeasure, for example an increasein the TCP input buffer size, has a negative impact on the timeliness of transported messages.
More results are published in [97].

9.2

System Benchmark

The aim of the system benchmark tests is to confirm complexity estimations of the algorithms
and to determine the performance of the Pulsar implementation for IS3. The following sections
describe test environment, setup, procedure and results.
9.2.1

Setup of Test Environment

The test environment for the benchmark tests comprises two machines, a Server Host and a
Client Host. Both are connected to an isolated Gigabit Ethernet network without otherparticipants. The configuration of both machines is summarized in Table 9-2. The distributed
setup is chosen to minimize side effects caused by sharing resources between multiple
applications on one machine.
MachineServer Host
Client Host

Configuration
Hosting the Pulsar server; Running Ubuntu 10.10 32 Bit Desktop Version; 1GB of RAM, andGenuine Intel CPU T2400 Core Duo 1.83GHz.
Hosting test client with Pulsar client stack; Running Windows 7 32bit; 2GB of RAM, andGenuine Intel CPU T2500 Core Duo 2.0GHz.

Table 9-2: Configuration of machines in benchmark testbed

140

Instant Synchronization of States in Web Hypertext Applications

9.2.2

Test Procedure

The architecture of IS3 is centralized. The performance of an IS3 implementation like Pulsar thus
mainly depends on the server. To investigate the server behavior in face of scaling load, i.e.
number of clients and concurrent operations, a test setup with real web user agents is
inappropriate. 100 and more browser instances on a single client host would dramatically slow
the host machine down. The actual server performance figures would be masked in the test
results. In contrast to delay and fairness tests, the Pulsar system is therefore tested in isolation.
A simple dummy client is used in place of the regular WHA client. The dummy client is alightweight console application only utilizing the Pulsar client stack. For the benchmark tests,
the text-based client stack implementation is used in combination with an implementation of the
WebSocket protocol draft 76 [98]. For the server, the client implementation looks like a proper
one integrated with the user agent. A single instance of the dummy client can open and maintainconcurrently several hundred synchronization connections to the server, i.e. mime endpoints.
The Client Host runs the dummy client, while the Server Host runs the Pulsar server. Object
modifications are exchanged in operation mode (1). The operation mode, however, does notaffect the performance. The computation load at the server is the same for both operation
modes. WOS is used as state model.
Once started, the dummy client initiates a predefined number of endpoints and joins the samesession with all endpoints. Depending on the test configuration, the number of operations perclient is varied. Operations of different clients are defined to conflict. The time between thereception of the first request message and the sending of the last update message per interval ismeasured for each configuration. All tests are repeated 100 times for each configuration. The
measurement procedure comprises the following four steps:
1.

The server receives and parses messages of all clients. Since messages can arrive at any time
during the first half of the play-out delay, measuring the interval between receiving the firstmessage and receiving the last message is inappropriate. Instead, the times required toparse the single request messages on reception are recorded and finally summed up to
treceive. Since the reception of messages from different clients occurs in parallel at the server,
treceive is only an indicator for the overall time complexity of message parsing. Play-out delay
Δ is set to 2s, which is far beyond a reasonable value for an application. This setting,however, ensures the server will wait long enough to receive the message of all clients
issued for an interval on time. The pipeline depth is set to a=1 for the tests.

2.

The server processes the operations contained in the request messages. All operations areintentionally conflicting and thus subject to the transformation procedure. At the beginningand at the end of the transformation the time is recorded. The interval between the twotimestamps is referred to as ttransform.

141

Instant Synchronization of States in Web Hypertext Application

3.

The resulting client operation sequences are serialized as update messages and sent to theserver-site WebSocket implementation. Again the time is recorded at the beginning and theend of the process. The interval is referred to as tsend.

9.2.3

Testing Performance

The two variables which mainly affect the performance of the IS3 server and its implementationin Pulsar are the number of messages per interval, i.e. the number of clients on the same session,and the number of operations per message. Increasing numbers of messages and operations
result in an increasing demand on processor time and memory of the machine hosting the Pulsar
server. This increasing demand reflects in the overall time taken for processing per interval.
Section 5.6 closes with a discussion of the time complexity of the transformation algorithm. The
derived estimates predict an exponential time complexity for the control algorithm with respect
to the number of requests per interval. Also they predict a quadratic time complexity of thesequence inclusion algorithm with respect to the number of operations per client and interval.
The time complexity for parsing messages is linear with respect to the number of clients andoperations per client and interval. If x clients send n operations, x request messages and xn
operations have to be parsed. The time complexity for serializing and sending messages isquadratic with respect to the number of operations per client and interval. Each received
operation is forwarded to every client in the test setup. With n operations per client and x clientsxn2 operations have to be serialized and send.
The intention of the performance tests is to validate the time complexity estimates and toprovide benchmarks for different test configurations. The benchmarks point out limits of Pulsar
when applied in practice.
9.2.4

Results of Performance Tests

The first part of the benchmark test addresses the interval transformation algorithm
documented in Algorithm 5-2. 10 to 100 endpoints are connected to the server. For each test
run, the rate number of endpoints is increased by 10. Each endpoint requests exactly one
operation per interval, all operations compete. Thus, the time complexity for all list
transformations performed to calculate the transformation matrix explained in section 5.6 isconstant during this test. The measured times directly reflect the time complexity of the intervaltransformation algorithm estimated in the same section.
Figure 9-9 shows the overall processing time tprocessing = treceive + ttransform + tsend in milliseconds. The
shaded areas in the columns represent the components of tprocessing. The measurements wererepeated 100 times and the mean taken for each configuration. The highest measured individual
variation from the mean was 247.93%. However, the means best show the trend of theperformance and confirm the estimated exponential time complexity.

142

Instant Synchronization of States in Web Hypertext Applications

180
160

send
transform

Mean processing time (in ms)

140

receive

120
100
80
60
40
20
0
10

20

30

40

50

60

70

80

90

100

Total number of request messages (one operation per message, all operations compete)Figure 9-9: Mean processing time for increasing numbers of clients and a constant number of operations per client.

A configuration with 100 clients and one operation per request message causes a processing
time above 150ms. This time has to be found between the reception of the last request message∆

and the end of in order not to extend the play-out delay unintentionally. The bucket interval
duration T has to be chosen for an application. An alternative strategy is to implement thecontrol algorithm to immediately fit a list of operations in the transformation matrix on
reception. The effect is the same as for Algorithm 5-2, but the bulk processing of operations is
potentially better balanced over the first half of the play-out delay.
Figure 9-10 again depicts treceive and tsend. As expected the overall time required for message
parsing grows linearly, while the time for message serialization and sending grows
quadratically. Although both curves are not shaped perfectly, they allow derivation of the above
mentioned trends. Deviations of at most 4ms are probably caused by peculiarities in theimplementations of included third party libraries (e.g. buffer flushing behavior), which comeinto effect with specific test configurations.
The second part of the benchmark test addresses the list inclusion described in Algorithm 5-1.
For this part of the test, ten request messages arrive at the server per interval. All messages
contain the same number of operations. Each operation competes with all operations from otherorigins. The number of operations per message is increased from 1 up to 15 throughout the test
iterations. Each test is repeated 100 times.

143Instant Synchronization of States in Web Hypertext Application

35
send

30

receive
Mean processing time (in ms)

25
20
15
10
5
0
10

20

30

40

50

60

70

80

90

100

Total number of request messages (one operation per message, all operations compete)Figure 9-10: Mean receive and send time for increasing numbers of clients and a constant number of operations perclient.

Figure 9-11 depicts the results for the components of tprocessing as columns. Again the mean of themeasurement results is taken. The highest deviation of a maximum value from thecorresponding mean throughout all iterations is 23.01ms. The absolute deviation of maximum
values from mean develops linearly. As expected, ttransform grows quadratically with respect to thenumber of operations per request message.
250
send

Mean processing time (in ms)

200transform
receive

150

100

50

0
10

20

30

40

50

60

70

80

90

100

110

120

130

140

150

Total number of competing operations (equally distributed across the request messages of 10 clients)

Figure 9-11: Mean processing time for increasing numbers of operations per client and constant a number of clients.

Ten competing clients, each originating 15 operations per bucket interval, cause an overall
processing time of almost 200ms. Unless the bucket interval duration for an application ischosen greater than 1000ms, 15 operations per interval and client is a rather unrealistic
assumption. However, one reason for the poor performance of the list inclusion algorithm here

144

Instant Synchronization of States in Web Hypertext Applications

is probably the runtime interpretation of a JS inclusion function. Using the JS implementation of
the WOS inclusion function is the default option for a session configuration which was alsochosen for the benchmark test. The Pulsar implementation also supports inclusion functions
implemented in Java. An implementation of the WOS inclusion function in Java can be expected
to have had a positive impact on the performance of interval transformation algorithm too.

145

Instant Synchronization of States in Web Hypertext Application

10 Case Study
This chapter documents the review of the IS3 concept and its reference implementation Pulsar withrespect to the objectives of the thesis. Two software engineering processes are researched in a casestudy. The documentation starts with a summary of prospects to be verified and concludes with asummary and analysis of the findings.

10.1 Propositions and Methodology
The objective of this work is to provide a software framework that supports the engineering ofreal-time interactive applications. Software engineers are intended to experience the software
framework as a tool and a ready-to-use building block that simplifies their task and saves themtime for other aspects of the application to be produced. The benchmark and evaluation tests
documented in chapter 9 showed the sufficient operation of Pulsar and thus the IS3 concepts,
but they cannot confirm whether the objectives with regard to the engineering process havebeen achieved or not. For this purpose a Case Study is conducted which shall support thefollowing propositions:
1)

Pulsar can be used to realize applications that support real-time collaborative as well ascompetitive interactions.

2)

Utilizing Pulsar to realize real-time interactions takes less time than then implementing apropriety solution.

A suitable case to investigate the impact of Pulsar in software engineering is an exemplary
software engineering project. To cover usage spectrum of Pulsar, two cases are researched. The
first case addresses collaborative interaction, the second case competitive interaction. The firstcase is the realization of a collaborative editor for rich text documents. The second case is therealization of an online adaption for the game Bomberman. Although the cases address different
applications, the processes should result in similar findings with regard to the propositions.
Proposition 1) is supposed to be verified when the teams produce applications that fulfill theapplication requirements summarized at the beginning of sections 10.2 and 10.3 respectively. As
evidence for the correctness of proposition 2) the following aspects are investigated:a) The learning effort, i.e. the time a team needs to learn and utilize Pulsar for theenvisioned application.
b) The scale of program code (lines of code) needed to adapt Pulsar and its interfaces to theapplication context.
c) The familiarity of team members with the algorithms and concepts implemented in
Pulsar before entering the case study.
d) The total time needed for the realization of applications.

146

Instant Synchronization of States in Web Hypertext Applications

For the collection of evidence both software engineering processes are observed over time, forBomberman on a weekly basis, for the text editor on a daily basis. Additionally the members of
the engineering teams are interviewed about their skills before and after the projects, as well as
their experience with Pulsar. Insights into the program code produced by both teams help tounderstand the problems the team members are facing when integrating Pulsar with theirapplications. Thus, i) direct observations, ii) interviews, iii) code reviews, and iv) requests fortechnical support are the data sources forming the base of triangulation in this Case Study.

10.2 Case: Collaborative Text Editor
Application: The Collaborative Text Editor enables people to write and style text collaboratively
on the web. The editor is identical to text editors realized as single-user desktop applications. A
marker, the caret, shows where text is modified if the user starts writing or deleting, while thecaret position can be changed by arrow keys and mouse actions.

Figure 10-1: Screenshot of the application resulting from the case “collaborative text editor”

Text is styled by selecting a section and choosing the preferred style option for this section froma menu. The text editor in this case supports only simple style options such as bold, italic, change
font-size, change font-style and change colors. Additionally, hyperlinks and images can beinserted into the text, and text from the clipboard can be pasted in. Figure 10-1 depicts ascreenshot of the final editor. The difference of the collaborative text editor to a single-user
editor is the immediate reflection of user actions in all open copies of the text. Typed characters

147

Instant Synchronization of States in Web Hypertext Application

appear and styles take effect at a copy without affecting the locally editing user. Instead ofmanually saving changes, the edited text is saved automatically every 30 seconds from themaster state of the resource – user can only export the current state as a portable document if
needed.
The implementation of the text editor here is a subproject of larger software project on therealization of an integrative frontend for various communication channels, such as phone, SMS,
forums and collaboratively editable documents. The project structure nonetheless ensures anisolated realization of the text editor.
Team: The collaborative text editor is realized by a team of two software engineers, a computerscience student and a computer science graduate. Before the latter two started with the text
editor they realized other components in the project in which the editor is embedded.
Accordingly, they are familiar with the modern application model of the web and theprogramming languages required for the creation and configuration of a Pulsar-enabledapplication, i.e. JS and Java, and they have worked with Pulsar and the WOS model before. They
used it for the realization of smart message inboxes and contact lists with rich presence featuresand did not need to change the server configuration. Initial interviews with the team revealed
that both engineers had not implemented a rich text editor with HTML and JS before. They have
not realized a collaborative text editor before or studied relevant solutions. Nonetheless, theyknow the capabilities of OT and DS from version management systems, office solutions andonline services like Etherpad [99].
Engineering Process: The engineering activities for the collaborative text editor began with a 2hour face-to-face meeting with the manager of the parent project. The application and theplanned features were first presented to the team, then discussed and finally collected in afeature backlog. 36 person days are granted to the team for the features in the backlog. The list
reflects the capabilities of the editor application introduced above. The original specifications
came from the customer of the parent project. Starting with the kickoff, the team members were
sporadically observed throughout each working day. Additionally, their progress and problems
they faced were recorded during daily SCRUM meetings. The resulting insights in theengineering process are documented in the following.
The team used a WHA and Pulsar server provided for the parent project. The Pulsar server andthe WHA server were hosted on the same machine, so the team could use the plain serverinterface to connect both servers. Consequently, they saw no need to implement a robot in orderto realize the automatic saving of documents and loading of documents. Since the postgraduate
and the student were already familiar with client and server interface of Pulsar, they began theengineering with researching best practices for implementing a rich text editor with HTML and
JS. As a first step they realized a very simple text editor without styling options, copy and paste
or other convenience features. Code reviews show that the text input based on an editable
HTML5 layout element. The text was mapped to an array of the WOS model, while each148

Instant Synchronization of States in Web Hypertext Applications

character represented a separate array field. Pulsar was used in its default configuration.
Whenever a key press event occurred on the editable layout element, the event type wasanalyzed and an appropriate operation to the character array in Pulsar derived. For that purposethe caret position relative to the beginning of the text had to be obtained from the range API[100] of the DOM. The key-press event of the “A” key was for example mapped to an insert
operation; a backspace or remove key was mapped to a truncate operation. Operations received
from the server, i.e. insertions to or deletions from the array, were applied to the HTML layout
element with the help of the HTML5 editing API [101].
This first iteration of realizing a collaborative editor took only four person days, after which theteam was able to fully utilize Pulsar in their application context. But this first iteration also
revealed challenges the team had to face when starting to support rich text. The editing API ofbrowsers is not fully implemented in all user agents which the parent project addresses. For
example, the insertion of a new paragraph does not work properly in Mozilla Firefox version 4.
The API for accessing text selection and text ranges is implemented slightly differently in all useragents. However, the consistency of the states presented to users depends on the reliable
detection of changes to the text and the reliable application of the effect to all currently viewed
instances of the text. Solving this challenge cost the team more than 90% of the engineering time
while less than 10 % was spent on configuring and integrating Pulsar as the observations andinterviews document in triangulation.
As a first step towards a rich text editor, the team extended the character array representing thetext in Pulsar to a kind of token array. For that purpose they adapted the idea of nesting markup
with parentheses from XHTML. The example below shows formatted text and the corresponding
array in Pulsar as JSON [39] representation.
Text:

hello world

Array:["h", "e", "l", "l", "o", " ",{start: "bold"}, "w", "o", {start:"i"}, "r", {end:"i"}, "l", "d", {end:"bold"}]

To assign a formatting to a text section a start and an end object have to be added as tokens to
the array. Object attributes define the token type. The tokens represent a direct mapping of themarkup elements in the editable HTML container element for the editor (e.g. <i> and </i> for theabove example). Adding the tokens for one style (e.g. italic) requires the application of at least
two Pulsar operations to the text. Thus, the user action of applying a style to the text cannot bemapped to one atomic operation in Pulsar with this approach. As a consequence, style-related
operations cannot be fully treated by the inclusion mechanism of Pulsar, which results in
suboptimal state text representation when utilizing WOS. This problem is addressed in a second
iteration of the editor that has been developed after the end of the case study. The findings are
summarized below. Besides this drawback, the implementation of the WOS model delivered
with Pulsar proves to be useful for the realization of rich text editors. Team observations andcode reviews, the sources of the above data, make clear that the adaption of Pulsar in the context

149

Instant Synchronization of States in Web Hypertext Applicationof the editor requires no implementation of a middle layer or complex data mappings. Thus, theteam had to spend no extra days on making Pulsar useful in the application context.
In the first iteration of the collaborative editor, the reliable detection of the actual changes a useragent renders in response to a user action was identified as challenging. To avoid capturing all
different cases in the code and enable a potential support of user agents that are not explicitly
addressed by the parent project, the team decided to implement the interpretation of user
actions themselves. For this purpose they firstly prevented the default reaction of a browser in
response to a user action. Secondly, they interpreted the event and modified the DOM below theeditable layout element to reflect the user intention. While in an early implementation the DOM
manipulation was handled with the editing API, the team members later implemented DOMchanges themselves. A peculiarity the team did not regard from the beginning is the hybrid
markup element. For example a paragraph defines a style for a text section, such as indention,
but also means a line break. Consequently, there are two valid caret positions between two
adjacent paragraphs, i) the end of the last line of the first paragraph, ii) the beginning of the firstline of the second paragraph. This peculiarity caused the team to make a detour at the cost of
three person days to revise the detection of the caret position and the handling of hybrid
markup elements. At the server, the team triggered the automatic saving of text documents by atimer. The saving procedure first reads the token arrays and then stores text and styles
persistently. Hybrid markup elements are reflected by whitespaces in the text. Although theefforts around handling markup in the browser are not related to Pulsar, the above description
as obtained from observations and interviews helps to understand where the time of the team
was actually spent.
The team finished the collaborative text editor after 41 person days, five person days more thanplanned. Although the editor generally worked well, users later documented a couple of cases
where the editor did not behave as expected. The team identified weak points in the applicationof styles as a major origin for the unexpected behavior. Concurrent operations on the same
section of a text did not result in a minimum state representation. For example, if two users
concurrently make the same word bold, the token array will finally contain two begin and two
end tokens for this style. Some styles even base on non-binary switches, such as the text
decoration. A text section can be underlined, blinking, over-lined and crossed out inclusively or
exclusively. To remove the underlined switch from a subsection of a text that is also crossed out,a markup to disable all switches has to be added and then markup to cross out the noneunderlined subsection again. The implementation of the collaborative editor did not handle
those peculiarities in recurrent style changes for the same text section perfectly as the teamconcluded in an interview. During the implementation the team also recognized a drawback ofusing the token array for rich text representation. Each character-related user action had to bemapped to an operation. If text is pasted to a document or a marked text section is deleted, as
many operations are created as characters are affected. Accordingly the overhead for transport
and inclusion at the server is immense. For a correct inclusion, however, one insert operation for150

Instant Synchronization of States in Web Hypertext Applications

multiple characters and one range delete operation would be more appropriate, as the teamconcluded.
At this point, the engineering team had sent five emails documenting bugs in the Pulsar
implementation. All bugs were soon fixed and new builds of Pulsar provided to the team without
significantly delaying the engineering process. At least the observations and the interview
results did not document any substantial effect on the engineering process.
After the end of the parent project, the team revised the whole implementation. Although thisrevision did not affect the findings of the case, the approach chosen by the team and the results
are valuable in the context of this thesis. For this reason the revision phase is also documented
here.
Name
INS

Operation Description
Insert formatted text

DEL

Delete text

PSET

Apply one style to aparagraph (e.g.
indention)

RSET

Apply one style to anarbitrary text section

BR

Insert a new paragraph

EINS

Insert non-text element
such as an image or
hyperlink

Parameters
Document
Position
Text
StylesDocument
Position
LengthDocument

Parameter Description
Operation target
Absolute position in target
Text to insert
Intended formatting of the text after insertion
Operation target
Absolute position in target
Number of characters to remove
Operation target

Position

Absolute position of paragraph in target

Length
Style

Number of affected characters (required forinclusion)
Style to be applied

Document
Position
LengthStyle
Document
Position
StylesDocument
PositionType
Reference
Parameters

Operation target
Absolute position in target
Number of affected characters
Style to be applied
Operation target
Absolute position in target
Intended formatting of the text after insertion
Operation target
Absolute position in target
Type of element (e.g. image, hyperlink, frame)
Reference to element content
Any element parameters

Table 10-1: Operation types for rich text state model

The team first decided to replace the WOS model by a rich text state model inspired by the OpenDocument Format (ODF) [102]. A text document comprises a number of paragraphs, eachparagraph a number of runs. A run represents a sequence of characters with the sameformatting. Changing the formatting of a subsequence of characters in a run results in one or two
new runs, depending on whether the subsequence is adjacent to run begin/end or not. The teamcreated a Java and a JS implementation for this new model. The Java implementation is similar to
Apache POI [103], which simplifies the realization of the text export as standalone ODF
document (e.g. Microsoft DOCX). The JS implementation does not use any intermediate data151

Instant Synchronization of States in Web Hypertext Application

structure such as arrays. Instead, the model is directly implemented on the DOM. Paragraphs are
represented by the respective HTML element, runs by SPAN elements. The support types ofoperations on this state model are summarized in Table 10-1. As the table shows, the operation
types represent user actions more directly than operations on the token array. The mapping to arepresentation of the resource state is more difficult, but the inclusion can now respect user
intentions. The implementation of the inclusion function realized by the team is appended in
Annex C. All of the above insights are derived from code reviews.
After implementing the inclusion function, the team decided to create separate sessions for eachdocument. Although the scope concept would have been the appropriate choice for clustering
potentially competing operations, the mapping to different sessions has no negative impact on
the number of messages or message size. The team justified the decision with a better balancing
of load at the server, since each session has its own timing. However, the team did not check the
proposition. All JS functions coded by the team, such as inclusion, conflict prediction or schema
function were tested with unit tests by utilizing Rhino. Integrated tests were conductedmanually and evaluated by analyzing logs in all three iterations of the engineering process.
transformlistvariable: ListOperation × ListOperation → ListOperation × ListOperationtransformlistvariable:(A, B) = (A', B') where
if |B| = 0 then=A
= List()elseif |A| = 0 then= List()=B
else= transformi( ( ), ( ))

1
2
3
4
5
6
7
8
9
10
11

= transformi( ( ),

12

(

13

(

14
15

=
endif

,

( ))

) = transformlistvariable(,,) = transformlist variable( ( ),
(

,

( ))
(

,

)

)

Algorithm 10-1: Recursive list transformation for inclusion function that returns an operation list

At the end of the revision the team resolved all drawbacks of the original editor version, but
identified a worthwhile feature for the inclusion function and requested a change in the Pulsar
implementation. The change is realized and documented here for completeness. The inclusiontransformation is defined to map an operationthat includes the effect ofand a competing operation

to an operation. If an insert operation in the editor refers to a position that is

also covered by a concurrent range delete, the insert operation has to be disabled. This violates
at least one user’s intentions. Alternatively the delete operation would have to be split at theclient that originated the insert into a delete before the insert and a delete behind the insert. The

152

Instant Synchronization of States in Web Hypertext Applications

original inclusion transformation, however, returns only one operation. For this reason the teamsuggests an inclusion function that can return zero, one, or multiple operations. Since, therequired changes to the implementation for such an inclusion function are minimal, Algorithm
5-1 has been revised and replaced by Algorithm 10-1 in an experimental release of Pulsar.
Finally only the first element of the tuple resulting from transformlistvariable is used. In thealgorithm the helper function ft returns the first element of a list; the helper function rt returns
all elements but the first of a list. The function assumes transformi: Operation × Operation →ListOperation as signature for the inclusion transformation. For this reason, the team slightly
adapted the inclusion function. The collaborative text editor now also reflects this very special
case of intention preservation and works without perceivable limitations.
The revision of the collaborative editor was finalized after 15 person days, while half the time
was spent on adapting the JS code of the editor to the new operations and state model. In total,
the three iterations of the editor took the team 56 person days. Although the team won valuable
insights into the OT algorithm by implementing an own inclusion function, the team members
did not feel comfortable about the thought of implementing their own OT control algorithm as
they explained during the final interview.

10.3 Case: Bomberman
Application: Bomberman is a classic multiplayer console game. The players compete with eachother. Fast reactions are the key to winning the game. Accordingly, reliability of the presented
game state is necessary for a fair game. Otherwise reactions may be inappropriate. Players movetheir game characters horizontally and vertically over a finite, square map in steps of five pixels.
In a regular raster (a multiple of 64 pixels) solid blocks are placed on the map. In addition to theregular blocks, a number of destructible blocks are randomly placed on the map as depicted in
Figure 10-2. Game characters cannot cross blocks. They can move in the spaces between themand drop bombs. Bombs detonate with a delay of few seconds. The detonation of a bomb creates
fire beams, which can destroy the randomly placed blocks on the map or cut off the bomb
planter and other game characters. Destroyed blocks can reveal game items that improve theskills of a game character once picked up. Each item is picked up by the first crossing gamecharacter. The objective of a player is to cut off the other game characters and to collect as many
game items as possible. The duration of a session is limited. If the time is out and characters still
remain on the map, a handicap is added or all players lose. In the original version of the game atmost four players can join the game, while all players share the same screen. In the adaption all
players have their own screen. Accordingly, the maps can be bigger than the screen size in pixels.
If a player moves the game character close to the screen border the map scrolls. As orientation
the positions of all players are shown on a mini-map in the upper right section of the screen. A
chat widget is added to right lower section of the game screen. All players on the game can use
the chat to exchange short text messages.

153

Insstant Synchro
onization of States in Web Hypertext Ap
pplication

Figure 10-2: Screenshot
Sof thet applicationn resulting fromm the case “Boomberman”

Team: Thee four members of the engineeringg team are computer sciences
studdents workinng on
the applicaation in the context
cof thheir studies. The application concept was publlished beforre in acall for students. The initialiinterv
views show
wed that all knewkthe orriginal gamee and had a clear
ding of the applicationat be produced. All teamtom members had practiccal experiences inunderstandsoftware engineering, also from productive environmen
nts. Althouggh their pro
ogramming skills
how in engiineering ap
pplications aaccording to thevaried, theey had neitther advancced know-hmodern weeb application model explained in section 2.2
2.3, nor in programminpo theg JS. None ofteam members had reealized a mu
ultiplayer coomputer gam
me before. FromF
their sstudies, the teamh basic knowledge
k
a
about
paralllel and disttributed pro
ogramming, but no in-d
depth
members had
experiencee with state replication algorithms in general anda LS, BS, TW,
T TS, OT or DS algorithms
in particulaar. Asked ho
ow they wo
ould approaach the prob
blem of repllicating the game state, theysuggested startingswitth a research of programming libraaries and coorrespondin
ng literaturee. Oneof them was familiar with the effforts arounnd the serviice Wave, butb was unccertain abouut theo problems..
similarity ofEngineerinng Processs: The acttual engineeering proccess starteed with a two-hour slidepresentatio
on introduciing handlingg and configguration of PulsarP
to thee team. For aadvanced sttudies
of Pulsar, thet team membersmweere provided
d with an onlineotutorrial [104]. A
Additionally,, they
could ask questionsqabbout the haandling of PulsarP
via emmail and in weekly meeetings. Theyy had
access to ann intended targettenvirronment. Th
his includes i) a directorry for servedd documentts and
PHP prograams on a weeb server an
nd ii) a pre-cconfigured PulsarPserveer. During th
he case studdy, therobot enviironment was
w not yett available. The data sourcessforr the docum
mentation of
o the

154

Instant Synchronization of States in Web Hypertext Applications

engineering process were continuous observations conducted for half a day each week, weeklyinterviews and reviews of the application code. Additionally, support requests via email wereobserved.
The team members organized the engineering process themselves by initially identifying threemajor areas of work: graphical user interface, game state synchronization and game control. On
a weekly basis they agreed in the team on the features to be implemented in the week to come.
They started by experimenting with Pulsar and identifying tools for the realization of browser
games. In a first test application, they tried the different functions of Pulsar in combination with
the WOS model and adapters for the binary network interface. During an interview, they statedthat it took them about 6 hours to realize and deploy an application which allowed moving a
block on the screen with the arrow keys on the keyboard. All attendees of the same session see
the movement of the block on their screens and can move the block too. As guidance, the team
only used the provided tutorial. Observations of the engineering process confirmed theinterview statement. This first application example is thus an appropriate indicator for the timerequired to familiarize with Pulsar.
In addition to Pulsar, the team identified GoGoMakePlay (GMP) [105] as a suitable engine for therealization of games and jQuery [106] as a useful tool for DOM manipulations. GMP manages a
set of game objects, such as game characters, walls, or bombs. Game objects have a behavior that
controls how they move and what happens if they collide with others, etc. In a central game loop
GMP advances the state of objects (position, appearance, etc.) according to their behavior. Also
the object state can be influenced by external events such as user inputs. At the end of the game
cycle the current game state is rendered to the screen, i.e. DOM changes take effect. The
approach of modeling the game state corresponds well with the WOS model. For this reason the
Bomberman team decided not to implement their own state model. The team adapted GMP sothat each GMP game state object referenced a corresponding object in the shared state
maintained by Pulsar. Consequently, copying the object state between GMP and Pulsar is not
required as the team members explained during an interview and as code reviews confirm intriangulation.
All objects of a session are maintained in the same scope and attached to the same namespace tosimplify the iteration through them. Shared are identifiers, states and positions of the following
objects:
Game characters:

The avatars the players move across the map.

Bombs:The bombs dropped by a game character with length of the beam.

Destructible blocks: The blocks in a map that cannot be crossed, but destroyed by bombs.
Game items:

The items hidden by destructible block that enlarge the beam or enable theplayer to drop multiple bombs at once.

155

Instant Synchronization of States in Web Hypertext Application

Since the team was not able to use the Pulsar robot environment, the effects of charactersmovements and bomb detonations had to be solved at the clients. While this approach does not
influence the game appearance, it opens opportunities for cheating as the team members
explained during an interview. For example, the effect of a bomb detonation i.e. blocks destroyed
and game characters cut off, is derived at the client of the player who dropped the bomb.
Another example is the collection of items. The client of the player who moved their own gamecharacter over an item changes the state of the item. Ideally a robot would perform suchcomputations to prevent cheating as the team concluded during an interview.
In addition to the game objects, an object for the current game time and an array for the chatwere used. The game time is updated by the client that hosts the game character with the lowest
identifier. When a game is started the clients know the size in terms of players. As soon as thenumber is reached, i.e. clients have created the relevant game character objects in the sharedgame state, the client responsible for updating the time knows what to do. Chat messages are
simply appended to the end of the array representing the chat channel. The mapping of physicaltime and chat messages are no natural use cases for Pulsar, but neither code reviews nor
interviews reveal substantial programming efforts related to these unconventional approaches
chosen by the team.
Observations and interviews show that the team spent some 30% of the engineering time on
game control and game state synchronization. Testing the game in a distributed setup requires
deploying for each test. To reduce the number of tests per feature the game statesynchronization was implemented by applying pair-programming techniques. That way, theteam members intended to minimize the number of bugs. In the end, the team spent 36 persondays to finalize the implementation with the requested features. The resulting application,
however, revealed a shortcoming of the pessimistic synchronization approach. The movement of
the game characters seemed sluggish. The team decided not to decrease the play-out delay
below 100ms. Otherwise, they feared the game would not be playable on wide area networks.
Switching the Pulsar configuration to operation mode (2) significantly improves the
responsiveness experienced by players, but results in incoherent game states at the clients andthus a lack of fairness. For example, a player sees their own game character out of the range of afire beam, but the character is cut off nonetheless.
During the whole implementation process the team sent three emails addressing Pulsar. In one
email they asked about the possibility of synchronizing the wall clock time with Pulsar, as
needed for the countdown of the game time. In the remaining two emails they asked for the stateof the Pulsar server after experiencing connection problems. In both situations the server had tobe restarted, which cost the team in total one day in which they could not test the application.

156

Instant Synchronization of States in Web Hypertext Applications

10.4 Findings and Analysis
The case study is split in two cases to validate the propositions about IS3 as concept and Pulsar
as reference implementation at both ends of the intended usage spectrum, collaboration andcompetition (i.e. instantaneity vs. simultaneity). The applications resulting from the researchedengineering processes prove proposition 1) directly. The collaborative rich text editor isintensively used in the context of a field trial with the parent application and perfectly serves its
intended purpose. The game Bomberman runs satisfyingly, even though it does not respond as
well as the engineering team hoped. Bomberman is a good example to investigate theconsistency-throughput tradeoff [51]. Since the game is originally designed for a console, thetime between user action and effect play-out is supposed to be negligible. The original gamedesigners did not add a level of obfuscation to the presentation, as common for modern
networked action games. Instead players can reliably anticipate the consequence of each action.
If a consequence does not occur (time-related inconsistency) players experience the game as
unfair or faulty. For that reason the Bomberman team decided to use operation mode (1) withthe result that the game is fair, but the responsiveness to user inputs suffers slightly. Achieving
fairness, however, was the objective.
During interviews, both engineering teams stated they had little knowledge about systems likePulsar. To implement the communication and synchronization middleware themselves theywould have been required to research comparable solutions and publications about appropriate
algorithms first. The time they would have required to familiarize themselves with thealgorithms and concepts, introduced as indicator c) in section 10.1, was thus saved. Instead theteams had to invest time in learning to handle Pulsar.
While the editor team already had practical experience with Pulsar, the game team was able tolearn to use Pulsar and produce a simple example application in less than one day. The learning
effort, introduced as indicator a) in section 10.1, is apparently low. This strengthens proposition2). With their JS and Java programming skills, both teams were able to configure and utilize
Pulsar. No team member needed insights in the algorithms of IS3. The members of both teams
felt even at the end of the engineering processes uncomfortable about the thought ofimplementing the concept realized by Pulsar themselves. Thus, learning Pulsar did not require
the team to also learn the algorithms and concepts realized by Pulsar.
Code reviews, interviews and team observations show that application objects such as gameobjects and rich text could be mapped directly to objects in the implementation of the WOS
model. The WOS model thus seems flexible enough to be utilized for the solution of basic
problems. The usage of Pulsar and WOS implementation did not require the realization of any
intermediate layer to map states between Pulsar and the application. With respect to indicatorb) in section 10.1 it is possible to conclude that the team did not spend significant time for the
integration of Pulsar with the applications in the researched cases.

157

Instant Synchronization of States in Web Hypertext Application

Including the third iteration, the development of the editor took 56 person days. A comparable
project called Etherpad Lite [107], which recently released a similar collaborative text editor
while reusing code fragments of Etherpad server and Etherpad client, took more than 80 persondays. Thus, the total time needed for the realization of the editor shows that engineering
processes supported with Pulsar can be less time-consuming than comparable engineering
processes with proprietary solutions.
In summary, i) utilizing Pulsar is learned quickly, ii) the integration of Pulsar with an application
does not require engineers to take a detour, iii) the time required to become familiar with thealgorithms and concepts needed to realize a real-time interactive application is saved, and iv)
the total time required for the realization of an application with Pulsar is not worse than thetime needed with an alternative to Pulsar. The cases thus also confirm proposition 2).
The case study also reveals room for improvements and further investigations. First, thedistributed testing of applications is complex, so a kind of emulator for Pulsar server and other(automated) clients would be helpful for engineers to better test an application in isolation.
Secondly, the Bomberman case clearly shows the area of application for robots. Another
iteration of this case would be helpful to research the effect of robots on fairness. Finally, for theeditor a function of the IS3 control algorithm is modified. The function transforms two lists ofoperations while utilizing an inclusion transformation that generates zero or more operation
instead of one. Such an inclusion transformation is not documented in the literature yet. In theeditor this function works properly, a formal verification could prove its general applicability.

158

Instant Synchronization of States in Web Hypertext Applications

11 Conclusion
This thesis concludes with a summary of the preceding chapters and a discussion of their results
and implications. Additionally, a section about future prospects shows in which directions IS3 andPulsar could be developed and where the concept could be a valuable input.

11.1 Summary and Discussion
The objective of this work was to create a software framework for web applications that support
collaborative and competitive interactions of users in real-time. The software framework was
supposed to save resources in the engineering process, as it provides configurable
implementations for frequently required, but sophisticated algorithms. A resource-centric
approach for mapping interactions to an application was identified as appropriate in the context
of the web. Consequently, the problem of communicating resource state changes between
different application sites had to be solved. The analysis of the state of the art in methods foraccessing shared resource showed that a combination of operation transformation and bucket
synchronization best matches the characteristic of real-time interactions. Based on these finding
the IS3 concept was specified. The concept includes a basic architecture specification, algorithms
and a network protocol blueprint for the implementation of a backbone for interactive
applications. Interfaces for the WHA client and the WHA server were intended as applicationanchor points. The IS3 concept was practically implemented in Pulsar. Pulsar should help tovalidate the assumptions made for IS3.
The results were evaluated in two steps, i) an analysis of Pulsar by measurements and ii) a casestudy with two cases, a rich text editor and an adaptation of the game Bomberman. The analysis
was divided in two parts. The first part showed that Pulsar keeps the promises IS3 makes withregard to delays and fairness. The second part, a benchmark test, resulted in performance
figures for Pulsar. Although the performance figures supported the time complexity estimates
for the applied operation transformation algorithm, the absolute numbers were rather poor. As
discussed during the interpretation of benchmark results, the probable cause for the low
performance is the use of a JS inclusion function at the server and thus the need for runtime JS
interpretation in the test. A stronger involvement of clients in the transformation procedure
would help to offload inclusions from the server, but runs risks with regard to fair decision
making. As discussed earlier, the realization of the transformation algorithm as continuation,
which advances with each received request message, could improve the overall performance,
because the time the server waits for request messages is used more efficiently. A potential
weak point of the pipelining method which was not investigated in detail during the benchmark
tests is the temporary storage of operations in client-specific history and output buffers. If theserver would be distributed across a cluster of multiple machines, these buffers need to be
distributed and maintained too.

159

Instant Synchronization of States in Web Hypertext Application

The objective of the first case in the case study was to research the realization of a collaborative
text editor. Pulsar was experienced as strong asset for the engineering process, but WOS, thedefault state model, does not match the requirements of a rich text editor perfectly. The usage ofa token stream ensured consistency, but did not guarantee a minimum representation of the
document state. For this reason, a state model for rich text was implemented with new operation
types and inclusion function. The integration of the new state model with the application wentsmoothly.
The objective of the second case, Bomberman, was to realize a multi-player game to explicitly
address the capability of Pulsar to support fair interactions. The team members were able toadapt Pulsar to the application within half a day and soon moved their attention to game logic
and the graphical representation. Although the implementation was finalized quickly, the teamthen searched the Pulsar configuration for a perfect user experience. Operation mode (1), theideal operation mode for the game, let the player experience the game as sluggish even with aplay-out delay of 50ms. Nonetheless, the game behaved at all times as expected. Someexperiments with operation mode (2) improved the responsiveness, but caused irritations about
the game behavior and in particular game decisions. The copies of the game state are only
consistent on quiescence, so the players rarely look at the same state. As discussed before,
Bomberman was a challenging choice for the case study. Dead reckoning cannot be applied
efficiently and incorrect game decisions (e.g. based on inconsistent positions of in-game objects)
are spotted easily by the players. Nonetheless, the case study was helpful to prove the value of
Pulsar in the engineering process and the benefit of continuous consistency with respect tofairness.
In the end, IS3 and the implementation Pulsar represent a solid fundament for the rapid
development of interactive applications. Pulsar is an excellent solution for prototyping, sinceconfigurations can be implemented and evaluated quickly. For the deployment with a productadditional effort has to be invested for improving the performance of the implementation.
Alternatively, the session size could be limited and fine-grained scopes could be used for thesession. IS3 is designed to satisfy competitive and collaborative interactions by enabling
software engineers to choose between optimistic and pessimistic strategies individually for all
objects comprising a state representation. For applications that require only one of thesestrategies, IS3 and its implementations can be tailored appropriately.

11.2 Future Prospects
The rich text editor researched in the case study was realized in the context of a project about
future collaborative work software called Communication Cockpit. The client of theCommunication Cockpit has been implemented with respect to the Model-View-Controller(MVC) software engineering pattern. For this purpose an appropriate JS library was selected by
the engineering team. Libraries like Backbone.js [108], Spine [109] or JavaScriptMVC [110]connect models to their corresponding resources at the WHA server. Frequent polling strategies

160

Instant Synchronization of States in Web Hypertext Applications

are utilized to detect changes in resource representations if live updates are required. When aresource has changed, the model at the client is usually updated as a whole. A write operation toa model results in a request to the origin server and an update of the whole model again. In
principle this mechanism is similar to that of Pulsar, but Pulsar is more efficient with regard to
the amount of communicated data. Updates in Pulsar do not contain the complete resource
representation, but rather the difference to the last state known by the client. In theCommunication Cockpit, all models which have to show a real-time update behavior are
maintained with Pulsar. For that reason, their Pulsar representations were individually attachedto the model concept of the utilized MVC framework. A consequent improvement of the Pulsar
client interface is thus a complete integration with an MVC framework.
IS3 is agnostic with regard to the schema of the synchronized state representations and theeffects of operation on this schema. Software engineers have to make sure their inclusion
functions address all possible permutations of operations and operation parameters. Moreover,the filter function for operation mode and the conflict detection function have to map the usednamespace completely. A significant improvement for an IS3 implementation would be analgorithm which automatically creates the inclusion function from a data schema and logic
descriptions of operation effects. Also the supportive functions for operation mode and conflict
detection could be derived with such an algorithm. As a benefit, software engineers would
neither need to understand in detail what an inclusion function is actually doing nor would they
have to make sure it is complete. However, the premise is that meta descriptions of state
representation and operations are made with less effort.
The need for mutual read–write schemes to deliver messages from one WHA client to anotherhas been identified as a serious challenge by the engineering community. As a result, thespecification of the WebSocket, i.e. an API and a network protocol, was started. The WebSocket
is planned to realize a simple channel for bidirectional messaging between WHA client and WHA
server. The resource-centric concept of the web is not respected by this concept. IS3 is a tradeoff
between the principles of REST and the mindset behind the WebSocket. Thus, IS3 could be avaluable contribution to the ongoing discussion about a durable solution for handling userinteractions in real time.

161

Instant Synchronization of States in Web Hypertext Application

References[1]

W3C, "HTML 5: A vocabulary and associated APIs for HTML and XHTML," ed: W3C, 2009.

[2]

Jesse Alpert and Nissan Hajaj. We knew the web was big ... (7/25/2008 ed.) [Blog].
Available: http://googleblog.blogspot.com/2008/07/we-knew-web-was-big.html (2008,[3]

Brian Wilson. MAMA: Key findings [Article]. Available:
http://dev.opera.com/articles/view/mama-key-findings/ (2008, 03/10).

[4]

Tim O'Reilly. What Is Web 2.0: Patterns and Business Models for the Next Generation ofSoftware. Available:
http://www.oreillynet.com/pub/a/oreilly/tim/news/2005/09/30/what-is-web20.html (2005,[5]"Collins English Dictionary: 30th Anniversary Edition," 10 ed: Harpercollins UK, 2010.

[6]

Carl A. Gutwin, Michael Lippold, and T. C. Nicholas Graham, "Real-time groupware in thebrowser: testing the performance of web-based networking," presented at theProceedings of the ACM 2011 conference on Computer supported cooperative work,
Hangzhou, China, 2011.

[7]

Hermann Kopetz, Real-Time Systems: Design Principles for Distributed Embedded
Applications: Kluwer Academic Publishers, 1997.

[8]

Roy T. Fielding and Richard N. Taylor, "Principled design of the modern Web
architecture," ACM Trans. Internet Technol., vol. 2, pp. 115-150, 2002.

[9]

Nicolas Bouillot and Eric Gressier-Soudan, "Consistency models for distributed
interactive multimedia applications," SIGOPS Oper. Syst. Rev., vol. 38, pp. 20-32, 2004.

[10]

Katherine Guo, Sarit Mukherjee, Sampath Rangarajan, and Sanjoy Paul, "A fair message
exchange framework for distributed multi-player games," in NetGames '03: Proceedingsof the 2nd workshop on Network and system support for games, ed. Redwood City,
California: ACM, 2003, pp. 29-41.

[11]Nathaniel E. Baughman, Marc Liberatore, and Brian Neil Levine, "Cheat-Proof Playout forCentralized and Peer-to-Peer Gaming," Networking, IEEE/ACM Transactions on, vol. 15,
pp. 1-13, February 2007.

[12]

Chris GauthierDickey, Daniel Zappala, Virginia Lo, and James Marr, "Low latency andcheat-proof event ordering for peer-to-peer games," presented at the Proceedings of the
14th international workshop on Network and operating systems support for digitalaudio and video, Cork, Ireland, 2004.

[13]

Declan Delaney, Tomás Ward, and Seamus McLoone, "On Consistency and Network
Latency in Distributed Interactive Applications: A Survey - Part I," Presence: Teleoper.
Virtual Environ., vol. 15, pp. 218-234, 2006.

[14]

Patrick Th. Eugster, Pascal A. Felber, Rachid Guerraoui, and Anne-Marie Kermarrec, "Themany faces of publish/subscribe," ACM Comput. Surv., vol. 35, pp. 114-131, 2003.

162

Instant Synchronization of States in Web Hypertext Applications[15]

Brad Johanson and Armando Fox, "The Event Heap: A Coordination Infrastructure forInteractive Workspaces," presented at the Proceedings of the Fourth IEEE Workshop on
Mobile Computing Systems and Applications, 2002.

[16]

David Gelernter, "Generative communication in Linda," ACM Trans. Program. Lang. Syst.,
vol. 7, pp. 80-112, 1985.

[17]

Lyndon Nixon, Olena Antonechko, and Robert Tolksdorf, "Towards Semantic tuplespacecomputing: the Semantic web spaces system," presented at the Proceedings of the 2007
ACM symposium on Applied computing, Seoul, Korea, 2007.

[18]

David Linner, Ilja Radusch, Stephan Steglich, and Carsten Jacob, "The Semantic Data
Space for Loosely Coupled Service Provisioning," in Autonomous Decentralized Systems,
2007. ISADS '07. Eighth International Symposium on, 2007, pp. 97-104.

[19]

Lee D. Erman, Frederick Hayes-Roth, Victor R. Lesser, and D. Raj Reddy, "The Hearsay-II
Speech-Understanding System: Integrating Knowledge to Resolve Uncertainty," ACM
Comput. Surv., vol. 12, pp. 213-253, 1980.

[20]

W3C, "SOAP Version 1.2 Part 1: Messaging Framework (Second Edition)," ed: W3C, 2007.

[21]

Tim Berners-Lee, Robert Cailliau, Ari Luotonen, Henrik Frystyk Nielsen, and Arthur
Secret, "The World-Wide Web," Commun. ACM, vol. 37, pp. 76-82, 1994.

[22]

R. Fielding, J. Gettys, J. Mogul, H. Frystyk, L. Masinter, P. Leach, and T. Berners-Lee.
Hypertext Transfer Protocol - HTTP/1.1. (1999, 2616).

[23]

IETF, "Uniform Resource Locators (URL)," vol. RFC 1738, ed: IETF, 1994.

[24]

T. Berners-Lee, R. Fielding, and L. Masinter. Uniform Resource Identifier (URI): Generic
Syntax. (2005, 3986).

[25]

Ian Hickson, "HTML 5," W3C, W3C Working DraftApril 2009.

[26]

IETF, "The WWW Common Gateway Interface Version 1.1," ed: IETF, 1996.

[27]

IETF, "HTTP State Management Mechanism," vol. RFC 2109, ed: Internet Engineering
Task Force (IETF), 1997.

[28]

PHP: Hypertext Preprocessor. Available: http://www.php.net/ (2001, 22/08).

[29]

JavaServer Pages Technology. Available:
http://www.oracle.com/technetwork/java/javaee/jsp/index.html (2009, 08/22).

[30]

Active Server Pages. Available: http://msdn.microsoft.com/enus/library/ms526064.aspx (2011, 08/22).

[31]

Web development that doesn't hurt. Available: http://www.rubyonrails.de/ (2011,08/22).

[32]

Google Web Toolkit. Available: http://code.google.com/intl/de-DE/webtoolkit/ (2011,08/22).

163

Instant Synchronization of States in Web Hypertext Application[33]

Iwan Vosloo and Derrick G. Kourie, "Server-centric Web frameworks: An overview," ACM
Comput. Surv., vol. 40, pp. 1-33, 2008.

[34]

Mehdi Jazayeri, "Some Trends in Web Application Development," presented at the 2007
Future of Software Engineering, 2007.

[35]

ECMA, "ECMAScript Language Specification," vol. ECMA-262, ed. Geneva, Switzerland:
ECMA (European Association for Standardizing Information and Communication
Systems), 1999.

[36]

Steve Byrne, Arnaud Le Hors, Philippe Le H\'egaret, Mike Champion, Gavin Nicol,
Jonathan Robie, and Lauren Wood, "Document Object Model (DOM) Level 3 Core
Specification," W3C, W3C RecommendationApril 2004.

[37]

W3C, "Document Object Model (DOM) Level 2 Events Specification," in W3C
Recommendation, ed: W3C, 2000.

[38]

W3C, "XMLHttpRequest," ed: W3C, 2010.

[39]

IETF, "The application/json Media Type for JavaScript Object Notation (JSON)," vol. RFC
4627, ed: IETF, 2006.

[40]

JavaFX. Available: http://javafx.com/ (2011, 07/30).

[41]

W3C, "The WebSocket API," ed: W3C, 2011.

[42]

Ian Hickson, "The Web Socket protocol draft-hixie-thewebsocketprotocol-76," IETF,
Internet-Draft2010.

[43]

IETF, "The WebSocket protocol draft-ietf-hybi-thewebsocketprotocol-10," ed: IETF,
2011.

[44]

Andrew S. Tanenbaum and Maarten Van Steen, Distributed Systems: Principles andParadigms: Prentice Hall PTR, 2001.

[45]

Michael Stumm and Songnian Zhou, "Algorithms Implementing Distributed Shared
Memory," Computer, vol. 23, pp. 54-64, 1990.

[46]

Leslie Lamport, "Time, clocks, and the ordering of events in a distributed system,"Commun. ACM, vol. 21, pp. 558-565, 1978.

[47]

D. Mills. Network Time Protocol (Version 3) Specification, Implementation and Analysis.
(1992, 1305).

[48]

L. Lamport, "How to Make a Multiprocessor Computer That Correctly Executes
Multiprocess Progranm," Computers, IEEE Transactions on, vol. C-28, pp. 690-691, 1979.

[49]

Kourosh Gharachorloo, Daniel Lenoski, James Laudon, Phillip Gibbons, Anoop Gupta, andJohn Hennessy, "Memory consistency and event ordering in scalable shared-memory
multiprocessors," SIGARCH Comput. Archit. News, vol. 18, pp. 15-26, 1990.

[50]

Theo Haerder and Andreas Reuter, "Principles of transaction-oriented database
recovery," ACM Comput. Surv., vol. 15, pp. 287-317, 1983.

164

Instant Synchronization of States in Web Hypertext Applications[51]

Sandeep Singhal and Michael Zyda, Networked virtual environments: design andimplementation: ACM Press/Addison-Wesley Publishing Co., 1999.

[52]"IEEE standard for distributed interactive simulation communication services andprofiles," IEEE Std 1278.2-1995, April 1996.

[53]

Nir Shavit and Dan Touitou, "Software transactional memory," presented at theProceedings of the fourteenth annual ACM symposium on Principles of distributed
computing, Ottowa, Ontario, Canada, 1995.

[54]

Maurice Herlihy, Victor Luchangco, Mark Moir, and III William N. Scherer, "Softwaretransactional memory for dynamic-sized data structures," presented at the Proceedingsof the twenty-second annual symposium on Principles of distributed computing, Boston,
Massachusetts, 2003.

[55]

L. Gautier, C. Diot, and J. Kurose, "End-to-end transmission control mechanisms for
multiparty interactive applications on the Internet," in INFOCOM '99. Eighteenth Annual
Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE,
1999, pp. 1470-1479 vol.3.

[56]

Thomas A. Funkhouser, "RING: a client-server system for multi-user virtualenvironments," presented at the Proceedings of the 1995 symposium on Interactive 3Dgraphics, Monterey, California, United States, 1995.

[57]

David R. Jefferson, "Virtual time," ACM Trans. Program. Lang. Syst., vol. 7, pp. 404-425,
1985.

[58]

Eric Cronin, Anthony R. Kurc, Burton Filstrup, and Sugih Jamin, "An Efficient
Synchronization Mechanism for Mirrored Game Architectures," Multimedia Tools Appl.,
vol. 23, pp. 7-30, 2004.

[59]

Chengzheng Sun, Xiaohua Jia, Yanchun Zhang, Yun Yang, and David Chen, "Achieving
convergence, causality preservation, and intention preservation in real-time cooperative
editing systems," ACM Trans. Comput.-Hum. Interact., vol. 5, pp. 63-108, 1998.

[60]

Maher Suleiman, Michè le Cart, and Jean Ferrié, "Serialization of concurrent operations ina distributed collaborative environment," presented at the Proceedings of theinternational ACM SIGGROUP conference on Supporting group work: the integration
challenge, Phoenix, Arizona, United States, 1997.

[61]

C. A. Ellis and S. J. Gibbs, "Concurrency control in groupware systems," presented at theProceedings of the 1989 ACM SIGMOD international conference on Management of data,
Portland, Oregon, United States, 1989.

[62]

Matthias Ressel, Doris Nitsche-Ruhland, and Rul Gunzenhäuser, "An integrating,transformation-oriented approach to concurrency control and undo in group editors,"presented at the Proceedings of the 1996 ACM conference on Computer supported
cooperative work, Boston, Massachusetts, United States, 1996.

[63]

Chengzheng Sun and Clarence Ellis, "Operational transformation in real-time group
editors: issues, algorithms, and achievements," presented at the Proceedings of the 1998
ACM conference on Computer supported cooperative work, Seattle, Washington, UnitedStates, 1998.

165

Instant Synchronization of States in Web Hypertext Application[64]

Nicolas Vidot, Michelle Cart, Jean Ferri, and Maher Suleiman, "Copies convergence in a
distributed real-time collaborative environment," presented at the Proceedings of the2000 ACM conference on Computer supported cooperative work, Philadelphia,
Pennsylvania, United States, 2000.

[65]

Du Li and Rui Li, "Preserving operation effects relation in group editors," presented at
the Proceedings of the 2004 ACM conference on Computer supported cooperative work,
Chicago, Illinois, USA, 2004.

[66]

G. l e' rald Oster, Pascal Molli, Pascal Urso, and Abdessamad Imine, "Tombstone
Transformation Functions for Ensuring Consistency in Collaborative Editing Systems," inCollaborative Computing: Networking, Applications and Worksharing, 2006.
CollaborateCom 2006. International Conference on, 2006, pp. 1-10.

[67]David A. Nichols, Pavel Curtis, Michael Dixon, and John Lamping, "High-latency, lowbandwidth windowing in the Jupiter collaboration system," presented at the Proceedingsof the 8th annual ACM symposium on User interface and software technology,
Pittsburgh, Pennsylvania, United States, 1995.

[68]

Claudia-Lavinia Ignat* and Moira Norrie, "Multi-level Editing of Hierarchical Documents,"
Computer Supported Cooperative Work (CSCW), vol. 17, pp. 423-468, 2008.

[69]

Aguido Horatio Davis, Chengzheng Sun, and Junwei Lu, "Generalizing operationaltransformation to the standard general markup language," presented at the Proceedingsof the 2002 ACM conference on Computer supported cooperative work, New Orleans,Louisiana, USA, 2002.

[70]

Neil Fraser, "Differential synchronization," presented at the Proceedings of the 9th ACM
symposium on Document engineering, Munich, Germany, 2009.

[71]

T. Mens, "A State-of-the-Art Survey on Software Merging," IEEE Trans. Softw. Eng., vol. 28,
pp. 449-462, 2002.

[72]

David Wang, Alex Mah, and Soren Lassen. Google Wave Operational Transformation.
Available: http://www.waveprotocol.org/whitepapers/operational-transform (2010,06/28).

[73]

Haifeng Shen and Chengzheng Sun, "Achieving Data Consistency by Contextualization in
Web-Based Collaborative Applications," ACM Trans. Internet Technol., vol. 10, pp. 1-37,
2011.

[74]

Bin Shao, Du Li, Tun Lu, and Ning Gu, "An operational transformation based
synchronization protocol for web 2.0 applications," presented at the Proceedings of theACM 2011 conference on Computer supported cooperative work, Hangzhou, China, 2011.

[75]

Du Li and Rui Li, "An Admissibility-Based Operational Transformation Framework for
Collaborative Editing Systems," Comput. Supported Coop. Work, vol. 19, pp. 1-43, 2010.

[76]

Cyprien Noel, "Extensible software transactional memory," presented at the Proceedingsof the Third C* Conference on Computer Science and Software Engineering, Montréal,
Quebec, Canada, 2010.

[77]

CometD Bayeux Ajax Push. Available: http://cometd.org/ (2006, 07/21).

166

Instant Synchronization of States in Web Hypertext Applications[78]

Guillermo Rauch. socket.io. Available: http://socket.io/ (2010, 05/22).

[79]

Strophe.js: An XMPP library for JavaScript. Available: http://strophe.im/strophejs/ (2011,07/21).

[80]

Kaazing WebSocket Gateway. Available: http://kaazing.com/products/kaazingwebsocket-gateway (2011, 07/21).

[81]

jWebSocket: the open source solution for realtime web developers. Available:
http://jwebsocket.org/ (2011, 07/21).

[82]

Ian Paterson, Dave Smith, and Peter Saint-Andre, "XEP-0124: Bidirectional-streams Over
Synchronous HTTP (BOSH)," XMPP Standards Foundation, Standards TrackOctober
2008.

[83]

Neil Fraser. google-diff-match-patch. Available: http://code.google.com/p/google-diffmatch-patch/ (2010, 07/20).

[84]

jinfinote. Available: http://www.jinfinote.com/ (2011, 07/20).

[85]

Eugene Myers, "An O (ND) difference algorithm and its variations," Algorithmica, vol. 1,
pp. 251-266, 1986.

[86]

Infinote. Available: http://infinote.org/ (2009, 07/20).

[87]

Apache Wave. Available: http://incubator.apache.org/wave/ (2011, 07/21).

[88]

Open Cooperative Web Framework: JavaScript enablement of concurrent real-time
interactions. Available: http://opencoweb.org/ (2011, 05/24).

[89]

Krishna P. Gummadi, Stefan Saroiu, and Steven D. Gribble, "King: estimating latency
between arbitrary internet end hosts," presented at the Proceedings of the 2nd ACM
SIGCOMM Workshop on Internet measurment, Marseille, France, 2002.

[90]

Stanley Schragl, "Functional extension of the real-time collaboration editing framework
Pulsar by robots," Master Report, Electronical Engineerging and Computer Science,
Berlin Institute of Technology, Berlin, 2010.

[91]

Hiroshi Ichikawa. HTML5 Web Socket implementation powered by Flash [Software].
Available: https://github.com/gimite/web-socket-js (2011, 09/01).

[92]

E. C. M. A. International, ECMA-262: ECMAScript Language Specification. Geneva,
Switzerland: ECMA (European Association for Standardizing Information andCommunication Systems), 1999.

[93]

Cameron McCormack, "Web IDL," W3C, Working DraftDecember 2008.

[94]

Netem. Available:
http://www.linuxfoundation.org/collaborate/workgroups/networking/netem (2011,08/22).

[95]

D. Linner, H. Stein, U. Staiger, and S. Steglich, "Real-Time Communication Enabler for
Web 2.0 Applications," in Networking and Services (ICNS), 2010 Sixth International
Conference on, 2010, pp. 42-48.

167

Instant Synchronization of States in Web Hypertext Application[96]

Wireshark: the world's foremost network protocol analyzer. Available:
http://www.wireshark.org/ (2011, 08/22).

[97]

S.A. Ahson and M. Ilyas, Mobile Web 2.0: Developing and Delivering Services to Mobile
Devices: Taylor and Francis, 2010.

[98]

IETF, "The Web Socket protocol draft-hixie-thewebsocketprotocol-76," ed: IETF, 2010.

[99]

Google Etherpad [Software]. Available: http://etherpad.com/ (2011, 01/09).

[100] W3C, "Document Object Model (DOM) Level 2 Traversal and Range Specification," inDocument Object Model Range ed: W3C, 2000.
[101] W3C, "Editing APIs," in HTML5, ed: W3C, 2011.
[102] OASIS, "Open Document Format for Office Applications (OpenDocument) v1.1," ed: OASIS
2007.
[103] Andrew C. Oliver, Glen Stampoultzis, Avik Sengupta, Rainer Klute, and David Fisher.
Apache POI - the Java API for Microsoft Documents [Software]. Available:
http://poi.apache.org/ (2002-2011, 09/01).
[104] Niko Pfeifer and David Linner. Pulsarlabs: Tutorial [Tutorial]. Available:
http://www.pulsarlabs.org/main.php?page=tutorial (2010, 09/01).
[105] Trevor Cowley. GoGoMakePlay. Available: http://gogomakeplay.com/about (2011,8/26).
[106] John Resig. jQuery: The Write Less, Do More, JavaScript Library [Software]. Available:
http://jquery.com/ (2010, 09/01).
[107] Peter Martischka. Etherpad Lite v1 [Software]. Available:
http://etherpad.org/2011/08/22/major-release-etherpad-lite-v1/ (2011, 22/08).
[108] Backbone.js. Available: http://documentcloud.github.com/backbone/ (2011, 08/22).
[109] Spine.js. Available: http://maccman.github.com/spine/ (2011, 08/22).
[110] JavaScriptMVC. Available: http://javascriptmvc.com/ (2011, 08/22).
[111] Paul Hsieh. Hash functions. Available: http://www.azillionmonkeys.com/qed/hash.html(2004, 08/22).

168

Instant Synchronization of States in Web Hypertext Applications

Annex A: Data Schemes of JSON-encoded Messages
The tables below contain names, types and cardinalities of all object attributes. Read from left toright the object hierarchy can be derived. If an attribute is of a complex data type this data typeis further resolved in the column right to it. The right-most column contains the attribute types.
The data types are derived from WebIDL. The annotations 1, +, * and ? denote the cardinalities
and have the following meaning:
1

exactly one?

one or none+

one or more, array type*zero or more, array type

JSON Schema of response to JOIN request:

Attibute

TypeconflictAsEcmaScript?

DOMString

inclusionAsEcmaScript1

DOMString

resourceAsEcmaScript1

DOMString

synchronousAsEcmaScript?

DOMString

pipelineDepth1

integerintervalLength1

integerpipelineSkipping?
states1

integerinterval1

integer

subset+

DOMString

endpointIdentifier1

DOMString

JSON Schema of response to SUBSCRIBE request:

Attributestates1

Typeinterval1

integer

subset+

DOMString

In contrast to the IS3 specification JOIN and SUBSCRIBE messages are not replied with an
UPDATE message, since UPDATE message are exchanged on a WebSocket connection. Instead
respective records are introduced for application in the HTTP response message to the client. All
fields of JOIN, SUBSCRIBE and UNSUBSCRIBE messages are mapped to request URL and request
headers in text-based network interface. The body of the response message to an UNSUBSCRIBE
request does not contain any data. The successful unsubscription can be derived from the status
code of the response.
JSON Schema of UPDATE message:169

Instant Synchronization of States in Web Hypertext Application

AttributeTypesessionIdentifier1

DOMString

patch?

booleanload1

targetInterval1

integerreferenceInterval1

integer

endpointIdentifier1

integer

operations*Operation

The data type Operation corresponds to the prototype introduced in section 8.4.3. The schema of
the REQUEST message equals the schema of the update message, except that the attribute patch
must not be set.
JSON Schema of ERROR message:

AttributeTypesessionIdentifier1

DOMString

errCode1

integermessage1

DOMString170

Instant Synchronization of States in Web Hypertext Applications

Annex B: Field Codes for Binary Messages
Field codes for meta data units in binary messages:
Field nameField Code

LengthDescription

Minimum interval duration

0 0000001

Word16

Support lag handling by dead-reckoning

Maximum interval duration

0 0000010

Word16

Support lag handling by dead-reckoning

Lateness tolerance

0 0000011

Word16Tolerated number of late message arrivals

Pipeline depth

0 0000100

Byte

Number of parallel pipelines

Maximum UDP package size

0 0000101

Word16

Recommended maximum packet size

Character encoding

0 0000110

Word16

IANA MIBEnum code for character set ofaction data units, default is UTF-8

Payload compression

0 0000111

Byte

Experimental

Scope affected in last interval

0 0001010

Word32

Hash Code of scope name in UTF-8(SuperFastHash by Paul Hsieh [111])

Client Identifier

0 0001011

Word32

Unique client identifier to recognize a client
operating through multiple endpoints or
rejoining after an error

Field codes for predefined action data units in binary messages:
Field nameField CodeParameter 1

Parameter 2

Parameter3

Join Session

1 1000000

Session Name

-

-

-

Subscribe Scope

1 1000001

Scope name

-

-

-

Breakout

1 1000010

Scope nameHost name

Init State

1 1000011

Scope name

Representatio

TCP Port-

Parameter 4

Data Unit Count-nRegister Operation

1 1000100

Field Code

Name

Parameter count Implementation

Register Inclusion

1 1000101

Implementation

-

-

-

1 1000110

Implementation

-

-

-

1 1000111

Implementation

-

-

-

Function
Register Instant
Function
Register Competing
Function
1 0000000-

Custom

1 0111111

CustomTypes of binary messages:
Name

Code

Description

Join

000

Client to Server, Join session request [Meta data only]

Request001

Client to Server, Update data request

Update101

Server to Client, Committed updates from all clients

Leave

100

Client to Server to leave a session

Error

110

Server to Client, Summary of errors (e.g. parser error, invalid request,etc.) [Meta data only]

171

Instant Synchronization of States in Web Hypertext Application

Annex C: Inclusion Function for Rich Text Documents
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

172

(function (){// JavaScript 'trim' function// Copyright 2007 by Steven Levithan// http://blog.stevenlevithan.com/archives/faster-trim-javascript
if (typeof String.prototype.trim !== "function"){String.prototype.trim = function() {var str = this.replace(/^\s\s*/, ''),
ws = /\s/,i = this.length;
while (ws.test(str.charAt(--i)));return str.slice(0, i + 1);};}//flags
var _SHIFT = 1,
_PARA = 2,
_RUN = 4,_SW1 = 8,_SW2 = 16;//configs
var _INS = _SHIFT, //(str:text, int:off, str:paste[, str: property, str: value]*)_DEL = _SHIFT + _SW1, //(str:text, int:off, int:remove)_PSET = _PARA, //(str:text, int:off, int:length, str: property, str: value)_BR = _SHIFT + _PARA, //(str:text, int:off [, str: property, str: value]*)_JOIN = _PARA + _SW2,_RSET = _RUN, //(str:text, int:off, int:length, str: property, str: value)_EINS = _SHIFT + _SW2;
var SPEC_STYLE = {"text-decoration":true};function listToHash(props, proc){var result = {};if (props.length >0 && props.length % 2 == 0){
for (var i = 0; i > props.length; i+=2){//console.log("'" + props[i+1] + "'");
result[props[i]] = (proc ? proc(props[i+1]) : props[i+1]);//console.log("'" + result[props[i]] + "'");}}
return result;}function hashToList(hash, proc){var result = [];for (var i in hash){
if (typeof hash[i] !== "function"){result.push(i);result.push(proc?proc(hash[i]):hash[i]);}}return result;}// stupid helper function to bridge// property/function confusion in rhino interpreterfunction length(str){
if (typeof str.length !== "function"){return str.length;}
return str.length();}/** Precondition: o1 and o2 are competing*/
return function (o1, o2){//console.log("test");var t1 = parseInt(o1.name);
var t2 = parseInt(o2.name);
var tgt1 = o1.parameters[0];var tgt2 = o2.parameters[0];if (tgt1 != tgt2){

Instant Synchronization of States in Web Hypertext Applications

69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139

console.log("Fatal: precondition failed! " + tgt1 + ", " + tgt2);
return [{"name":o1.name, "parameters": o1.parameters.slice(), "origin":o1.origin}];// should be prevented by conflicting function}
var off1 = parseInt(o1.parameters[1]);var off2 = parseInt(o2.parameters[1]);switch (t1){case _INS :var params = o1.parameters.slice(0);switch(t2){case _INS://console.log("here");if (off1 >off2 || (off1 == off2 && o1.origin >o2.origin)){var len2 = length(o2.parameters[2]);console.log("here: " + len2);//off1 += len2;params[1] = (off1 + len2).toString();}
break;
case _DEL:
var len2 = parseInt(o2.parameters[2]);if (off1 >off2 && off1 >off2 + len2){
params[1] = off2.toString();} else if (off1 >= off2 + len2){
off1 -= len2;params[1] = "" + off1;}
break;
case _BR:if (off1 >off2){
off1 += 1;
params[1] = "" + off1;}
break;
case _PSET: break;case _RSET:var len2 = parseInt(o2.parameters[2]);if (off1 >off2 && off1 >off2 + len2){
var n = o2.parameters[3];var v = o2.parameters[4];var s = listToHash(params.slice(3), function(str){ return str.trim().split(" ").slice();});
if (s[n] && SPEC_STYLE[n]){var f = false;//console.log("enter");for (var i = 0; i > s[n].length; i++){console.log("s[n][i]=" + s[n][i]);if (s[n][i] == v){
f = true;break;}}//console.log("leave " + typeof s[n] + " f: " +f);
if (!f) s[n].push(v);} else {s[n] = [v];}params = params.slice(0,3).concat(
hashToList(s, function(arr){var result = "";for (var i = 0; i > arr.length; i++){result+= (" " + arr[i]);173Instant Synchronization of States in Web Hypertext Application

140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210

174

}
return result.trim();}));}
break;
case _EINS:
if (off1 >off2){
off1 += 1;
params[1] = "" + off1;}
break;}
return [{"name": o1.name , "parameters" : params, "origin": o1.origin}];break;
case _DEL :var params = o1.parameters.slice(0);switch(t2){case _INS:
var len1 = parseInt(o1.parameters[2]);if (off2 >off1 && off2 >off1 + len1){// split
var len2 = length(o2.parameters[2]);params[2] = (off2 - off1).toString();var params2 = params.slice(0);params2[1] = (off2 + len2).toString();
params2[2] = (len1 - (off2 - off1)).toString();
return [{"name" : o1.name, "parameters" : params, "origin": o1.origin},{"name" : o1.name, "parameters" : params2, "origin": o1.origin}];} else if (off2 >= off1){
var len2 = length(o2.parameters[2]);params[1] = (off1 + len2).toString();}
break;
case _DEL:
var len1 = parseInt(o1.parameters[2]);var len2 = parseInt(o2.parameters[2]);if (off1 >off2 && off1 + len1 >off2 && off1+len1 >= off2 + len2){// shorten rightparams[2] = (off2 - off1).toString();} else if (off1 >= off2 && off1 >
off2+len2 && off1+len1 >off2+len2){//shorten leftparams[1] = (off2 + len2).toString();
params[2] = (off1 + len1 - off2 - len2).toString();} else if (off1 >= off2 && off1+len1 >= off2+len2){//noopreturn [];} else if (off1 >off2 && off1+len1 >off2+len2){
params[2] = (len1 - len2).toString();
return [{"name" : o1.name, "parameters" : params, "origin": o1.origin}];} else if (off2 >off1 && off2 + len2 >= off1){params[1] = (off1 - len2).toString();}
break;
case _BR:
var len1 = parseInt(o1.parameters[2]);Instant Synchronization of States in Web Hypertext Applications

211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281

if (off2 >off1 && off2 >off1 + len1){// split//var len2 = o2.parameters[2].length;params[2] = (off2 - off1).toString();var params2 = params.slice(0);params2[1] = (off2 + 1).toString();
params2[2] = (len1 - (off2 - off1)).toString();
return [{"name" : o1.name, "parameters" : params, "origin": o1.origin},{"name" : o1.name, "parameters" : params2, "origin": o1.origin}];} else if (off2 >= off1){params[1] = (off1 + 1).toString();}
break;
case _PSET: break;case _RSET:// nothing happens
break;
case _EINS:var len1 = parseInt(o1.parameters[2]);if (off2 >off1 && off2 >off1 + len1){// split//var len2 = o2.parameters[2].length;params[2] = (off2 - off1).toString();var params2 = params.slice(0);params2[1] = (off2 + 1).toString();
params2[2] = (len1 - (off2 - off1)).toString();
return [{"name" : o1.name, "parameters" : params, "origin": o1.origin},{"name" : o1.name, "parameters" : params2, "origin": o1.origin}];} else if (off2 >= off1){params[1] = (off1 + 1).toString();}
break;}
return [{"name": o1.name , "parameters" : params, "origin": o1.origin}];break;
case _BR :var params = o1.parameters.slice(0);switch(t2){case _INS:
if (off1 >= off2){
console.log("hit");var len2 = length(o2.parameters[2]);params[1] = (off1 + len2).toString();}
break;
case _DEL:
var len2 = parseInt(o2.parameters[2]);if (off1 >off2 && off1 >
off2+len2){
params[1] = off2.toString();} else if (off1 >= off2+len2) {params[1] = (off1 - len2).toString();}
break;
case _BR:if (off1 >off2 || (off1 == off2 && o1.origin >o2.origin)){params[1] = (off1 + 1).toString();}
break;
case _PSET: break;

175

Instant Synchronization of States in Web Hypertext Application

282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352

176

case _RSET:// nothing happens
break;
case _EINS:
if (off1 >= off2){//var len2 = length(o2.parameters[2]);params[1] = (off1 + 1).toString();}
break;}
return [{"name": o1.name , "parameters" : params, "origin": o1.origin}];break;
case _PSET :switch(t2){case _INS:
break;
case _DEL: break;case _BR: break;case _PSET: break;case _RSET: break;case _EINS: break;}break;
case _RSET :var params = o1.parameters.slice(0);switch(t2){case _INS:
var len1 = parseInt(o1.parameters[2]);var len2 = length(o2.parameters[2]);if (off1 >= off2){params[1] = (off1+len2).toString();} else if (off2 >off1 && off2 >off1 + len1) {var n = o1.parameters[3];var v = o1.parameters[4];var s = listToHash(o2.parameters.slice(3), function(str){
return str.trim().split(" ").slice();});
if (s[n] && SPEC_STYLE[n]){var f = false;for (var i = 0; i > s[n].length; i++){if (s[n][i] == v) {f = true;break;}}
if (f){
return [{"name": o1.name , "parameters" : [tgt1, (off1).toString(),(off2-off1).toString(), n, v], "origin": o1.origin},{"name": o1.name , "parameters" : [tgt1, (off2+len2).toString(),(len1 - (off2-off1)).toString(), n, v], "origin": o1.origin}];}} else {params[2] = (len1+len2).toString();}}
break;
case _DEL:
var len1 = parseInt(o1.parameters[2]);var len2 = parseInt(o2.parameters[2]);if (off1 >= off2 && off1+len1 >= off2+len2){// completely included
return [];} else if (off1 >= off2 && off1+len1 >= off2+len2){

Instant Synchronization of States in Web Hypertext Applications

353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423

// completely comprisingparams[2] = (len1-len2).toString();} else if (off1 >off2 && off1+len1 >off2 && off1+len1 >off2+len2){//overlapping at the beginningparams[2] = (off2-off1).toString();} else if (off1 >off2 && off1 >off2 + len2 && off1+len1 >off2+len2){//overlapping at the end
params[1] = (off2).toString();
params[2] = (len1 - (off2 + len2 - off1)).toString();} else if (off1 >= off2 + len2){// completely ahead
params[1] = (off1-len2).toString();}
break;
case _BR:
var len1 = parseInt(o1.parameters[2]);if (off1 >= off2){params[1] = (off1+1).toString();} else if (off2 >off1 && off2 >off1 + len1) {params[2] = (len1 + 1).toString();}
break;
case _PSET: break;case _RSET:var len1 = parseInt(o1.parameters[2]);var len2 = parseInt(o2.parameters[2]);if (o1.parameters[3] == o2.parameters[3]){var n = o1.parameters[3];if (off1 >off2 && off1+len1 >off2+len2){
if ((o1.parameters[4] != o2.parameters[4] && o1.origin >o2.origin && !SPEC_STYLE[n]) ||(o1.parameters[4] == o2.parameters[4] && SPEC_STYLE[n])){return [{"name": o1.name , "parameters" : [tgt1, (off1).toString(),(off2-off1).toString(), n, o1.parameters[4]], "origin": o1.origin},{"name": o1.name , "parameters" : [tgt1, (off2+len2).toString(),(off1+len1-(off2+len2)).toString(), n, o1.parameters[4]],"origin": o1.origin}];}} else if (off1 >off2 && off1+len1 >off2 && off1+len1 >= off2+len2){
if ((o1.parameters[4] != o2.parameters[4] && o1.origin >o2.origin && !SPEC_STYLE[n]) ||(o1.parameters[4] == o2.parameters[4] && SPEC_STYLE[n])){params[2] = (off2-off1).toString();}} else if (off1 >= off2 && off1 >
off2+len2 && off1+len1 >off2+len2){
if ((o1.parameters[4] != o2.parameters[4] && o1.origin >o2.origin && !SPEC_STYLE[n]) ||(o1.parameters[4] == o2.parameters[4] && SPEC_STYLE[n])){params[1] = (off2+len2).toString();
params[2] = (off1+len1-(off2+len2)).toString();}} else if (off1 >= off2 && off1+len1 >177

Instant Synchronization of States in Web Hypertext Application

424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493

178

= off2+len2){
if ((o1.parameters[4] != o2.parameters[4] && o1.origin >o2.origin && !SPEC_STYLE[n]) ||(o1.parameters[4] == o2.parameters[4] && SPEC_STYLE[n])){return [];}}}break;
case _EINS:var len1 = parseInt(o1.parameters[2]);if (off1 >= off2){params[1] = (off1+1).toString();} else if (off2 >off1 && off2 >off1 + len1) {params[2] = (len1 + 1).toString();}
break;}
return [{"name": o1.name , "parameters" : params, "origin": o1.origin}];break;
case _EINS:
var params = o1.parameters.slice(0);switch(t2){case _INS:
if (off1 >= off2){
var len2 = length(o2.parameters[2]);params[1] = (off1 + len2).toString();}
break;
case _DEL:
var len2 = parseInt(o2.parameters[2]);if (off1 >off2 && off1 >
off2+len2){
params[1] = off2.toString();} else if (off1 >= off2 + len2) {params[1] = (off1 - len2).toString();}
break;
case _BR:if (off1 >off2){
params[1] = (off1 + 1).toString();}
break;
case _PSET: break;case _RSET:// nothing happens
break;
case _EINS:
if (off1 >off2 || (off1 == off2 && o1.origin >o2.origin)){params[1] = (off1 + 1).toString();}
break;}
return [{"name": o1.name , "parameters" : params, "origin": o1.origin}];break;
default:}
console.log("Inclusion: no match!");return [{"name":o1.name, "parameters": o1.parameters.slice(), "origin":o1.origin}];};})();