IEEE TRANSACTIONS ON COMPUTERS, VOL. 46, NO. 3, MARCH 1997
`
`337
`
`Mobile Computing with the Rover Toolkit
`
`Anthony D. Joseph, Student Member, IEEE, Joshua A. Tauber, Student Member, IEEE
`and M. Frans Kaashoek, Member, IEEE
`
`Abstract—Rover is a software toolkit that supports the construction of both mobile-transparent and mobile-aware applications. The
`mobile-transparent approach aims to enable existing applications to run in a mobile environment without alteration. This
`transparency is achieved by developing proxies for system services that hide the mobile characteristics of the environment from
`applications. However, to excel, applications operating in the harsh conditions of a mobile environment must often be aware of and
`actively adapt to those conditions. Using the programming and communication abstractions present in the Rover toolkit, applications
`obtain increased availability, concurrency, resource allocation efficiency, fault tolerance, consistency, and adaptation. Experimental
`evaluation of a suite of mobile applications demonstrates that use of the toolkit requires relatively little programming overhead,
`allows correct operation, substantially increases interactive performance, and dramatically reduces network utilization.
`
`Index Terms—Mobile computing, distributed objects, mobile code, wireless networks, software libraries, distributed systems,
`replication, caching, operating systems, remote procedure call.
`
`—————————— F ——————————
`
`M
`
`1 INTRODUCTION
`OBILE computing environments present application
`designers with a unique set of communication and
`data integrity constraints that are absent in traditional dis-
`tributed computing settings. For example, although mobile
`communication infrastructures are becoming more com-
`mon, network bandwidth in mobile environments is often
`severely limited, unavailable, or expensive. Therefore, sys-
`tem facilities in mobile computing environments should
`minimize dependence upon continuous network connec-
`tivity, provide tools to optimize the utilization of available
`network bandwidth, minimize dependence on data stored
`on remote servers, and allow dynamic division of work
`between clients and servers. In this paper, we describe the
`Rover toolkit, a set of software tools that supports applica-
`tions that operate obliviously to the underlying environ-
`ment, while also enabling the construction of applications
`that use awareness of the mobile environment to adapt to
`its limitations. We illustrate the effectiveness of the toolkit
`using a number of distributed applications, each of which
`runs well over networks that differ by three orders of mag-
`nitude in bandwidth and latency.
`
`1.1 Mobile versus Stationary Environment
`Designers of applications for mobile environments must
`address several differences between the mobile environ-
`ment and the stationary environment. Issues that represent
`minor inconveniences in stationary distributed systems are
`significant problems for mobile computers. This distinction
`requires a rethinking of the classical distributed systems
`techniques normally used in stationary environments.
`Computers in a stationary environment are usually very
`reliable. Relative to their stationary counterparts, mobile
`
`————————————————
`• The authors are with the Laboratory for Computer Science, Massachusetts
`Institute of Technology, Cambridge, MA 02139.
` E-mail: {adj, josh, kaashoek}@lcs.mit.edu.
`For information on obtaining reprints of this article, please send e-mail to:
`transcom@computer.org, and reference IEEECS Log Number C97027.
`
`computers are quite fragile: A mobile computer may run
`out of battery power, be damaged in a fall, be lost, or be
`stolen. As pointed out by the designers of Coda, given these
`threats, primary ownership of data should reside with sta-
`tionary computers rather than with mobile computers [1].
`Furthermore, application designers should take special pre-
`cautions to enhance the resilience of the data stored on mo-
`bile computers.
`Relative to most stationary computers, a mobile com-
`puter often has fewer computational resources available. In
`addition, the available resources may change dynamically
`(e.g., a “docked” mobile computer has access to a larger
`display, auxiliary graphics or math coprocessors, additional
`stable storage, unlimited power, etc.).
`A stationary environment can distribute an application’s
`components and rely upon the use of high-bandwidth, low-
`latency networks to provide good interactive application
`performance. Mobile computers operate primarily in a lim-
`ited bandwidth, high-latency, and intermittently connected
`environment; nevertheless, users want the same degree of
`responsiveness and performance as in a fully connected
`environment.
`Network partitions are an infrequent occurrence in sta-
`tionary networks, and most applications consider them to
`be failures that are exposed to users. In the mobile envi-
`ronment, applications will face frequent, lengthy network
`partitions. Some of these partitions will be involuntary (e.g.,
`due to a lack of network coverage), while others will be
`voluntary (e.g., due to a high dollar cost). Mobile applica-
`tions should handle such partitions gracefully and as trans-
`parently as possible. In addition, users should be able, as
`far as possible, to continue working as if the network was
`still available. In particular, users should be able to modify
`local copies of global data.
`When users modify local copies of global data, consis-
`tency becomes an issue. In a mobile environment, optimis-
`tic concurrency control [2] is useful because pessimistic
`methods are inappropriate (a disconnected user cannot ac-
`
`0018-9340/97/$10.00 © 1997 IEEE
`
`Petitioners Great West Casualty Co., BITCO Gen. Ins. Corp., and BITCO Nat'l Ins. Co.
`Ex. 1027, p. 1
`
`

`
`338
`
`IEEE TRANSACTIONS ON COMPUTERS, VOL. 46, NO. 3, MARCH 1997
`
`quire or release locks), as pointed out by the designers of
`Coda [1]. However, using an optimistic approach does in-
`volve some difficulties. In particular, long duration parti-
`tions will cause a greater incidence of apparent write-write
`conflicts than in stationary environments. It is therefore
`important to use application-specific semantic information
`to detect when such conflicts are false positives and can be
`avoided.
`
`1.2 The Argument for Mobile-Aware Computing
`The attributes of the typical stationary environment have
`guided the development of classical distributed computing
`techniques for building client-server applications. These
`applications are usually unaware of the actual state of the
`environment; therefore, they make certain implicit as-
`sumptions about the location and availability of resources.
`Such mobile-transparent applications can be used unmodi-
`fied in mobile environments by having the system shield or
`hide the differences between the stationary and mobile en-
`vironments from applications. Coda [1] and Little Work [3]
`use this approach in providing a file system interface to
`applications. These systems consist of a local proxy for some
`service (the file system) running on the mobile host and
`providing the standard service interface to the application,
`while attempting to mitigate any adverse effects of the mo-
`bile environment. The proxy on the mobile host cooperates
`with a remote server running on a well-connected, station-
`ary host.
`This mobile-transparent approach simplifies mobile ap-
`plications, but sacrifices functionality and performance.
`Although the system hides mobility issues from the appli-
`cation, it usually requires manual intervention by the user
`(i.e., having the user indicate which data to prefetch onto the
`user’s computer). Similarly, conflict resolution is complicated
`because the interface between the application and its data
`was designed for a stationary environment. Consider an ap-
`plication writing records into a file shared among stationary
`and mobile hosts. While disconnected, the application on the
`mobile host inserts a new record. The local file system proxy
`records the write in a log. Meanwhile, an application on a
`stationary host alters another record in the same file. Upon
`reconnection, the file system can detect that conflicting up-
`dates have occurred: One file contains a record that does not
`appear in the other file and one file contains a record that
`differs from the same record in the other file. Depending
`upon how records are named, it may not be possible to dis-
`tinguish between the instance where the same record is
`modified in one file and not the other and the instance where
`a record is deleted and a new one is added. Thus, the file
`system alone cannot resolve the conflict.
`The cause of this ambiguity is that these systems change
`the contract between the application and the file system in
`order to hide the condition of the underlying network. The
`read/write interface no longer applies to a single file, but to
`possibly inconsistent replicas of the file. Therefore, any ap-
`plications that depend on the semantics of the standard
`read/write interface for synchronization and ordering may
`fail.
`Coda recognizes this limitation in conflict resolution and
`provides support for application-specific resolvers (ASRs) [4],
`
`programs that are invoked based on the file name extension
`to resolve conflicts during synchronization. However, ASRs
`alone are insufficient, because the only information pro-
`vided to an ASR is the two conflicting files, not the two op-
`erations and contexts that led to the differing results. An
`application has no way of knowing that the file system
`contract has been changed by Coda, and, therefore, no way
`to save the additional information the ASR would need to
`resolve the conflict. Thus, in the above example, there is no
`way for an ASR to use the file system interface to determine
`whether the mobile host inserted a new record or the sta-
`tionary host deleted an old one.
`So, although the mobile-transparent approach is ap-
`pealing in that it offers to run existing applications without
`alteration, it is fundamentally limited in that it hides the
`information needed to allow applications to remain correct
`and to perform well in an intermittently connected envi-
`ronment. The alternative to hiding environmental informa-
`tion from applications is to expose information and involve
`applications and users in decision making. This alternative
`yields the class of mobile-aware applications.
`In the above case, a mobile-aware application can store
`not only the value of a write, but also the operation associated
`with the write. That operation can include any relevant con-
`text. Storing the operation allows the application to use ap-
`plication-specific semantic and contextual information; for
`example, it allows for “on-the-fly” dynamic construction of
`conflict avoidance and conflict resolution procedures.
`The mobile-aware argument can be viewed as applying
`the end-to-end argument (“Communication functionality
`can be implemented only with the knowledge and help of
`the application standing at the endpoints of the communi-
`cations system.” [5]) to mobile applications. The file system
`example described above illustrates that some applications
`need to be aware of intermittent network connectivity to
`achieve consistency. Similar examples exist for perform-
`ance, reliability, low-power operation, etc.
`The mobile-aware argument does not require that every
`application use its own, ad hoc approach to mobile com-
`puting. Rather, it allows the underlying communication
`and programming systems to define an application pro-
`gramming interface that optimizes common cases and sup-
`ports the transfer of appropriate information between the
`layers. Since mobile-aware applications share common de-
`sign goals, they can share design features and techniques.
`The Rover toolkit provides such a mobile-aware application
`programming interface that, unlike previous systems, is
`designed to support both mobile-aware and mobile-
`transparent approaches.
`
`1.3 Rover: The Toolkit Approach
`The Rover toolkit offers applications a distributed object
`system based on a client/server architecture with client
`caching and optimistic concurrency control [6] (see Fig. 1).
`Clients are Rover applications that typically run on mobile
`hosts, but could run on stationary hosts as well. Servers,
`which may be replicated, typically run on stationary hosts
`and hold the long-term state of the system.
`The toolkit provides mobile communication support
`based on two ideas: relocatable dynamic objects (RDOs) and
`
`Petitioners Great West Casualty Co., BITCO Gen. Ins. Corp., and BITCO Nat'l Ins. Co.
`Ex. 1027, p. 2
`
`

`
`JOSEPH ET AL.: MOBILE COMPUTING WITH THE ROVER TOOLKIT
`
`339
`
`Fig. 1. Rover offers applications a client/server distributed object system with client caching and optimistic concurrency control. This figure shows
`the control flow within the toolkit.
`
`queued remote procedure call (QRPC). A relocatable dynamic
`object is an object (code and data) with a well-defined inter-
`face that can be dynamically loaded into a client computer
`from a server computer, or vice versa, to reduce client-
`server communication requirements. Queued remote pro-
`cedure call is a communication system that permits appli-
`cations to continue to make nonblocking remote procedure
`calls [7] even when a host is disconnected—requests and
`responses are exchanged upon network reconnection.
`Rover applications employ an optimistic, primary-copy,
`tentative-update, distributed object model of data sharing:
`They call into the Rover library to import RDOs and to ex-
`port logs of operations that mutate RDOs. Client-side appli-
`cations invoke operations directly on locally cached RDOs.
`Server-side applications are responsible for resolving con-
`flicts and notifying clients of resolutions. A network sched-
`uler (operating above the operating system level) drains the
`stable QRPC log, which contains the RPCs that must still be
`performed at the server. Where possible, in addition to
`opening and closing network connections, the network
`scheduler also interacts with the operating system to initiate
`or terminate connection-based transport links (e.g., dial-up)
`or to power-up/power-down wireless transmitters.
`Servers can run either at stationary hosts or at mobile
`hosts. Running servers at mobile hosts is useful when
`forming “mobile workgroups,” where a group of clients
`isolated from other hosts can interact with local servers.
`However, for two reasons, we mostly use stationary hosts:
`First, an operation cannot be committed (i.e., it is tentative)
`until it reaches and is accepted by a server; second, a
`server’s copy of an object is the canonical version of the
`object. Thus, clients can ascertain the latest value for an ob-
`ject only by contacting the server that owns the object. Both
`commit and import operations require well-connected
`servers. If servers are on poorly connected mobile hosts,
`clients outside of the workgroup may encounter delays in
`committing operations or importing objects.
`The key task of the programmer when building a mo-
`bile-aware application with Rover is to define RDOs for the
`data types manipulated by the application and for data
`transported between clients and servers. The programmer
`then divides the program into portions that run on the cli-
`
`ent and portions that run on the server; these parts com-
`municate by means of QRPC. The programmer then defines
`methods that update objects, including code for conflict
`detection, avoidance, and resolution.
`To use the Rover toolkit, a programmer links the mod-
`ules that compose the client and server portions of an ap-
`plication with the Rover toolkit. The application can then
`actively cooperate with the runtime system to import objects
`onto the local machine, invoke well-defined methods on
`those objects, export logs of method invocations on those
`objects to servers, and reconcile the client’s copies of the ob-
`jects with the server’s.
`
`1.4 Main Results
`This paper extends previous work on the Rover architecture
`[6], [8] by providing a more detailed discussion of the design
`and implementation of queued RPC and relocatable dynamic
`objects, including compressed and batched QRPCs; present-
`ing in greater depth the argument for making applications
`mobile-aware; and explaining how applications use that
`awareness and the Rover toolkit to mitigate the effects of in-
`termittent communication on application performance. We
`draw four main conclusions from our experimental data and
`experience developing Rover:
`1) QRPC is well suited to intermittently connected envi-
`ronments. Queuing enables RPCs to be scheduled,
`batched, and compressed for increased network per-
`formance. QRPC performance is acceptable in the tar-
`get environment even if every RPC is stored in stable
`logs at clients and servers. For lower bandwidth net-
`works, the overhead of writing the logs is dwarfed by
`the underlying communication costs.
`2) Use of RDOs allows mobile-aware applications to mi-
`grate functionality dynamically to either side of a
`slow network connection and thereby minimize reli-
`ance on network connectivity. Caching RDOs reduces
`latency and bandwidth consumption. User interface
`functionality can run at full speed on a mobile host,
`while large data manipulations can be performed on
`the well-connected server.
`3) Porting applications to Rover and making them mo-
`bile-aware generally requires relatively little change
`
`Petitioners Great West Casualty Co., BITCO Gen. Ins. Corp., and BITCO Nat'l Ins. Co.
`Ex. 1027, p. 3
`
`

`
`340
`
`IEEE TRANSACTIONS ON COMPUTERS, VOL. 46, NO. 3, MARCH 1997
`
`to the original application. In addition, building
`Rover proxies is easy and has allowed the use of ap-
`plications (e.g., Netscape and USENET browsers)
`without modification. We have implemented several
`mobile-aware applications (Rover Exmh, Webcal) by
`modifying conventional instances of the same appli-
`cations. We have built others from scratch (Irolo,
`Stock Market Watcher). Most were made mobile-
`aware with a few simple changes (to approximately
`10% of the original code and with as little as three
`weeks of work). Only one of the applications required
`more than a month of work. In part, the extra time
`was due to additional evolution and redesign of the
`toolkit.
`4) Measurements of end-to-end mobile application per-
`formance show
`that, by using Rover, mobile-
`transparent and mobile-aware applications perform
`significantly better on slow networks than their origi-
`nal versions. For example, when performing routine
`Web browsing using Netscape with the mobile-
`transparent Rover HTTP proxy, we observe perform-
`ance improvements of up to 17% over Netscape alone.
`When using mobile-aware applications running over
`slow networks to perform routine tasks, we observe
`performance improvements of up to a factor of 7.5
`over the original versions.
`5) We also observe significant improvements in the per-
`formance of the user interfaces of client/server-based
`mobile-aware applications in comparison to those of
`conventional applications used remotely across slow
`networks. Without Rover, scrolling and refreshing
`operations are extremely slow and pressing buttons
`and selecting text are unpleasant because of the lag
`between mouse clicks and display updates. With
`Rover, the user sees excellent GUI performance across
`a range of networks that varies by three orders of
`magnitude in both bandwidth and latency.
`
`2 RELATED WORK
`The need for mobile-aware applications and complemen-
`tary system services to expose mobility to applications was
`identified concurrently by several groups. Katz noted the
`need for adaptation of mobile systems to a variety of net-
`working environments [9]. Davies et al. cited the need for
`protocols to provide feedback about the network to appli-
`cations in a vertically integrated application environment
`[10]. Kaashoek et al. created a Web browser that exposed
`the mobile environment to code implementing mobile-
`aware Web pages [11]. The Bayou project proposed and
`implemented an architecture for mobile-aware databases
`[12]. Baker identified the dichotomy between mobile-
`awareness and mobile-transparency in general application
`and system design [13]. However, Rover is the first imple-
`mented general application-architecture to support both
`mobile-transparent system service proxies and mobile-
`aware applications.
`Several previous projects have studied building mobile-
`transparent services for mobile clients. The Coda project
`pioneered distributed services for mobile clients. In par-
`
`ticular, it investigated how to build a mobile-transparent
`file system proxy for mobile computers by using optimistic
`concurrency control and prefetching [1]. Coda logs all up-
`dates to the file system during disconnection and replays
`the log on reconnection; automatic conflict resolution
`mechanisms are provided for directories and files, using
`Unix file naming semantics to invoke ASRs at the file sys-
`tem level [4]. A manual repair tool is provided for conflicts
`that cannot be resolved automatically. A newer version of
`Coda supports low-bandwidth networks as well as inter-
`mittent communication [14]. Odyssey is a mobile-aware
`follow-on project that focuses on system support to enable
`mobile-aware applications to use “data fidelity” to control
`resource utilization. Data fidelity is defined as the degree to
`which a copy of data matches the original [15].
`The Ficus file system is a mobile-transparent, user-level
`file system supporting disconnected operation and peer-to-
`peer data sharing [16]. The Little Work project caches files
`to smooth disconnection from an AFS file system. Conflicts
`are detected and reported to the user. Little Work is also
`able to support partial connection over low-bandwidth
`networks [3].
`The BNU project implements an RPC-driven mobile-
`transparent application framework on mobile computers. It
`enables code shipping by downloading Scheme functions
`for interpretation [17]. The BNU environment includes mo-
`bile-transparent proxies on stationary hosts for hiding the
`mobility of the system. BNU applications do not dynami-
`cally adjust to the environment, nor do they have a concept
`of tentative or stale data. No additional support for discon-
`nected operation, such as Rover’s queued RPC is included
`in BNU. A follow-up project, Wit, addresses some of these
`shortcomings and shares many of the goals of Rover, but
`employs different solutions [18].
`A number of proposals have been made for various de-
`grees of mobile awareness in operating system services and
`applications. The Bayou project [12] defines a mobile-aware
`database architecture for sharing data among mobile users.
`Bayou supports tentative operation logs and tentative data
`values combined with session guarantees for weakly con-
`sistent replicated data [19]. Each database write is associ-
`ated with a dependency check and a deterministic, applica-
`tion-specific merge procedure. Each Bayou host replicates
`the entire database and may receive incremental updates
`from any other host. To illustrate these concepts, the
`authors built a calendar tool and a bibliographic database.
`Rover shares the notions of tentative operations and data,
`session guarantees, and the calendar tool example with the
`Bayou project. Rover’s RDO method invocation via QRPC
`is more general than Bayou database writes in that it sup-
`ports computation relocation and communication schedul-
`ing for dealing with intermittent communication, limited
`bandwitdh, and resource-poor clients.
`The DATAMAN project organized a framework for mo-
`bile-aware applications around an object-oriented, lan-
`guage-level event delivery architecture [20]. Applications
`interested in events in the environment declare EventOb-
`jects, which support both polling and triggers (callbacks).
`The DATAMAN application framework does not include
`support for data replication and consistency management.
`
`Petitioners Great West Casualty Co., BITCO Gen. Ins. Corp., and BITCO Nat'l Ins. Co.
`Ex. 1027, p. 4
`
`

