DROPBOX EX. 1003
`
`DROPBOX EX. 1003
`
`
`
`

`
`High-Latency, Low-Bandwidth Windowing
`in the Jupiter Collaboration System
`
`David
`Michael
`
`Curtis,
`Lumping
`
`Pavel
`A. Nichols,
`John
`Dixon,
`and
`Xerox PARC
`3333 Coyote Hill Rd.
`Palo Alto, CA 94304
`+1 4158124452
`{nichols,pavel, mdixon,lamping} @pare.xerox.com
`
`drawing widget,
`a text editor, a graphical
`includes
`number of simpler widgets such as buttons and sliders.
`
`and a
`
`KEYWORDS
`UIMS, window toolkits, CSCW, groupware
`mistic concurrency
`control.
`
`toolkits,
`
`opti-
`
`a
`
`1 INTRODUCTION
`by providing
`Jupiter
`supports
`long-term collaboration
`shared, persistent virtual world composed of network
`places
`[7]. By mirroring
`some of
`the ways people use physical
`places, network places provide a context
`in which
`users can work individually
`or with other users, by mov-
`ing between (virtual)
`places,
`users can organize the materials they are working on and
`the resources they are using by distributing
`them among
`the places, and
`into
`and resources can be brought
`other users, materials,
`immediately
`gaining access to the
`an activity at any time,
`full context of the activity.
`
`l
`
`l
`
`l
`
`ABSTRACT
`virtual world intended to
`Jupiter
`is a multi-user, multimedia
`support
`long-term remote collaboration.
`In particular,
`it sup-
`ports shared documents,
`shared tools, and, optionally,
`live
`audio/video
`communication.
`Users who program can, with
`only moderate effort, create new kinds of shared tools using
`a high-level windowing
`toolkit;
`the toolkit
`provides
`trans-
`parent
`support
`for
`fully-shared
`widgets
`by default.
`This
`paper describes
`the low-level
`communications
`facilities
`used by the implementation
`of the toolkit
`to enable that sup-
`port.
`
`application
`including
`the Jupiter virtual world,
`The state of
`code written by users, is stored and (for code) executed in a
`central server shared by all of
`the users. This architecture,
`along with our desire to support multiple
`client platforms
`and high-latency
`networks,
`led us to a design in which the
`server and clients communicate
`in terms of high-level wid-
`gets and user events.
`
`As in other groupware toolkits, we need a concttrrency-con-
`trol algorithm to maintain common values for all
`instances
`of
`the shared widgets. Our algorithm is derived from a fully
`distributed,
`optimistic
`algorithm developed
`by Ellis
`and
`Gibbs [12]. Jupiter’s
`centralized
`architecture
`allows us to
`substantially
`simplify
`their algorithm. This combination
`of a
`centralized
`architecture
`and optimistic
`concurrency
`control
`gives us both easy serializability
`of concurrent
`update
`streams and fast response to user actions.
`
`to fix up
`The algorithm relies on operation transformations
`are not
`conflicting
`messages. The best
`transformations
`concerns
`always obvious,
`though,
`and several conflicting
`are involved
`in choosing them. We present our experience
`with choosing
`transformations
`for our widget
`set, which
`
`Permission to make digikl/l)ard
`for
`[his mateciai
`copies of all or part uf
`personal or classroom usc is granted wi[hout
`fee provided
`thal
`Ihe copies
`are not made or distributed
`for pn)fit or commercial
`advautage,
`Ihe copy-
`right notice,
`the title of {he publication
`and its date appear. and notice is
`given *a: =v~yrigl~t
`i. by pvrmimivn
`of (IIC ACM.
`Im. To copy o[herwise,
`to repubhsh, to post on servers or to redistribute
`to lists,
`requires specific
`permission
`and/or
`fee.
`UIST 95 Pittsburgh PA USA
`@ 1995 ACM 0-89791-709-x/95/l
`
`1.. $3,50
`
`the Jupiter world is intended to be hi~hlv cus-
`addition,
`In
`tomizable by its us~rs, so that they can adapt
`it to th~ir needs
`as readily
`as people adapt physical
`spaces. This includes
`facilities
`for
`creating
`new places,
`connecting
`existing
`places, moving
`objects
`among
`places,
`creating
`new
`instances
`of generic
`objects, modifying
`the behavior
`of
`existing
`objects,
`and creating
`completely
`new types of
`generic objects. These last
`two capabilities
`involve writing
`programs in Jupiter’s
`internal
`interpreted
`programming
`lan-
`guage.
`
`is that all objects
`of Jupiter
`the key characteristics
`One of
`This applies to the places
`and persistent.
`there are shared
`themselves,
`to the documents or other materials, and to the
`tools. For example,
`the Whiteboard
`is a useful
`generic
`object
`that provides a drawing surface with simple sketching
`tools. As users come and go from the place containing
`the
`whiteboard
`they may open it, see its contents. and edit
`them;
`any number of users may be simultaneously
`viewing
`and
`editing it. Even if all
`the users leave the place,
`log out of
`
`November 14-17, 1995
`
`UIST ’95
`
`111
`
`Dropbox Ex. 1003
`
`

`
`Jupiter, and come back later,
`drawing that was left on it.
`
`the whiteboard will
`
`retain the
`
`Jupiter’s central server stores the state of virtual objects and
`executes all of
`their associated program code.
`In contrast,
`the client programs run by users on their
`local workstations
`remain largely ignorant of
`this virtual-world model. Clients
`simply manage their
`local
`input/output
`hardware of behalf
`of
`the server and the user.
`In particular,
`clients create and
`modify windows
`according to specifications
`received from
`the server, report user input events to the server, and (when
`available)
`capture,
`transmit,
`receive, and display audio and
`video data under user and server control
`[8].
`
`communi-
`clientiserver
`This paper describes the low-level,
`cations facilities
`used by the implementation
`of the window-
`ing toolkit
`to support Jupiter’s
`pervasive
`sharing between
`users. The Jupiter programmer’s
`view of
`the toolkit will be
`described in a separate,
`forthcoming
`paper.
`
`to two sources of signif-
`are subject
`Jupiter user interactions
`icant
`response latency, which occasionally
`cause delays up
`to a few seconds. First,
`the serialization
`of server actions can
`introduce
`contention
`for execution
`resources. More gener-
`ally,
`though, some users connect
`to the system through high-
`latency communications
`paths, such as low-bandwidth
`dia-
`ltrp lines and long-haul
`or congested Internet
`routes. We
`developed
`the design presented here in response to these
`specific
`sources of
`latency,
`but
`the solutions
`described
`would be applicable
`to any situation with the potential
`for
`unacceptable user-event
`response times.
`
`in terms of high-level
`The server and client communicate
`widgets,
`such as sliders and text editors 1. Both client and
`server keep track of widget
`state, and communicate
`high-
`Ievel state changes,
`instead of
`low-level
`user events and
`graphics primitives.
`This high-level
`protocol means they
`transmit
`less information,
`and less frequently,
`than if a more
`traditional
`networked window system (such as the X win-
`dow system [25]) were used. Because windows
`can be
`shared between several users, we need a concurrency
`con-
`trol algorithm to maintain consistency.
`
`sys-
`or
`
`use by groupware
`control algorithms
`The concurrency
`as being pessimistic
`tems for sharing can be classified
`require
`communication
`optimistic.
`Pessimistic
`algorithms
`with other sites or with a central coordinator
`before making
`a change to data. This communication
`can be made apparent
`to the user, as with a floor control policy, or left
`implicit,
`where the user’s program does the communication
`behind
`the scenes. Even in the latter case, the user must wait
`for a
`round-trip
`to the other sites before any change is finalized.
`
`control. on the other hand, requires
`concurrency
`Optimistic
`no communication
`before
`applying
`changes locally.
`The
`party making a change applies it
`immediately,
`then informs
`the other parties of
`the action.
`If more than one participant
`makes a change at the same time, a conflict
`resolution
`algo-
`rithm creates compensating
`changes to move everyone to
`the same final state.
`
`com-
`for high-latency
`are well-suited
`algorithms
`Optimistic
`since the results of a user’s actions
`channels
`munications
`may be displayed without waiting
`for a communications
`round-trip.
`For
`these reasons, we chose an optimistic
`algo-
`rithm for Jupiter. The client always applies user changes
`(such as moving
`a slider or typing new text)
`immediately,
`without waiting
`for a server
`response,
`thereby providing
`users with immediate
`feedback.
`
`control algorithms
`concurrency
`Another way of classifying
`is by whether
`they use a central coordinator
`or are fully dis-
`tributed. Because Jupiter already had a central server main-
`taining the persistent
`virtual world,
`it was natural
`for us to
`use a centralized
`architecture.
`
`of these two choices turned out to simplify
`The combination
`our system design considerably. While there are example of
`both centralized
`and distributed
`groupware
`systems using
`pessimistic
`concurrency
`control,
`the systems using optimis-
`tic algorithms
`are fully distributed. A distributed,
`optimistic
`algorithm must be prepared to handle a change from any
`participant
`at any time. Much of
`the complexity
`for
`these
`algorithms
`comes from this requirement,
`and getting all
`the
`cases right
`is very difficult.
`
`the
`for
`only
`protocol
`Jupiter uses the optimistic
`Instead,
`server-client
`links. To the server, each client
`individual
`appears to be operating
`synchronously
`with respect
`to the
`server’s actions. The server can thus use a simple change
`propagation
`algorithm to keep all
`the clients updated and in
`sync.
`
`In the next section, we review related work. SectIons 3 and 4
`describe the toolkit’s
`design in more detail.
`In Sections 5
`and 6, we describe the two-way optimistic
`algorithm, which
`draws from previous work.
`then describe how it
`is used to
`achieve
`n-way
`consistency.
`Section
`7 discusses
`issues
`related to choosing message transformations,
`a necessary
`part of the optimistic
`algorithm we use.
`
`2 RELATED WORK
`The related work falls into two main categories, groupware
`systems with their approaches to concurrency
`control,
`and
`window
`systems
`that
`cope with
`low-bandwidth,
`high-
`latency communication
`links.
`
`to the Jupiter chent, which is the pro-
`to refer
`1. We use “client”
`gram that runs on the user’s machme and displays windows
`on that
`machme’s display. Our
`“server”
`runs application
`programs, which
`make requests of
`the chent and respond to user events reported by
`it. The X window system [25] uses these words m the opposite
`sense; “clients”
`are apphcatlons,
`and the “server”
`]s the program
`that displays the windows.
`
`for
`toolkits
`systems provide either
`A number of groupware
`building
`shared applications,
`or specific shared applications
`such as text or drawing
`editors. These include COEX [20],
`DistEdit
`[17], GroupDesign
`[16], GroupKit
`[24],
`the Grove
`text editor
`[12], LIZA [14], MMConf
`[5], Rendezvous
`[21],
`Suite [11 ], and Visual Obliq [3]. LIZA, Rendezvous, Suite
`
`112
`
`UIST ’95
`
`November 14-17, 1995
`
`Dropbox Ex. 1003
`
`

`
`and Visual Obliq use a centralized coordinator, while COEX,
`DistEdit, GroupDesign, GroupKit,
`the Grove text editor, and
`MMConf
`are distributed.
`
`and Grove are the only systems to
`these, GroupDesign
`Of
`use optimistic
`concurrency
`control, and they have decentral-
`ized architectures. As discussed above,
`these algorithms
`are
`made more complex by having to support
`full n-way repli-
`cation. The Jupiter
`two-way
`algorithm is derived from the
`dOPT algorithm used by Grove. This paper extends their
`work by showing a simplified
`algorithm that
`takes advan-
`tage of
`the centralized
`architecture,
`and discusses the prag-
`matic
`of designing
`the message transformations
`required
`by the algorithm.
`
`to Visual Obliq in a different way. Both
`is similar
`Jupiter
`systems use techniques
`from the FormsVBT
`system for
`Modula-3
`[4] and provide
`took
`for
`rapid prototyping
`of
`shared applications. Visual Obliq requires that
`the applica-
`tion
`explicitly
`manage
`sharing, while
`Jupiter
`provides
`shared widgets. Also, Visual Obliq is not optimized
`for low-
`bandwidth
`or high-latency
`communications.
`
`commu-
`Another group of systems deal with low-bandwidth
`nications
`channels
`in single-user window systems. These
`systems use two basic approaches to dealing with low-band-
`width: compression and code-shipping.
`
`X
`Low-bandwidth
`systems include Xremote,
`Compression
`[9, 10], and vari-
`(LBX)
`[13], Higher bandwidth X (HBX)
`remote access to
`ous commercial
`programs
`for providing
`Microsoft Windows
`connections,
`such as CarbonCopy.
`They try to reduce the bandwidth
`used while keeping the
`same semantics for the network protocol. Although
`remark-
`able compression
`ratios can be achieved (HBX gets a 20:1
`compression ratio in some cases), they do not eliminate
`the
`round trips caused by user interactions
`such as keystrokes
`and mouse clicks.
`
`by only sending mes-
`Jupiter eliminates many round-trips
`sages for larger-scale widget value updates, not
`for
`individ-
`it
`ual
`low-level
`keyboard
`and mouse events. However,
`requires a trade-off
`from the application
`designer:
`Jupiter
`applications must use the Jupiter
`toolkit,
`and are thus lim-
`ited to the set of widgets it provides.
`
`The other approach to coping with slow networks is to split
`the application
`into two parts, and send the code for one part
`to the user’s machine where it can have fast access to the
`display and input devices. This is done by Sun Microsys-
`tems’ NeWS [15] and HotJava [26] systems, and by Bell
`Lab’s Blit
`terminals
`[22]. We call
`this code-shipping.
`
`very powerful,
`approach is in principle
`The code-shipping
`since it allows the application
`to customize the communica-
`tions protocol
`to its particular
`needs. An application
`can
`send most of
`its user interface to the other side, and only
`communicate
`high-level
`events, such as “please run this
`database transaction with these inputs.” The Sam text editor
`[23]
`for the Blit
`is an example of such an application.
`
`(VBOX
`(HBox
`(Button %help (Text “Help”))
`(Fill)
`(Button %quit (Text (FGColor red) “Dismiss’’)))
`(Bar)
`(TextEdit %contents (BGColor white)))
`
`form for Jupiter. Figure 2
`1: An example
`Figure
`shows the resulting window.
`
`Help
`
`w
`
`I
`
`Figure 2: A window created by the form in Figure 1.
`
`to
`designer
`forces the application
`code-shipping
`However,
`write a distributed
`application.
`The program must be split
`and a network protocol
`invented for it. While this is straight-
`forward in some cases, the problems of distributed
`systems,
`such as maintenance
`of replicated
`state, must be addressed
`by the programmers
`of
`these system.
`In some systems,
`the
`code shipped to the user interface engine must be written in
`a different programming
`language from the application,
`fur-
`ther complicating
`development.
`
`is able to hide
`Jupiter
`Again, by trading off some generality,
`The applica-
`these network problems
`from the application.
`interface, and
`tion programmer
`sees a conventional
`toolkit
`the protocols and remote code are handled by the system.
`
`3 THE APPLICATION INTERFACE
`the
`instance of
`Jupiter
`is built
`on top of an unmodified
`LambdaMOO
`server;
`all
`of
`the
`server-side
`facilities
`described here are written
`in the MOO programming
`lan-
`guage [6]. The server contains a database of all
`the informat-
`ion
`in the Jupiter
`environment,
`as well
`as a MOO
`interpreter. Windowing
`applications
`are written by Jupiter’s
`users and run in this server.
`
`to an application
`presented
`interface
`The programming
`to that of the FormsVBT
`system [1, 4].
`writer
`is very similar
`A window is described with an S-expression
`that specifies
`the types of widgets present and a containment
`hierarchy for
`laying them out. For example, Figure
`1 shows the descrip-
`tion of a window we use for editable documents
`in Jupiter,
`and Figure 2 shows how that window appears to the user.
`
`things (VBOX),
`stack of
`This window consists of a vertical
`consisting of a
`the first of which is a horizontal
`row (HBox)
`push-button
`named “help”
`containing
`the text “Help”,
`some
`filler
`that serves to place the two buttons at either end of the
`row, and another button named “quit”
`and displaying
`the
`
`November 14-17, 1995
`
`UIST ’95
`
`113
`
`Dropbox Ex. 1003
`
`

`
`or vertical composition
`horizontal
`spacing between widgets
`space around a widget subtree
`
`Layout widgets
`HBox, VBOX
`Fill, Glue, Bar
`Rim. Border
`Leaf widgets
`a slider
`Numeric
`graphical display and interaction
`StrokeEdit
`output only
`Text
`full
`text editor
`TextEdit
`list of text
`items to choose from
`TextList
`single-line
`input
`TypeIn
`append-only with user input
`Typescript
`displays a digital video stream
`VideoPane
`Filter widgets, which decorate a widget
`subtree
`AudioHighlight
`flashes a border around the subtree
`when a user speaks
`shows a visible onfoff value
`push once or momentary
`
`Boolean
`Button
`
`automati-
`are sharable, with the toolkit
`Jupiter applications
`identical widget
`values for each partici-
`cally maintaining
`pating user. Each change made by a user is reported to the
`application
`and automatically
`propagated to the other users.
`
`4 THE CLIENT-SERVER INTERFACE
`It
`local workstation.
`Jupiter’s
`users run the client on their
`running on a central
`makes a TCP connection
`to the server,
`machine. The client program is assumed to evolve slowly,
`with users obtaining a new one primarily when major proto-
`col changes occur. Currently,
`implementations
`for the client
`exist
`for several Unix platforms,
`using the TcllTk
`toolkit
`[18], and for Microsoft Windows,
`using the native Windows
`programming
`environment.
`
`the
`largely parallels
`for Jupiter
`protocol
`The client-server
`in
`programmer’s
`interface; most calls by applications
`result
`messages to the client, and most client messages generate
`event
`notifications
`to the application.
`The protocol
`is
`designed to use one-way messages, not requiring
`immediate
`replies, whenever possible.
`
`Table 1: Widget
`
`types available in Jupiter
`
`drawn in red. Below this row is a thin black
`text “Dismiss”
`line (Bar), and a text editor widget named “contents”.
`
`the server sends the S-expres-
`When a window is created,
`sion describing
`the window to the client, which creates the
`corresponding window.
`
`to manipu-
`is used by the application
`The name on a widget
`late the widget
`(e.g., change its value) and by the toolkit
`to
`inform the application
`of any user interactions with the wid-
`get. The name is also used to refer
`to the widget
`in the com-
`munications
`protocol.
`
`supported by Jupiter.
`the widgets
`Table 1 shows a list of
`These are mostly
`the conventional
`set from other window-
`ing toolkits. The TypeIn widget
`is for single line text entry.
`The TextEdit widget
`is for editing larger
`(plain text) docu-
`ments. The StrokeEdit
`widget
`is a graphical
`display
`and
`interaction widget, similar
`to EZD [2] or Tk’s canvas widget
`[18]. The VideoPane
`and AudioHighlight
`widgets provide
`support
`for audiolvideo
`communications.
`
`values can
`the window is created, updates to widget
`After
`originate
`from either
`the client or server. Updates to simple
`widgets, such as Numerics
`and Booleans,
`include the entire
`widget value. For user-originated
`changes,
`low-level mouse
`and keystroke interactions
`are filtered out. For example,
`the
`Numeric widget does not send intermediate
`values while the
`slider
`is being moved, but waits until
`the mouse button is
`released to send the final widget value.
`
`and StrokeEdits,
`such as TextEdits
`More complex widgets,
`use incremental
`state update messages. For TextEdits, a gen-
`eral
`“replace
`this region of
`text with this value” message
`suffices. StrokeEdits use a more complex protocol,
`shown in
`Table 2.
`
`type exports a set of operations to the applica-
`Each widget
`tion. For example,
`the TextList widget, which allows a user
`to select
`from a list of
`text
`items, supports operations
`for
`changing the list of
`items and for setting which item is cur-
`rently selected. Widgets with small values, such as Booleans
`and Numerics,
`support setting that value. Widgets with com-
`plex value types, such as the TextEdit
`and StrokeEdit wid-
`gets, supply operations for incremental
`update.
`
`Both client and server maintain a full copy of each widget’s
`value. The client copy allows user changes to be reflected
`immediately
`in the window, before they are processed by the
`server. The server’s copy is used to coordinate updates gen-
`erated by the various clients sharing the widget.
`In addition,
`the server’s
`copy provides
`quick
`access for applications;
`they do not incur
`round-trip
`delays for fetching the values of
`widgets in order to do computations.
`
`type supplies a set of event notifica-
`In addition, each widget
`tions, most of which are a result of user interactions. Buttons
`notify the application when they have been activated by the
`user. Numerics do so when the user chooses a new value for
`them. The StrokeEdit widget has a number of user interac-
`tion modes, allowing
`the user to click on existing strokes, or
`add new ones. When any widget event occurs, a predeter-
`mined application
`routine is invoked with information
`about
`the event.
`
`PROTOCOL
`5 THE TWO-WAY SYNCHRONIZATION
`As mentioned earlier, optimistic
`concurrency
`control allows
`clients to change widget values without having to wait
`for a
`server interaction.
`If either
`the client or the server initiates a
`change to a widget,
`the change is immediately
`applied
`locally
`and a notification
`is sent
`to the other party. When
`messages cross on the wire,
`each receiver
`fixes up the
`incoming message so that
`it makes sense relative
`to the
`receiver’s
`current state. The algorithm we describe guaran-
`tees that
`these fixups will suffice,
`that
`the client and server
`
`114
`
`UIST ’95
`
`November 14-17, 1995
`
`Dropbox Ex. 1003
`
`

`
`Server Operations
`create stroke, delete stroke
`
`move stroke
`set stroke attributes
`
`set mode
`
`set creation attributes
`
`Client Operations
`hit down, hit up
`
`sweep down, sweep drag,
`sweep up
`
`create stroke, delete stroke
`
`change the set of graphic
`items being displayed
`move an existing stroke
`change color, etc. of an
`existing stroke
`set a user interaction mode,
`allowing
`local creation or
`deletion of strokes
`set attributes for strokes cre-
`ated by the user
`
`report simple mouse hits of
`existing strokes
`report strokes hit by a sweep
`operation that potentially
`passes through several
`strokes
`reports user-initiated
`ations and deletions
`
`cre-
`
`Table 2: Operations available on StrokeEdit widgets
`
`client
`
`server
`
`“ABCDE
`
`del 4
`
`“ABCE
`
`“ABCDE
`
`de] 2
`
`“ACDE”
`
`“ACE”
`
`“ACD”
`
`conflict. The
`of an update
`3: An example
`Figure
`“D, while the
`client has deleted the fourth character,
`“B. Without
`server has deleted
`the second
`one,
`concurrency
`control,
`the client and server wind up
`with different
`final values. The fix is to have the
`sewer
`transform the client’s message into “del 3 so
`that both client and server get the same result.
`
`will always agree on the widget
`have been received and processed.
`
`value when all messages
`
`systems, Jupiter does not use the
`other groupware
`Unlike
`directly
`between
`the
`clients.
`synchronization
`protocol
`Instead, each client synchronizes with the server,
`the server
`serializes all changes and echoes changes made by one cli-
`ent
`to all others that are sharing the widget. This lets us
`achieve
`n-way
`synchronization
`by running
`independent
`two-party
`synchronization
`protocols
`on each client-server
`link.
`
`Figure 3 shows an example of
`TextEdit widget
`that cross.
`If
`
`two messages for a single
`the messages are not
`trans-
`
`client
`
`/
`
`3,0
`
`2,0
`
`3,1
`
`0.0
`
`,,/
`.
`xi’
`Lo.,
`\
`
`L
`
`0,1
`
`., server
`\
`
`0,3
`
`0’2
`
`1,3
`
`/l’~’\
`
`2, f’
`\
`
`3,2
`
`‘2{ ~.
`
`\
`
`,:1’2
`
`. .
`
`2,3
`
`3,3
`Figure 4: The state space
`the client and server
`traverse while processing messages. Each node is
`Iabelled with
`the
`number
`of
`client
`and
`server
`messages
`processed when in that state. A conflict
`has occurred starting from the state 1,1.
`
`the client and server windup with differ-
`formed on receipt,
`the widget. Since the client
`intended to
`ent
`final values for
`delete the “D”
`in the original
`string,
`its message must be
`fixed up to read “delete 3“ when the server detects the con-
`flict.
`
`for handling conflicting messages is a func-
`tool
`The general
`that maps a pair of messages to the fixed up ver-
`tion, xform,
`sions. We write
`Xforrn(c, s) = { c ‘, s ‘}
`client and server messages.
`where c and s are the original
`The messages c‘ ands’ must have the property that if
`the cli-
`ent applies c followed
`by s‘, and the server applies s fol-
`lowed by c‘,
`then the client and server will wind up in the
`same final state.
`
`that have this
`there are many possible functions
`Of course,
`property. For example,
`the function
`x~orrn(c, s) = {delete
`everything,
`delete everything } would
`satisfy our ordering
`property, but would probably not satisfy many users ! In gen-
`eral,
`the transforms
`should try to find some “reasonable”
`way to combine the two operations
`into a final effect. For
`our delete example,
`this is easy to do:
`x~irrn(del
`x, del y) =
`{delx-l,
`dely}ifx>y
`{delx,
`dely-l)ifx<y
`{no-op, no-op}
`ifx = y
`to
`in the document
`index
`is, we modify
`the later
`That
`account
`for
`the earlier deletion. Other pairs of operations
`present more difficulties;
`Section 7 talks about
`the issues in
`designing transformations
`in more detail.
`
`to picture the
`is helpful
`it
`the full protocol,
`In describing
`state space that
`the client and server pass through as they
`process messages. Figure 4 shows an example. Each state is
`labelled with the number of messages from the client and
`server
`that have been processed to that point. For example,
`
`November 14-17, 1995
`
`UIST ’95
`
`115
`
`Dropbox Ex. 1003
`
`

