Sync: A Java Framework for Mobile Collaborative Applications

Jonathan P. Munson and Prasun Dewan
Department of Computer Science, University of North Carolina at Chapel Hill

Abstract

Sync is a new Java™-based framework for developing collaborative applications for wireless mobile systems. Sync is based on object-oriented replication and offers high-level synchronization-aware classes based on existing Java classes. Programmers may also extend the Sync-provided classes to create new replicated classes, either to add functionality or to modify a class’s merge policy. Sync supports fully disconnected operation and employs centralized, asynchronous synchronization. Application programmers use the Sync framework to define conflicts and specify conflict resolution on the basis of the application’s structure and semantics.

We discuss the general needs of wireless mobile applications, and present a high-function example application that would be useful to mobile users, to be used for illustration throughout the paper. Next we discuss related work, and evaluate each work relative to its ability to support the example application. We then present the Sync framework, motivating each feature with its use in the example application.

Introduction

Distributed applications for wireless, mobile systems must operate in an environment significantly different than that of distributed applications for local-area networks. In a wireless network, latency is high, bandwidth is low, connections are intermittent, and communication may be charged by the minute or by the byte.

To function well in this environment, wireless applications must use different communication patterns than do LAN-based applications. For instance, an application operating on a LAN that queries a non-local database in response to user input may be able to display the results of the query quickly enough for interactive use. If the same application is operating on a wireless network, the delay in response due to the network may well make the application unsuitable for interactive use. In addition, a user obstructed by a large building may be unable to connect to a database server. For this reason, data replication, whether explicit or implicit (caching), has become an essential element in wireless applications.

Replication alone, however, does not suffice to solve all the problems of wireless computing, especially in the case of multi-user applications. These applications, designed to enable multiple users to share data objects and thus communicate and collaborate with each other, need coordination mechanisms other than the conventional mechanism, locks. Disconnection can either prevent applications from obtaining locks on data objects or prevent them from releasing the locks for long periods of time. Data objects involved include traditional databases as well as recent workgroup applications such as group calendars.

Introducing the factors of wireless mobile systems into application development thus complicates developers’ lives significantly. They must achieve good interactive performance for their applications and solve the coordination problem at the same time.

Frameworks

Application frameworks targeted for wireless mobile systems can considerably simplify application development. Such frameworks should:

To meet these requirements, we have developed Sync. Sync is a Java-based applications framework that provides high-level primitives, in the form of predefined classes, that enable programmers to create arbitrarily complex, synchronized replicated data objects.

Sample Application

Figure 1 shows the user interface for a drawing-centered discussion tool, with which we will illustrate these Sync capabilities. It is used, for example, by people planning a conference who need to discuss the room assignments and layouts. At the top level, the application has two parts: a newsgroup-like discussion forum for general discussion about the events and a set of drawings. The drawing shown is the initial planning for a room containing a small computer network.

Figure 1. Main window of a drawing-based collaborative planning tool.

Figure 2 is the skeleton of the Java program that implements this application. (We show only the data modeling aspects of the application; we omit all method declarations). The application’s data is tree-structured. PlannerApplication, the root, contains the main discussion and the set of drawings. Posting contains a subject and the text of the posting, as well as the replies to the posting, which makes it an arbitrarily deep recursive structure. A Drawing is a title and an ordered set of DrawingObjects.

   public class PlannerApplication
   {
      Vector discussion;  // Vector of Posting objects
      Hashtable drawings; // Hashtable of Drawing objects, title as key
   }
   public class Posting
   {
      String subject;
      String text;
      Vector replies; // Vector of Posting objects
   }
   public class Drawing
   {
      String title;
      Vector objects; // Vector of DrawingObject
   }
   public abstract class DrawingObject
   {
      Rectangle bounds; // x and y coordinates of object
      Color fill_color; // fill color of object
      PenType pen_type; // pen type object drawn in
   }
   public class RectangleObject extends DrawingObject
   {
      ...
   }

Figure 2. Application programmed for single-user operation on local or connected data.

This code shows the application as it would be programmed for single-user operation on local or connected data.