`
`JOSEPH ET AL.: MOBILE COMPUTING WITH THE ROVER TOOLKIT
`
`341
`
`The InfoPad [21], Daedalus [22], GloMop [23], and W4
`[24] projects focus on mobile-aware wireless information
`access. The InfoPad project employs a dumb terminal and
`offloads all functionality from the client to the server with
`the specific goal of reducing power consumption. Daedalus
`and GloMop use dynamic “transcoding” or “distillation” to
`reduce the bandwidth consumed by data transmitted to a
`mobile host. Transcoding technology is completely com-
`patible with Rover’s architecture. Applications on the mo-
`bile host cooperate with mobile-aware proxies on a station-
`ary host to define the characteristics of the desired network
`connections. Similarly, to enable Web browsing, W4 divides
`application functionality between a small PDA and a more
`powerful, stationary host. Rover is designed for more flexi-
`ble, dynamic divisions. Depending on the power of the mo-
`bile host and available bandwidth, Rover allows mobile-
`aware browsers to move functionality between the client
`and the server dynamically.
`The DeckScape WWW browser [25] modifies the user
`interface of a Web browser, turning it into a “click-ahead”
`browser. DeckScape was developed simultaneously with
`the Rover HTTP proxy which transparently provides click-
`ahead for existing browsers. Since they implemented a
`browser from scratch, DeckScape is not compatible with
`existing browsers.
`The BARWAN project addresses the problems associated
`with “overlay networks,” networks of varying bandwidth,
`latency, coverage, and application-level performance visi-
`bility [26]. BARWAN supports mobile, “data type aware”
`applications by using proxies on both sides of the client–
`server link to monitor the performance attributes of the
`network. The monitoring, in conjunction with mobile code
`and a dynamically extensible type system, enables mobile-
`aware applications to trade processing cycles for network
`traffic. Similarly, Davies’s Adaptive Services [10] uses a
`protocol-centric approach to expose information about the
`mobile environment to applications. In contrast, Rover is
`designed to focus on dynamic adaptation of program func-
`tionality and data types.
`A number of successful commercial mobile-aware appli-
`cations have been developed for mobile hosts and limited-
`bandwidth channels. For example, Qualcomm’s Eudora is a
`mail browser that allows efficient remote access over low-
`bandwidth links. Lotus Notes [27] is a groupware applica-
`tion allowing users to share data in a weakly connected
`environment. Notes supports two forms of update opera-
`tions: append and time-stamped. Conflicts are referred to
`the user. TimeVision and Meeting Maker are group calen-
`dar tools that allow a mobile user to download portions of a
`calendar for off-line use. The Rover toolkit and its applica-
`tions provide functionality that is similar to these proprie-
`tary approaches, but in an application-independent man-
`ner. Using the Rover toolkit, standard workstation applica-
`tions such as Exmh and Ical can easily be turned into mo-
`bile-aware applications.
`Gray et al. perform a thorough theoretical analysis of the
`options for database replication in a mobile environment
`and conclude that primary-copy replication with tentative
`updates is the most appropriate approach for mobile envi-
`ronments [28].
`
`3 DESIGN OF THE ROVER TOOLKIT
`The Rover toolkit is designed to support the construction of
`mobile-aware applications and proxies
`for mobile-
`transparent applications. In this section, we describe the
`design of the key components of the Rover toolkit. In the
`following section, we discuss implementation details for
`each component of the toolkit.
`
`3.1 Object Design and QRPC
`The central structures in Rover are relocatable dynamic
`objects (RDOs). All Rover design decisions are based upon
`RDOs; thus, they provide the key point of control in Rover
`applications. RDOs have four components: mobile code,
`encapsulated data, a well-defined interface, and the ability
`to make outcalls to other RDOs. The mobile code and en-
`capsulated data components make an RDO relocatable
`from one machine to another. Each RDO provides methods
`for marshaling and unmarshaling itself so that it can be
`relocated to another machine and stored in a client’s cache.
`An RDO can invoke the methods of another RDO by using
`that RDO’s well-defined interface.
`RDOs may execute at either clients or servers. Each RDO
`has a “home” server that maintains its primary, canonical
`copy. Clients use library functions provided by the Rover
`toolkit to import secondary copies of RDOs into their local
`caches and to export logs of mutating method invocations
`back to servers.
`All application code and all application-touched data are
`contained within RDOs. RDOs may vary in complexity
`from simple data items with a small set of operations (e.g.,
`calendar entries) to modules that encapsulate a significant
`part of an application (e.g., the graphical user interface for
`an e-mail browser). The toolkit provides functions that en-
`able complex RDOs optionally to create threads of control
`when they are imported. The toolkit ensures the safe exe-
`cution of RDOs by using authentication and by executing
`RDOs in a controlled environment. For our research proto-
`type, we assume that RDOs may be faulty, but not mali-
`cious. Thus, the toolkit executes RDOs in separate address
`spaces, but does not rely on code inspection or other tech-
`niques to detect malicious code. These safety measures are
`appropriate for the sharing of objects between mobile hosts
`and servers in the framework of specific applications.
`However, there are several safety issues relating to the gen-
`eral use of mobile code that are not addressed by our cur-
`rent implementation. These safety issues represent an area
`of active research that is beyond the scope of this paper.
`At the level of RDO design, application builders have
`semantic knowledge that is useful in attaining the goals of
`mobile computing. By tightly coupling data with program
`code, applications can manage resource utilization more
`carefully than is possible with a replication system that
`handles only generic data. For example, an RDO can in-
`clude compression and decompression methods along with
`data in order to obtain application-specific and situation-
`specific compression, reducing both network and storage
`utilization.
`A QRPC may contain an RDO, a request for an RDO, or
`arbitrary application data. Rover clients use QRPC to fetch
`RDOs from servers lazily (see Fig. 1). When an application
`
`Petitioners Great West Casualty Co., BITCO Gen. Ins. Corp., and BITCO Nat'l Ins. Co.
`Ex. 1027, p. 5
`
`

