DROPBOX EX. 1032
`
`DROPBOX EX. 1032
`
`
`
`

`

`I Wmyiiiiiiiilliiiiiiiiiii.
`
`“106E! ULBE‘IEI‘IH E’
`
`Eighth Annual
`Symposium on
`User Interface
`Software and
`
`Technology
`
`Proceedings of the
`ACM Symposium on
`User Interface Software
`and Technology
`
`Pittsburgh, Pennsylvania
`November 14-17, 1995
`
`a
`
`Sponsored by ACM SIGGRAPH
`and ACM SIGCHI
`in cooperation with ACM SIGSOFT
`
`Dropbox Ex. 1032
`Page 1
`
`Dropbox Ex. 1032
`Page 1
`
`

`

`The Association for Computing Machinery
`1515 Broadway
`New York, NY. 10036
`
`ACM ISBN: 0-89791—709—x
`
`Additional copies may be ordered prepaid from:
`
`ACM Order Department
`P.O. Box 12114
`Church Street Station
`New York, N .Y. 10257
`
`Phone: 1-800-342—6626
`(U.S.A. and Canada)
`1-212-626-0500
`(All other countries)
`Fax: 1-212-944-1318
`
`Copyright © 1995 by the Association for Computing Machinery, Inc.(ACM). Permission to
`make digital or hard copies of all of this work for personal or classroom use is granted without
`fee provided that the copies are not made or distributed for profit or commercial advantage
`and that copies bear this notice and the full citation on the first page. Copyrights for compo-
`.nents of this work owned by others than ACM must be honored. Abstracting with credit is
`permitted. To copy otherwise, to republish, to post on servers or to redistribute to lists
`requires prior specific permission and/or a fee. Request permission to republish from: Publi-
`cations Dept. ACM, Inc. Fax +1 (212) 869—0481 or <permissions@acm.org>
`For other copying of articles that carry a code at the bottom of the first or last page, copying
`is permitted provided that the per-copy fee indicated in the code is paid through the Copyright
`Clearance Center, 222 Rosewood Drive, Danvers, MA 01923.
`
`
`
`r
`E—mail: acmhelp@acm.org
`acm_europe@acm.org (in Europe)
`
`ACM Order Number: 429952
`
`Printed iii the U.S.A.
`
`Dropbox Ex. 103
`Page
`
`Dropbox Ex. 1032
`Page 2
`
`

`

`High-Latency, Low-Bandwidth Windowing
`in the Jupiter Collaboration System
`
`David A. Nichols, Pavel Curtis,
`Michael Dixon, and John Lamping
`Xerox PARC
`
`3333 Coyote Hill Rd.
`Palo Alto, CA 94304
`+1415 812 4452
`
`{nichols,pavel,mdixon,1amping} @parc.xerox.com
`
`ABSTRACT
`
`Jupiter is a multi—user, multimedia virtual world intended to
`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.
`
`The state of the Jupiter virtual world, including application
`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 concurrency-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.
`
`The algorithm relies on operation transformations to fix up
`conflicting messages. The best
`transformations are not
`always obvious, though, and several conflicting concerns
`are involved in choosing them. We present our experience
`with choosing transformations for our widget set, which
`
`Permission to make digital/hard copies ofall or part ofthis malerial for
`personal or classroom use is granted without fee provided that the copies
`are not made or distributed for profit or commercial advantage, the copy-
`right notice. the title of the publication and its date appear. and notice is
`given that copyright is by permission ofthe ACM, Inc. To copy otherwise,
`to republish, to post on sewers or to redistribute to lists. requires specific
`permission and/or fee.
`UIST 95 Pittsburgh PA USA
`© 1995 ACM 0—89791-709—x/95/ll..$3.50
`
`includes a text editor, a graphical drawing widget, and a
`number of simpler widgets such as buttons and sliders.
`
`KEYWORDS
`
`UIMS, window toolkits, CSCW, groupware toolkits, opti-
`mistic concurrency control.
`
`1
`
`INTRODUCTION
`
`Jupiter supports long-term collaboration by providing a
`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
`
`0 users can work individually or with other users, by mov-
`ing between (virtual) places,
`
`0 users can organize the materials they are working on and
`the resources they are using by distributing them among
`the places, and
`
`0 other users, materials, and resources can be brought into
`an activity at any time, immediately gaining access to the
`full context of the activity.
`
`In addition, the Jupiter world is intended to be highly cus-
`tomizable by its users, so that they can adapt it to their 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.
`
`One of the key characteristics of Jupiter is that all objects
`there are shared and persistent. This applies to the places
`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. 1032
`Page 3
`
`Dropbox Ex. 1032
`Page 3
`
`

`