Multi-user, disconnected operation implies that multiple users will independently update local copies of the data. As changes are made, they must be logged, then synchronized with the changes of others upon reconnection. In the absence of specific support for this, the application programmer must handle these merge-time tasks: of collecting or identifying changes made to the data, sending these across the network, merging them with other changes—identifying conflicts in the process—and propagating them to other users.

Toolkits For Multi-User Mobile Applications

Researchers have developed several toolkits to address the problems of mobile applications. These toolkits differ from Sync in the sets of features they offer and the tradeoffs made between flexibility and ease of use.

Lotus Notes

Lotus Notes™ replicates document databases. Documents have record-like structure, the fields of which may contain arbitrary objects, which are opaque to Notes. The programmer declares static templates that define how documents are created and viewed. Users have some flexibility in how synchronization is performed: for example, they may elect not to replicate deletions of their documents. Notes handles conflicts, such as concurrent updates to the same document, by choosing one set of updates for the primary document and creating a response document for the other set of updates.

In the example application, Lotus Notes easily handles the discussion and drawing titles parts of the application but has more trouble with the drawings themselves. Because Notes views are oriented toward forms-based information, our example application would employ another application for the drawing editor. A Notes database could contain the drawing objects, but the objects would be opaque to Notes. Thus any concurrent updates to the same drawing would be considered in conflict, and thus require users to manually merge their changes.

Coda

Coda is a file system that supports disconnected operation by caching files in client workstations. Users have full access to the cached files when disconnected, during which time Coda records file updates in a log. Upon reconnection to one of multiple servers, Coda merges the updates in the compressed log with the master file updates received during the client’s disconnection, a process called reintegration. Coda-aware applications may supply procedures to resolve conflicts detected during the merge. A technique called trickle reintegration allows reintegration to be performed as a background process when clients are connected over low-bandwidth channels. By replicating at the file level, Coda can transparently support preexisting file-based applications.

Programming the example application for Coda would be cumbersome: All runtime objects for which separate conflict detection is desired would need file representations as well. Coda performs conflict detection on an update-by-update basis, and thus if any updates are lost due to conflict, inconsistency may result unless all updates are independent of each other.

Bayou

Bayou is a toolkit focused specifically on wireless mobile applications. A Bayou application’s code and data are replicated at multiple clients and multiple servers. The servers provide synchronization services to the clients, and then synchronize among themselves. A client can synchronize with any server; updates propagate from one server to another until they reach a designated primary server, at which time they become committed. Application developers may write conflict resolution procedures to resolve conflicts such as writes to the same database record. These procedures allow users to specify alternative updates in case primary updates conflict. Developers may also supply functions to detect conflicts specific to a particular application.

Like Code, Bayou also processes updates one by one, but its conflict detection language allows it to detect conflicts between an update and a set of concurrent updates. Unlike the object model, its tuple-store data model is not naturally suited to representing the hierarchically structured example application.

Rover

Rover offers two programming abstractions designed to address the problems of network disconnection and slow communications. Relocatable Dynamic Objects encapsulate the application’s code and data. Initially resident on an application’s home server, they may be imported to reside in the remote client’s physical memory, and updated locally. When exported, the logged updates are applied to the replica at the home server. Type-specific, programmer-supplied procedures resolve detected conflicts. Queued Remote Procedure Calls allow clients to make non-blocking RPCs even when the client is disconnected. Requests are queued until reconnection, whereupon they are delivered to the server, and the responses returned to the client.

Because it is based on arbitrary objects, Rover has no trouble with the data-modeling aspects of the example application. As with Coda and Bayou, conflicts are handled one-by-one, and all of one client's queued updates must be independent of each other to avoid inconsistency in case one of them is nullified.

Summary

In Lotus Notes we see one approach to coordination in mobile applications, and in Bayou, Coda, and Rover we see another. The Notes approach is to provide structure-based automatic merging, with predefined conflict resolution. The benefit of this approach is ease of programming; the drawback is that the predefined conflict resolution restricts the range of application semantics that can be accommodated. The Bayou, Coda, and Rover approach is to provide conflict detection at the atomic data object level, giving programmers the entire responsibility of specifying conflict resolution. The benefit of this approach is flexibility, but the drawback is a greater burden on the programmer. In Sync we have tried to gain the benefits of both approaches, offering collection classes with predefined merge behavior, yet allowing programmers to extensively customize the behavior in the high-level language of the merge matrix.