`
`342
`
`IEEE TRANSACTIONS ON COMPUTERS, VOL. 46, NO. 3, MARCH 1997
`
`issues a QRPC, Rover stores the QRPC in a local stable log
`and immediately returns control to the application. If the
`application has registered a callback routine, it will be in-
`voked when the requested QRPC completes. Applications
`may poll the state of the QRPC or simply block to wait for
`critical data. However, this choice is undesirable, especially
`when the mobile host is disconnected. Upon reconnection,
`the Rover network scheduler drains the log in the back-
`ground, forwarding any queued QRPCs to the server.
`When a Rover application modifies a locally cached
`RDO, the cached copy is marked tentative. The RDO is only
`marked committed after the client knows that the Rover
`server has applied the mutating operations to the canonical
`RDO. These updates and resolutions are lazily propagated
`between the client and server using QRPC. In the mean-
`time, the application may choose to use tentative RDOs.
`This choice allows the application to continue execution
`even if the mobile host is disconnected. Cached copies of
`the RDO at other clients are updated either by client polling
`or server callbacks.
`
`3.2 Communication Scheduling
`The Rover network scheduler may deliver QRPCs out of
`order (i.e., non-FIFO) based on consistency requirements
`and application-specified operation priorities. Reordering is
`important for usability in an environment with intermittent
`connectivity, as it allows the user, through applications, to
`identify important operations. For example, a user may
`choose to send urgent updates as soon as possible while
`delaying other sends until inexpensive communication is
`available.
`Multiple QRPCs for the same server may be batched to-
`gether, reducing communication overhead. If the operating
`system provides the appropriate interface, the network
`scheduler can use batching to reduce the amount of time
`that a wireless transmitter is powered up but idle.
`QRPC supports split-phase operation; if a mobile host is
`disconnected between sending the request and receiving the
`reply, a Rover server will periodically attempt to contact the
`mobile host and deliver the reply. The split-phase communi