`Jupiter, and come back later, the whiteboard will retain the
`drawing that was left on it.
`
`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].
`
`This paper describes the low-level, client/server communi-
`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.
`
`Jupiter user interactions are subject to two sources of signif—
`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-
`lup 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.
`
`The server and client communicate in terms of high-level
`widgets, such as sliders and text editorsl. Both client and
`server keep track of widget state, and communicate high-
`level 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.
`
`The concurrency control algorithms use by groupware sys-
`tems for sharing can be classified as being pessimistic or
`optimistic. Pessimistic algorithms require communication
`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.
`
`Optimistic concurrency control, on the other hand, requires
`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.
`
`Optimistic algorithms are well-suited for high-latency com-
`munications channels since the results of a user’s actions
`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.
`
`Another way of classifying concurrency control algorithms
`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.
`
`The combination of these two choices turned out to simplify
`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.
`
`Instead, Jupiter uses the optimistic protocol only for the
`individual server-client
`links. To the server, each client
`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.
`
`1. We use “client” to refer to the Jupiter client, which is the pro-
`gram that runs on the user’s machine and displays windows on that
`machine’s display. Our “server” runs application programs, which
`make requests of the client and respond to user events reported by
`it. The X window system [25] uses these words in the opposite
`sense; “clients” are applications, and the “server” is the program
`that displays the windows.
`
`A number of groupware systems provide either toolkits for
`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. 1032
`Page 4
`
`Dropbox Ex. 1032
`Page 4
`
`