Table 1 summarizes Sync and the systems above with respect to four key characteristics.

Table 1. Dimensions of mobile application toolkits.

System Replicated object Replication topology Conflict definition Conflict resolution
Bayou Tuple store Peer-to-peer Application-supplied queries on tuple store Application-supplied, per-write conflict resolution procedures
Coda File, directory Hub-and-spoke, single logical hub, multiple physical servers Same-file or same-directory update Fixed procedure for directories, application-supplied procedures for files
Lotus Notes Document store Hub-and-spoke, peer-to-peer, or tree topologies Same-document update Later-received update kept as version of first-received update
Rover Arbitrary object Hub-and-spoke, single physical "home" server for each object Method invocation on same object Application-supplied conflict resolution procedures
Sync Arbitrary object constructed of Sync classes (sequence, record, dictionary, atomic) Hub-and-spoke, single physical server for each application Operation on same element in collection or method invocation on same object; optional atomic commit. Defined by class-specific merge matrix. Entries may be defined by programmer and overridden by users.

 

The Sync Applications Framework

Sync comprises five distinct models: its basic system model, its programming model, its change model, its synchronization model, and its support for atomic commit of multiple changes.

Basic architecture

Sync applications are divided into a client side and a server side, as shown in Figure 3. The client side consists of the user interface and the application’s code and data (encapsulated as an object); this side handles all user interactions. The client side is replicated persistently at each mobile site and is a remote client to the synchronization server, where the server side of the application executes. The server side consists of an application object replica and, optionally, an interface to external resources. Accessing external resources may be to retrieve legacy data from databases, or to archive data to a file system. Additionally, the server side is responsible for operations with once-only semantics, such as triggering a software system rebuild or sending and receiving electronic mail. The synchronization server as a whole acts as a central, high-availability resource through which remote clients asynchronously share updates with each other, and from which the current state of the application object is always available for new clients.

Figure 3. Sync basic system model

Programming model

Programmers define the replicated object using Sync replicated classes or subclasses derived from them. Sync replicated classes, listed in Table 2, are based on existing non-replicated Java classes. Rather than require programmers to define the merge behavior of each class they create, as is the Rover approach, Sync takes a constructor-based approach. Developers create their classes using a small set of predefined Sync classes as constructors, much as types are created in Pascal using the RECORD and ARRAY constructors. Sync provides the classes ReplicatedRecord, ReplicatedSequence, and ReplicatedDictionary, as well as replicated versions of the Java basic types.

Sync class Purpose
Replicated Abstract class inherited by all replicated classes
ReplicatedRecord For programmer-defined class with replicated fields (abstract class)
ReplicatedAtomic For programmer-defined class without replicated fields
ReplicatedSequence Implements subset of java.util.Vector
ReplicatedDictionary Implements java.util.Dictionary (also implemented by java.util.Hashtable)
ReplicatedInteger Same interface as Integer with addition of setValue(int) method
ReplicatedFloat Same interface as Float with addition of setValue(float) method
ReplicatedString Same interface as String with addition of setValue(String) method
ReplicatedBoolean Same interface as Boolean with addition of setValue(boolean) method

Table 2. Sync replicated classes

To illustrate use of the Sync classes, we repeat the code for the PlannerApplication example as it would be declared as a Sync replicated object.

   public class PlannerApplication extends ReplicatedRecord
   {
      ReplicatedSequence discussion; // Sequence of Postings
      ReplicatedDictionary drawings; // Dictionary of Drawings
   }
   public class Posting extends ReplicatedRecord
   {
      ReplicatedString subject;
      ReplicatedString text;
      ReplicatedSequence replies; // Sequence of Postings
   }
   public class Drawing extends ReplicatedRecord
   {
      ReplicatedString title;
      ReplicatedSequence objects; // Sequence of DrawingObjects
   }
   public abstract class DrawingObject extends ReplicatedRecord
   {
      Rectangle position; // Position is ReplicatedAtomic subclass
      Color fill_color; // Color and PenType are subclasses of
      PenType pen_type; // ReplicatedInteger
   }