`
`int myMsgs = O; /’ number of messages generated *1
`int otherMsgs = O; P number of messages received ‘1
`queue outgoing = ~;
`
`{
`Generate(op)
`apply op locally;
`send(op, my Msgs, otherMsgs);
`add (op, my Msgs) to outgoing;
`myMsgs = myMsgs + 1;
`
`‘/
`
`} R
`
`{
`eceive(msg)
`/“ Discard acknowledged messages.
`for m in (outgoing){
`if (m.myMsgs c msg.otherMsgs)
`remove m from outgoing
`
`}P
`
`ASSERT msg.myMsgs == otherMsgs. *1
`for i in [1..length(outgoing)]
`{
`/’ Transform new message and the ones in
`the queue. l1
`{msg, outgoing[i]} = xform(msg, outgoing[i]);
`
`}a
`
`pply msg.op locally;
`otherMsgs = otherMsgs + 1;
`
`} F
`
`to
`igure 6: The algorithm used by client and server
`deal with conflicting messages. The pair
`(myMsgs,
`otherMsgs)
`corresponds
`to the state from Figure 4.
`
`one step, we can use the xform func-
`by only
`diverge
`client
`If
`they diverge further, however,
`the situation
`tion directly.
`is more complex. Consider Figure5a.
`In this case, the client
`has executed c and receives the conflicting message S1 from
`to get to
`the server. It uses the xform function to compute sl’
`the state (1, 1). The server
`then generates message S2 from
`the state (O,1),
`indicating
`that
`it still hasn’t processed c.
`s2) because
`What should the client do? It can’t use xform(c,
`c and S2 were not generated from the same starting state. For
`example,
`if c is “del 4,” SI is “del 1,“ and S2 is “del 3,” then
`the correct
`transform for S2 is “no-op,”
`but xform(c,
`s2) is
`“del 3.”
`
`The solution is depicted in Figure 5b. When the client com-
`putes sl’,
`it must also remember c‘,
`the other returned value
`from xform.
`This
`represents
`a hypothetical
`message
`that
`the
`client
`could
`have generated
`to move
`from the state (O, 1) to
`(1, 1). When S2 arrives,
`the client
`can use c’
`to compute
`s2) = {c”, s2’}
`xfornt(c’,
`the server has pro-
`If
`It executes S2’ to get to the state (1,2).
`cessed the client’s message,
`it will be In the state (1 ,2) as
`well.
`If not,
`its next message will originate from (0,3), so the
`client saves c” just
`in case.
`
`shown in
`We are now ready to examine the full algorithm,
`Figure 6. We describe It
`from the client’s perspective,
`but
`the server’s actions are identical.
`The algorithm maintains
`the invariant
`shown in Figure 7. The server was last known
`to be in the state (x, y). Since then,
`the client has sent k mes-
`
`‘ ‘ . =rvel-
`<
`
`‘\
`
`0,2
`
`two
`the server generates
`In this example,
`Figure 5:
`messages, S1 and s2,
`that conflict with the chent
`message c.
`in order
`to process s2,
`the client must
`compute c’, even though it will never execute it.
`
`it has generated and pro-
`IS in the state (2,3),
`the client
`if
`cessed two messages of
`its own, and has received and pro-
`cessed three from the server.
`
`the client or server moves
`As each message is processed,
`they process messages in the
`down though the state space. If
`same order
`(that
`is,
`there are no conflicts),
`then they will
`take the same path.
`If
`there is a conflict,
`then the paths will
`diverge,
`as shown in the diagram.
`The client
`and server
`moved to the state (1,1)
`together by first processing a client
`message, and then a server message. At
`that point,
`the client
`and server processed different messages, moving
`to the
`states (2, 1) and (1,2),
`respectively. They each received and
`processed the other’s message using the xform function
`to
`move to state (2,2). Then the server generated another mes-
`sage, sending it and the client
`to (2,3).
`
`labels each message with the state the sender
`The protocol
`was in just before the message was generated. The concur-
`rency-control
`algorithm uses these labels to detect conflicts,
`and the xform function to resolve them. The algorithm guar-
`antees that, no matter how far the client and server diverge
`in state space, when they do reach the same state, they will
`have identical
`values for all
`their widgets.
`
`takes a pair of client and server mes-
`The xform function
`sages that were generated from the same starting state and
`returns
`transformed messages that allow the client
`and
`server to reach the same final state. As long as the server and
`
`116
`
`UIST ’95
`
`November 14-17, 1995
`
`client
`/
`
`(a)
`
`client
`
`/
`
`(b)
`
`~
`
`.s
`‘~
`O!l. s2
`.
`
`“.
`
`server
`%
`
`‘v
`
`0,2
`
`2,0
`
`0,0,
`
`/“c
`
`1,0
`
`51’
`
`1,1
`
`\
`
`2,1
`
`L,L
`
`m.
`
`~
`
`(f”.s
`
`‘A
`0)1.:2
`c’
`
`S1’
`
`Z.
`
`l’;/
`
`2,1
`
`S2’
`
`1,2
`
`1,1
`
`\
`
`2,2
`
`Dropbox Ex. 1003
`
`

`
`client
`/
`
`X,y
`
`/
`
`., server
`\
`
`n
`
`client
`
`server
`
`window
`
`window
`
`A
`
`B
`
`I
`
`I
`
`/“
`X+(,V
`.
`
`/
`
`‘i
`x+i,y+l
`
`/“
`x+k,y
`
`n
`
`n
`
`Figure 7: Whenever our algorithm is not processing a
`message,
`the situation shown above holds (as seen
`by the client). The server was last known to be in the
`state (x, y). We are in the state (x+k, y) and have
`saved all the messages necessaty
`to get
`from (x, y)
`to (x+k, y). The next server message must originate
`from some state along this path.
`
`in the state (x+k, y). These messages are
`leaving it
`sages,
`queue.
`In the code, myMsgs
`is x+k, and
`kept
`in the outgoing
`otherMsgs
`is y.
`
`is easy:
`this invariant
`Sending a message while maintaining
`just apply the operation locally to move to (x+k+ 1, y), trans-
`mit
`it to the server, and then append the message to the out-
`going message queue.
`
`server mes-
`incoming
`the next
`For reception, we know that
`sage must originate from one of the states between (x, y) and
`inclusive;
`that
`is,
`the server will
`have processed
`(x+k,
`y)
`those k client messages. Assume
`some arbitrary number of
`taking the server
`to (x+i,
`that
`it comes from state (x+i,
`y),
`y+ 1). First, discard the saved messages that
`take us from (x,
`y) to (x+i, y), as they are no longer needed. Next,
`run the
`incoming message through the transformer with respect
`to
`each of
`the saved messages. The final
`result will be a mes-
`to (x+k, y+l), which we
`sage that
`takes us from (x+k,
`y)
`apply locally. While
`doing this, save the transformed
`ver-
`sion of each saved message. When we are done, we have a
`sequence of saved messages that
`takes us from the last
`known server state,
`(x+i, y+ 1),
`to our current
`state,
`(x+k,
`y+l ). We have thus restored the invariant
`and are ready for
`the next
`incoming message.
`
`Some fine points
`they are
`In our system, messages must be saved until
`acknowledged
`by the other party, since they may be needed
`in order
`to fix up incoming messages. Normally,
`these
`acknowledgments
`are piggy-backed
`on traffic
`going
`the
`other way. However,
`it is possible for the traffic to a window
`to be one-sided (e.g.,
`for a status display window being peri-
`odically
`updated). Therefore,
`each side must periodically
`generate explicit acknowledgments
`(i.e. no-op messages)
`prevent
`the outgoing queues from growing forever.
`
`to
`
`B(O,O)
`
`A(l
`
`,0)
`
`A(2,0
`
`*
`
`Figure 8: Sequence numbers must be assigned at a
`grain at least as fine as the locking granularity of the
`toolkit. Otherwise, an incoming message waiting for a
`might
`be
`incorrectly
`lock
`on
`one
`window
`acknowledged
`by the reply to a message for another
`window.
`
`of message
`is the interaction
`consideration
`important
`An
`that applica-
`The toolkit
`requires
`locking.
`with
`numbering
`lock whenever
`they are examining
`a per-window
`tions hold
`widget
`values
`for
`that window.
`If a message
`or changing
`arrives
`from a client
`while
`this
`lock
`is held,
`the message
`the lock is released.
`cannot
`be processed
`until
`
`before they
`However, messages must not be acknowledged
`are processed. Figure 8 illustrates
`this problem. The client
`sends a message to window B, which has been locked by
`application
`code in the server. As a result, processing of that
`message is deferred until
`the lock is released. Meanwhile,
`the client sends a message to the unlocked window A, which
`generates a reply
`that acknowledges
`both of
`the client’s
`messages. While the window is locked,
`the application
`gen-
`erates a message for B. which also claims to have been gen-
`erated after both client messages. However,
`the client’s first
`message actually hasn’t been processed yet. The sequence
`numbers