`

`(VBox
`(HBox
`(Button %help (Text “Help"))
`(Fill)
`(Button °/oquit (Text (FGColor red) “Dismiss”)))
`(Bar)
`(TextEdit %contents (BGColor white)))
`
`Figure 1: An example form for Jupiter. Figure 2
`shows the resulting window.
`
`Help
`
`I' To do‘
`—
`
`Dismiss
`
`1: ap er
`
`— take vacation
`
`and Visual Obliq use a centralized coordinator, while CoEx,
`DistEdit, GroupDesign, GroupKit, the Grove text editor, and
`MMConf are distributed.
`
`Of these, GroupDesign and Grove are the only systems to
`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-
`matics of designing the message transformations required
`by the algorithm.
`
`Jupiter is similar to Visual Obliq in a different way. Both
`systems use techniques from the FormsVBT system for
`Modula-3 [4] and provide tools 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.
`
`Another group of systems deal with low-bandwidth commu-
`nications channels in single-user window systems. These
`systems use two basic approaches to dealing with low-band-
`width: compression and code—shipping.
`
`Compression systems include Xremote, Low-bandwidth X
`(LBX) [13], Higher bandwidth X (HBX) [9, 10], and vari-
`ous commercial programs for providing remote access to
`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.
`
`Jupiter eliminates many round—trips by only sending mes-
`sages for larger-scale widget value updates, not for individ-
`ual
`low-level keyboard and mouse events. However,
`it
`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.
`
`The code-shipping approach is in principle very powerful,
`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.
`
`Figure 2: A window created by the form in Figure 1.
`
`However, code-shipping forces the application designer to
`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.
`
`Again, by trading off some generality, Jupiter is able to hide
`these network problems from the application. The applica-
`tion programmer sees a conventional toolkit interface, and
`the protocols and remote code are handled by the system.
`
`3 THE APPLICATION INTERFACE
`
`Jupiter is built on top of an unmodified instance of the
`LambdaMOO server;
`all of
`the
`server-side
`facilities
`
`described here are written in the M00 programming lan-
`guage [6]. The server contains a database of all the informa-
`tion in the Jupiter environment, as well as
`a MOO
`interpreter. Windowing applications are written by Jupiter’s
`users and run in this server.
`
`The programming interface presented to an application
`writer is very similar to that of the FormsVBT system [1, 4].
`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.
`
`This window consists of a vertical stack of things (VBox),
`the first of which is a horizontal row (HBox) consisting of a
`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. 1032
`Page 5
`
`Dropbox Ex. 1032
`Page 5
`
`

`

`Layout widgets
`
`HBox, VBox
`Fill, Glue, Bar
`
`horizontal or vertical composition
`spacing between widgets
`
`Rim, Border
`Leaf widgets
`Numeric
`
`space around a widget subtree
`
`a slider
`
`StrokeEdit
`
`graphical display and interaction
`
`Text
`TextEdit
`
`TextList
`
`TypeIn
`
`output only
`full text editor
`
`list of text items to choose from
`
`single—line input
`
`append-only with user input
`Typescript
`displays a digital video stream
`VideoPane
`Filter widgets, which decorate a widget subtree
`
`AudioHighlight
`
`Boolean
`
`Button
`
`flashes a border around the subtree
`when a user speaks
`shows a visible on/off value
`
`push once or momentary
`
`Table 1: Widget types available in Jupiter
`
`text “Dismiss” drawn in red. Below this row is a thin black
`
`line (Bar), and a text editor widget named “contents”.
`
`The name on a widget is used by the application to manipu-
`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.
`
`Table 1 shows a list of the widgets supported by Jupiter.
`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 audio/video communications.
`
`Jupiter applications are sharable, with the toolkit automati-
`cally maintaining identical widget values for each partici-
`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
`
`Jupiter’s users run the client on their local workstation. It
`makes a TCP connection to the server, running on a central
`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 Tcl/Tk toolkit
`[18], and for Microsoft Windows, using the native Windows
`programming environment.
`
`The client-server protocol for Jupiter largely parallels the
`programmer’s interface; most calls by applications result in
`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.
`
`When a window is created, the server sends the S-expres-
`sion describing the window to the client, which creates the
`corresponding window.
`
`After the window is created, updates to widget values can
`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.
`
`More complex widgets, such as TextEdits and StrokeEdits,
`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.
`
`Each widget type exports a set of operations to the applica—
`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.
`
`In addition, each widget type supplies a set of event notifica—
`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.
`
`5 THE TWO-WAY SYNCHRONIZATION PROTOCOL
`
`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
`
`the change is immediately applied
`change to a widget,
`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. 1032
`Page 6
`
`Dropbox Ex. 1032
`Page 6
`
`

`

`
`
`Server Operations
`
`create stroke, delete stroke
`
`move stroke
`
`set stroke attributes
`
`set mode
`
`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 creation attributes
`set attributes for strokes cre-
`
`ated by the user
`
`Client Operations
`
`hit down, hit up
`
`sweep down, sweep drag,
`sweep up
`
`report simple mouse hits of
`existing strokes
`
`report strokes hit by a sweep
`operation that potentially
`passes through several
`strokes
`
`create stroke, delete stroke
`reports user-initiated cre-
`
`ations and deletions
`
`Table 2: Operations available on StrokeEdit widgets
`
`client
`
`server
`
`client
`
`3,0
`
`2,0
`
`0.0
`
`0,1
`
`l,\‘
`1,l
`/ \
`2,\
`‘1,2
`
`‘x \ server
`‘
`
`0,2
`
`0,3
`
`3,3
`
`Figure 4: The state space the client and server
`traverse while processing messages. Each node is
`labelled with the number of client and server
`messages processed when in that state. A conflict
`has occurred starting from the state 1,1.
`
`formed on receipt, the client and server wind up with differ-
`ent final values for the widget. Since the client intended to
`delete the “D” in the original string, its message must be
`fixed up to read “delete 3” when the server detects the con-
`flict.
`
`The general tool for handling conflicting messages is a func—
`tion, xform, that maps a pair of messages to the fixed up ver-
`sions. We write
`
`“ABCDE”
`
`del 4
`
`“ABCE”
`
`“ABCDE”
`
`del 2
`
`“ACDE”
`
`xform(c, s) = {c’, s’}
`
`“ACE”
`
`HACDH
`
`Figure 3: An example of an update conflict. The
`client has deleted the fourth character, “D”, while the
`server has deleted the second one, “B”. Without
`concurrency control, the client and server wind up
`with different final values. The fix is to have the
`server transform the client’s message into “del 3" so
`that both client and server get the same result.
`
`will always agree on the widget value when all messages
`have been received and processed.
`
`Unlike other groupware systems, Jupiter does not use the
`synchronization protocol directly between the clients.
`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 two messages for a single
`TextEdit widget that cross. If the messages are not trans-
`
`where c and s are the original client and server messages.
`The messages c ’ and 3’ must have the property that if the cli-
`ent applies c followed by s’, and the server applies 5 fol-
`lowed by c’, then the client and server will wind up in the
`same final state.
`
`Of course, there are many possible functions that have this
`property. For example, the function xform(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:
`xform(del x, del y) =
`{del x-l, del y} ifx > y
`{del x, del y-l} ifx < y
`{no-op, no—op} ifx = y
`
`to
`is, we modify the later index in the document
`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.
`
`it is helpful to picture the
`In describing the full protocol,
`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
`
`1 15
`Dropbox Ex. 1032
`Page 7
`
`Dropbox Ex. 1032
`Page 7
`
`

`

`I“ number of messages generated */
`int myMsgs = 0;
`int otherMsgs = 0;
`/" number of messages received ‘I
`queue outgoing = {};
`
`Generate(op) {
`apply op locally;
`send(op, myMsgs, otherMsgs);
`add (op, myMsgs) to outgoing;
`myMsgs = myMsgs + 1;
`
`} R
`
`eceive(msg) {
`l’ Discard acknowledged messages. “I
`for m in (outgoing) {
`it (m.myMsgs < msg.otherMsgs)
`remove m from outgoing
`
`} l
`
`' ASSERT msg.myMsgs == otherMsgs. '/
`for i in [1..length(outgoing)] {
`/’ Transform new message and the ones in
`the queue. ‘l
`{msg, outgoing[i]} = xform(msg, outgoing[i]);
`
`} a
`
`pply msg.op locally;
`otherMsgs = otherMsgs + 1;
`
`} F
`
`igure 6: The algorithm used by client and server to
`deal with conflicting messages. The pair (myMsgs,
`otherMsgs) corresponds to the state from Figure 4.
`
`client diverge by only one step. we can use the xform func-
`tion directly. If they diverge further, however, the situation
`is more complex. Consider FigureSa. In this case, the client
`has executed c and receives the conflicting message 31 from
`the server. It uses the xform function to compute s] ’ to get to
`the state (1,1). The server then generates message 52 from
`the state (0,1), indicating that
`it still hasn't processed c.
`What should the client do? It can’t use xform(c, 52) because
`6 and s2 were not generated from the same starting state. For
`example, ifc is “del 4,” 5] is “del 1,” and s2 is “del 3,” then
`the correct transform for 52 is “no-op,” but xform(c, 32) is
`“del 3.”
`
`The solution is depicted in Figure 5b. When the client com-
`putes s] ’, 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 (0,1) to
`(1,1). When 52 arrives, the client can use «3' to compute
`
`xform(c’, 52) = {6", 32’}
`
`It executes 32’ to get to the state (1,2). If the server has pro-
`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.
`
`We are now ready to examine the full algorithm, shown in
`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—
`
`clieny
`
`/ \
`'x ‘ server
`1’0 Sly
`0’1~\52
`‘
`\
`\
`0,2
`
`1,1
`
`2,0
`
`2,1
`
`1,2
`
`(a)
`
`2,2
`
`client
`
`0
`KS]
`/ i‘
`1,0
`0 ,1
`
`W \ server
`\
`
`2,0
`
`0,2
`
`1,1
`V3
`1,2
`
`2,1
`
`b(
`
`l
`
`22
`
`Figure 5: In this example, the server generates two
`messages, 51 and 32,
`that conflict with the client
`message 0.
`In order to process 52, the client must
`compute c', even though it will never execute it.
`
`if the client is in the state (2,3), it has generated and pro-
`cessed two messages of its own, and has received and pro-
`cessed three from the server.
`
`As each message is processed, the client or server moves
`down though the state space. If they process messages in the
`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).
`
`The protocol labels each message with the state the sender
`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.
`
`The xform function takes a pair of client and server mes-
`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
`Dropbox Ex. 1032
`Page 8
`
`Dropbox Ex. 1032
`Page 8
`
`

`

`‘ ~ \ server
`
`\
`
`I
`
`l
`
`I
`
`c1ien;/
`
`x,_\'
`
`/I
`
`/
`
`I
`
`I
`
`.r+i‘,y
`/ k _
`x+z.y+1
`
`I
`
`x+k,y
`
`I
`
`I
`
`I
`
`I
`
`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 necessary to get from (x, y)
`to (X+k, y). The next server message must originate
`from some state along this path.
`
`sages, leaving it in the state (x+k, y). These messages are
`kept in the outgoing queue. In the code, myMsgs is x+k, and
`otherMsgs is y.
`
`Sending a message while maintaining this invariant is easy:
`just apply the operation locally to move to (x+k+l, y), trans-
`mit it to the server, and then append the message to the out-
`going message queue.
`
`For reception, we know that the next incoming server mes-
`sage must originate from one of the states between (x, y) and
`(X+k, y) inclusive; that is, the server will have processed
`some arbitrary number of those k client messages. Assume
`that it comes from state (x+i, y), taking the server to (x+i,
`y+l). 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-
`sage that takes us from (X+k, y) to (X+k, y+]), which we
`apply locally. While doing this, save the transformed ver—
`sion