Figure 4. Application programmed as a Sync replicated object.

By defining the application’s data through Sync replicated classes, used directly or derived, programmers effectively expose the structure of their data to the Sync replication and synchronization system. Sync can thus offer automatic, fine-grained change detection and merging. This is the same approach taken by Lotus Notes, except that Sync offers more kinds of collections and allows these collections to be composed into arbitrarily complex structures. This is in contrast to the approach taken by Coda, Bayou, and Rover, which do not expose an application’s structures to the replication system, defining conflict detection and resolution at the atomic data object level. Hence the burden of specifying conflict detection and resolution is fully the responsibility of the programmer. We discuss Sync’s conflict resolution mechanism in the section "Merge model."

At the client side of the application, Sync adopts a version of the Model-View-Controller paradigm. The user interface, supplied by the programmer, implements Java’s Observer interface, and the replicated object extends Java’s Observable class (through Sync’s Replicated class). For the server side of their application, developers may provide a class that implements the SyncServerApplication interface, which allows the application to respond to synchronization notifications from Sync. Programmers have other options through the Java event notification mechanism; we do not discuss these here.

Change model

Sync’s change model specifies how objects represent the way in which they have changed between synchronizations. Its primary features are

The change model is formally defined with a context-free grammar, but we will illustrate it here through a plain-language example. Suppose one of the conference organizers using the example application made the following changes to the drawing shown in Figure 1:

  1. changed the fill color of the rectangle marked "Temporary wall here";
  2. added an arrow to the drawing to better identify the wall rectangle as a wall and not a table;
  3. added a comment to the discussion as a reply to someone else’s comment that mistook the wall for a table.

These changes would be reported using (approximately) the syntax shown in Figure 5.

Figure 5. Example change set.

Note that the change syntax directly reflects the structure of the application’s object. This hierarchical syntax for reporting changes adds overhead for changes made deep within an object, but has the advantage over the conventional linear scheme of allowing application developers the flexibility of defining conflict at whatever structural level of the application is appropriate. For the class DrawingObject of the example application, the developer may deem that concurrent changes to two different fields (e.g., position and fill_color) conflict, but that changes to the two fields in the class Drawing (title and drawing) do not conflict.

As shown in Figure 5, changes are reported to the granularity of the basic types. This reduces the amount of data transmitted in the synchronization request to an amount proportional to the amount of data changed in the application, and so both speeds communications and, perhaps more importantly, reduces the network charges when communication is charged by the byte.

Synchronization model

The task of the central synchronization server is to accept synchronization requests from remote replicas, collect all changes received by the server since the remote replica’s last synchronization, and merge them with the replica’s changes included in the replica’s synchronization request. Of the merged set of changes, those originating from the replica are applied to the server’s replica, and those originating from the server are sent to the remote replica.

For this, the first version of Sync, we regard an update as committed when it reaches the server. This fixed policy for resolving conflicts denies applications some flexibility, such as allowing remote clients to query users for conflict resolution, but has the benefits of requiring less memory, converging more rapidly, and—the primary one for our present purposes—being simpler to implement. We are investigating policies and mechanisms that allow the server to defer conflict resolution.

Merge model

Sync’s merge model describes how two sets of changes to an object are merged and their conflicts resolved. We have adapted the Suite merge model described in , but have made several changes. First, due to our focus on mobile applications, Sync does not support interactive, user-to-user merging, as does Suite. Due to network latency, interactive operation between users linked over a wireless network is unlikely to be unsatisfactory, and the difficulty of bringing two mobile users together in time is also a problem. Second, by abandoning synchronous merging in favor of asynchronous merging, Sync can support any number of users, whereas Suite is limited to two. Third, by adopting an object-oriented language as a base, Sync can support user-defined classes. Last, Sync offers an additional constructor class, the ReplicatedDictionary.

At the core of the Suite and Sync merge models is a construct called the merge matrix. The merge matrix is class-specific and for each class consists of rows and columns labeled by the operations for that class. In Sync, rows represent the operations of the remote client, and columns represent the operations already committed at the server. The merge matrix entry identified by a particular row operation and column operation determines the action the merge procedure will take—typically accepting one operation or the other, or both. Merge matrices are defined for all of the replicated classes of Table 2. We describe the general merge matrix using the Dictionary merge matrix for illustration.

A Dictionary merge matrix (Figure 6) has rows and columns for Add, Remove, and Modify operations, parameterized by key. If two users have concurrently submitted operations with the same key parameter, the merge matrix determines the result. Operations with different keys are assumed not to conflict. The "null" label signifies that the row or column user did not submit an operation with the key parameter. The "S:x, C:y" notation means that the merge procedure will return operation x to be applied to the server replica, and operation y to be applied to the client replica. For example, Figure 6 specifies that if the remote client removed the element associated with key and the server added a new element with that same key, the server’s operation prevails and the new element is kept. The server-Modify/client-Remove entry shows the server’s Modify operation being transformed to a Put operation to be applied at the client. It is necessary to transform the operation because at the client the modified element is no longer in the dictionary. When a client’s changes are overridden like this, the client receives notification in the reply to its synchronization request. It may then notify the user, or reapply the changes and synchronize again. This time the changes are likely to be accepted, since client changes are merged against only those changes the client has not already seen. Sync provides default merge matrix settings, but programmers may choose the merge behavior they desire by overriding the default settings as described below.

  Server operation (os)
Remote operation (oc) Put(key) Remove(key) Modify(key) Null
Put(key) S:Ø, C:os S:oc, C:Ø S:Ø, C:os S:oc, C:Ø
Remove(key) S:Ø, C:os S:Ø, C:Ø S:Ø, C:Put(key) S:oc, C:Ø
Modify(key) S:Ø, C:os S:Ø, C:os merge(os, oc) S:oc, C:Ø
Null S:Ø, C:os S:Ø, C:os S:Ø, C:os  

Figure 6. ReplicatedDictionary merge matrix.

If both users modified the same element, the merge procedure will by default attempt to merge the changes at the level of the Dictionary element. In our example application, this situation may occur when two users have changed the same drawing, but perhaps in non-conflicting ways. Both sets of changes would appear as a change to the same element of the Dictionary, but in the hope that the changes can be merged, the Dictionary merge matrix defers resolution to the lower-level object—in this case, a Drawing. This is the meaning of the "merge" entry in merge matrices. We walk through the procedure below.

The merge procedure follows the tree structure of the change sets. At each level of the object hierarchy, the procedure pairs corresponding changes—changes to the same field of a record, or the same element of a sequence or dictionary—from the two change sets and consults the merge matrix for their resolution. If the elements are themselves replicated collections, and the Modify/Modify entry in the merge matrix specifies "merge," the merge procedure will call itself recursively with the change sets to the element. We illustrate the merge procedure using the single example change set from above. The merge procedure will begin with the changes to the top-level object, which at this level appear as {Modify(discussion), Modify(drawings)}. Suppose another user had modified a drawing; this will be represented as a Modify(drawings) change, and the merge procedure will call itself, trying to merge the two sets of changes to the drawings field. Now at the dictionary level, the merge procedure will determine if there are changes to the same element (i.e., a drawing). If so, the merge procedure will again call itself with the change sets to that element, and so will merge at the sequence level (a drawing is a sequence of drawing objects). This recursion will continue until we reach atomic objects such as integers, or objects that the programmer has declared atomic for merge purposes, or until the Modify/Modify merge matrix entry does not specify recursive merge. By setting an object’s SyncConflictHandling parameter, inherited from Replicated, to Merge.Atomic, the programmer instructs the merge procedure to treat the object as atomic, yet allows fine-grained change reporting.

Merge matrices are implemented in Sync as two-dimensional arrays of objects that implement a Sync-defined MergeAction interface. Sync populates merge matrices with default actions, but these may be replaced at runtime through the setMergeMatrixEntry method, defined for all merge matrices. Programmers may also supply their own merge action, to implement an application-specific action. For example, the default behavior for a ReplicatedDictionary object in the case where two users have made an addition with the same key is to reject the addition submitted (Figure 6, Put/Put entry). The programmer may wish a more Lotus Notes-like behavior and keep the addition, but under a different key. This could be done with an action that generates an alternate key.

Extending Sync replicated classes

Programmers who find either that Sync replicated classes do not meet their needs or that specifying merge behavior through modifying merge matrix entries is not sufficient may define classes in Sync. They can do so in two ways.

Sync also supports atomic commit of multiple changes. Careful merge matrix definition and designation of certain objects as atomic can satisfy many of an application’s consistency requirements. But there are situations when structural inclusion is too weak a relation between changes, and hence designating the entire structure as atomic is too restrictive. Consider the set of three changes in the meeting room layout example above. If one change is denied due to a conflict with an earlier committed change, the other changes become inconsistent. The only object that contains all the changes is the top-level object of the application. It is inconvenient to mark the entire application as Atomic, yet we want all these updates to commit or none, which is the atomic commit property of transactions.

To address this, Sync lets developers mark a change set as a transaction. Multi-transaction change sets and a non-transaction change set may be sent in one synchronization. If the merge process uncovers a conflict between a change in a transaction change set and an already committed change, Sync nullifies the entire transaction and notifies the client. So in the meeting room example (assuming all three changes are marked as part of the same transaction), if another user had earlier committed a change to the the wall (e.g., moved it slightly), Sync would reject the fill color change, then nullify the additions of the arrow to the drawing and the reply to the discussion.

Conclusions and Future Work

Sync recognizes the need for rich data modeling primitives and flexible but easy-to-specify conflict definition and resolution. Sync offers high-level Java classes with which programmers may construct arbitrarily complex objects. It employs centralized, asynchronous synchronization, allows flexible merge policy specification, and supports atomic commit of multiple changes. Its architecture accommodates the need to access external resources such as databases. We motivated our work through an example application and evaluated it with respect to other related frameworks for mobile/collaborative systems.

We would now like to explore how to support collaboration where some users are disconnected and using the mechanisms described here to maintain consistency, and some are connected and using stronger mechanisms such as locking. A second issue is how partial replication and the intersection of different replica sets affects consistency guarantees. Third, we would like to integrate other replication topologies, such as offered by Lotus Notes and Bayou, with our own change model. Last, we would like to be able to utilize one-way communication services, as Rover does, to support a form of Coda’s trickle reintegration. In conjunction with all these efforts will be the development of a wide variety of applications, which will undoubtedly lead to new requirements.

Acknowledgments

This work was supported by an IBM Cooperative Fellowship, National Science Foundation grants IRI-9627619 and IRI-9408708, and DARPA/ONR grant N 66001-96-C-8507. Special thanks to Iva Anderson and his Technology and Mobility Projects department in IBM’s Software Solutions Division for their resources and support.

References

  1. L. Kalwell, S. Beckhardt, T. Halvorsen, R. Ozzie, and I. Greif, "Replicated document management in a group communication system," in Groupware: Software for Computer-Supported Cooperative Work, D. Marca and G. Bock, Editors. 1992, IEEE Computer Society Press. p. 226–235.
  2. J. J. Kistler and M. Satyanarayanan, "Disconnected operation in the Coda file system," ACM Transactions on Computer Systems, Vol. 10, No. 1 (February 1992), 1992, pp. 3–25.
  3. L.B. Mummert, M.R. Ebling, and M. Satyanarayanan, "Exploiting weak connectivity for mobile file access," Operating Systems Review, Vol. 29, No. 4, 1995, pp. 143–155.
  4. D.B. Terry, M.M. Theimer, K. Petersen, A.J. Demers, Mike J. Spreitzer, Carl H. Hauser, "Managing update conflicts in Bayou, a weakly connected replicated storage system," Operating Systems Review, Vol. 29, No. 5, 1995, pp. 172–83.
  5. A.D. Joseph, A.F. deLespinasse, J.A. Tauber, D.K. Gifford, and M.F. Kaashoek, "Rover: a toolkit for mobile information access," Operating Systems Review, Vol. 29, No. 5, 1995, pp. 156–71.
  6. J.P. Munson and P. Dewan, "A flexible object merging framework," Proc. ACM Conference on Computer Supported Cooperative Work, 1994, pp. 231–242.