A File System for Mobile Computing
`
`A Dissertation Proposal
`
`Jolm Saldanha
`
`Technical Report 93-17
`Distributed Computing Research Laboratory
`Department of Computer Science and Engineering
`University ofNotre Dame, Notre Dame, Indiana
`December 1993
`
`LG Electronics, Inc. et al.
`EXHIBIT 1007
`IPR Petition for
`U.S. Patent No.7, 149,511
`
`

`

` Abstract
`
`The recent proliferation of portable computers, the advent of personal digital assistants
`
`(PDAs) and continuing advances in computer networking all point to a future in which mobility of
`
`both users and computing system elements will be standard. However, these developments also inval-
`
`idate many of the assumptions made by current system software, which has been built for stationary
`
`systems and users. An important component of system software that needs to looked at afresh is the
`
`file system. A user should be able to access the files he or she needs regardless of location. Although
`
`existing research efforts do provide some support for this, there are significant deficiencies that need
`
`to be remedied. We propose two related designs to address these problems. The first exploits the
`
`unique property of a PDA that it can accompany its owner at all times by using it to carry files of most
`
`immediate need to him or her. The second makes use of the recently proposed idea of a computing
`
`persona.
`
`

`

`Table of Contents
`
`1. Introduction................................................................................................................................. 1
`2. Mobile Computing...................................................................................................................... 4
`2.1. Ubiquitous Computing..................................................................................................4
`2.2. Location-independent Computing ................................................................................5
`2.3. Networking ...................................................................................................................7
`3. Distributed File Systems............................................................................................................. 9
`3.1. The Coda File System...................................................................................................9
`3.1.1. Hoarding ......................................................................................................10
`3.1.2. Emulation.....................................................................................................11
`3.1.3. Reintegration................................................................................................12
`3.2. Disconnected Operation for AFS................................................................................13
`3.3. Ficus............................................................................................................................14
`4. Design ....................................................................................................................................... 16
`4.1. Problem Exposition.....................................................................................................16
`4.2. A PDA-based File System Design..............................................................................17
`4.3. Computing Personae and File Systems.......................................................................19
`5. Implementation ......................................................................................................................... 22
`
`REFERENCES ..............................................................................................................................24
`
`

`

`1. Introduction
`
`We are about to enter a new era in computing: the era of mobile computing. Computer hard-
`
`ware technology has progressed so rapidly that today’s portable computers are more powerful than the
`
`desktop computers built just a few years ago. Computer networks have also been expanding at an
`
`astonishing pace, and there have been constant advancements in networking technologies. While most
`
`computer networks until now have been of the wired type, there is much promise of wireless networks
`
`becoming widely available in the near future. All these developments will provide the hardware base
`
`needed for mobile computing.
`
`However, these advances in hardware cannot, by themselves, make mobile computing a com-
`
`mon reality. Many of the assumptions upon which current system software is based will no longer be
`
`valid. As pointed out in [Satyanarayanan 1993b], there are relative differences between mobile and
`
`stationary computers that will always exist and that are not the result of shortcomings of current tech-
`
`nology:
`
`• Mobile computers are resource-poor compared to stationary computers. Due to constraints on
`
`weight, size and power consumption, mobile computers will always be inferior to stationary comput-
`
`ers in multiple respects such as processing power and storage capacity. Moreover, there is also a
`
`strong possibility that technology advances for mobile computers will focus on reducing size and
`
`increasing battery life and, thus, the gap between them and fixed systems is likely to grow [Weiser
`
`1993b]. In some cases, incremental advances in technology will be of no avail due to human limita-
`
`tions. For example, no matter how much resolution is improved, there will be a limit to what the
`
`human eye can see clearly on a tiny screen.
`
`• Mobile computers are more prone to loss, damage and theft than stationary computers. Being moved
`
`around makes mobile computers more susceptible to loss or damage. And, of course, the street is not
`
`as safe as the office or home.
`
`• Mobile computers must operate under a much wider range of networking conditions than stationary
`
`ones. Stationary computers are generally connected to a wired network that has reliable and well-
`
`defined characteristics. A mobile one on the other hand must make do with whatever wired or wireless
`
`connectivity is available at its current location, which might often be none at all.
`
`1
`
`

`

`These differences are very significant and will require a complete redesign of system software.
`
`It is also likely that we will soon a see much greater variety of mobile computing devices in
`
`terms of functionality. Currently, most mobile computers are portable workstations i.e. machines that
`
`are lighter and smaller than desktop workstations but functionally very similar to them. They have
`
`full-size keyboards and screens that are typically 10” across; they can be used quite easily for tasks
`
`such as typing in a document. Recently however, we have seen the introduction of a new class of
`
`mobile computers popularly called personal digital assistants (PDAs). Examples are the Apple New-
`
`ton, the AT&T Eo and the IBM-BellSouth Simon. These PDAs are pocket-sized, have pads that serve
`
`as both screens and input devices, and are likely to be used quite differently from conventional com-
`
`puters. The very different character of these devices must be considered when designing system soft-
`
`ware for them.
`
`Mobility of computers is not the only kind of mobility that will have to be dealt with. Even in
`
`cases where elements of a distributed system are stationary, its users are mobile, and there are numer-
`
`ous problems to be solved. The movement of a user from one location in the system to another should
`
`in general make as little difference as possible to the way that user interacts with the system. For
`
`example, the user would like to be able to access the same files and applications and possibly even
`
`have running applications move as he or she moves. Mail intended for the user should always be
`
`delivered to his or her current location.
`
`There are, of course, some things that should not be location-independent. As a simple exam-
`
`ple, the user would presumably want the clock display to show the local time. Or, if a user moves from
`
`a terminal that can display only text to one that can display graphics, applications should take advan-
`
`tage of this additional capability. We thus see the need for system software to insulate the user from
`
`most changes caused by mobility while adapting to or even exploiting others.
`
`Each user has a certain set of preferences as to the environment provided by the computing
`
`system. In a fairly static system, a user profile stored in a file would suffice to define these preferences.
`
`However, under the widely varying conditions introduced by mobility, this will probably be insuffi-
`
`cient. In [Banerji 1993], the concept of a computing persona has been proposed to deal with this prob-
`
`lem. Associated with each user is a customized persona that represents the computing environment
`
`2
`
`

`

`that is closest to the user’s preferences under the prevailing conditions. When the user moves to a new
`
`location, the persona is re-established there with as little modification as is possible. When changes in
`
`physical conditions so demand, the user’s persona will change according to specified policies.
`
`An important component of system software that mobile computing forces us to take a fresh
`
`look at is the file system. An isolated computer has its own file system while one that is part of an
`
`interconnection can use a shared file system in which files may be stored on remote computers. Exist-
`
`ing file systems assume that a computer falls cleanly into one of these two categories. However, a
`
`mobile computer can be an isolated computer at times and part of a distributed system at others. It can
`
`also move from one distributed system to another or be connected to a single and otherwise isolated
`
`computer through a short-range link. How does one design a file system for such a computer so that its
`
`user can effectively operate in these different situations and move from one to another in a seamless
`
`manner? This problem will form the focus of this document.
`
`In the next chapter, we take a broad look at work that has been done in the area of mobile com-
`
`puting. In Chapter 3, we review existing distributed file systems that provide support for mobile com-
`
`puting. In the following chapter, we point out where these systems fall short and present a design that
`
`addresses these problems. The final chapter presents some early ideas for implementation of the sys-
`
`tem.
`
`3
`
`

`

`2. Mobile Computing
`
`This chapter provides an overview of the different directions being taken to support mobile
`
`computing. It will first cover an approach to future computing that is extensively based on the use of
`
`mobile computers. Next, we take a look at work that has been done in the area of location-indepen-
`
`dent computing. Finally, we touch on work being done to support networking of mobile computers.
`
`2.1 Ubiquitous Computing
`
`An important research effort that is intimately connected with mobile computing is the ubiqui-
`
`tous computing (Ubicomp) project at Xerox PARC. [Weiser 1991] introduced a vision of the future
`
`of computing in which scores of computers of widely varying sizes and kinds are scattered inconspic-
`
`uously throughout the physical environment and their use by people becomes unconscious. This
`
`vision is based on the idea that it is only when computers fade into the background, instead of being
`
`the focus of attention, that they will become truly effective tools in our everyday life.
`
`As the first step in the project, Weiser and his colleagues have built and deployed in their
`
`offices computing devices of three different sizes. The first is a wall-mounted interactive surface
`
`called a board that is roughly speaking an intelligent whiteboard. The second is a notebook-sized
`
`device called a pad which has a writing and display surface. The third and smallest kind of device,
`
`called a tab, is palm-sized and consists of a monochrome display with a transparent pressure-sensitive
`
`screen on top and buttons on the side. A typical room will contain hundreds of tabs, tens of pads and
`
`one or two boards.
`
`Both the pads and the tabs are mobile devices and clearly most of the communication will
`
`have to be wireless. Ubiquitous computing and mobile computing are therefore very closely tied
`
`together if not two terms for the same thing. In [Weiser 1993a], several of the computer science issues
`
`that have to be addressed in order to make ubiquitous computing a reality are raised. New hardware
`
`will have to be developed e.g. low-power devices, wireless networks capable of handling hundreds of
`
`devices within a small space, and pen-based devices. New network protocols are needed for wireless
`
`media access. New substrates for human-computer interaction have also to be developed. For exam-
`
`4
`
`

`

`ple, tabs are too small for a keyboard, so an alternative means of input has to be used. Ubiquitous
`
`computing will require a whole new set of applications e.g. ones for locating people and shared draw-
`
`ing. Mechanisms have to be created that will allow individuals control over the accumulation and dis-
`
`semination of information about them such as their location [Spreitzer 1993].
`
`Ubicomp is already been applied to a real problem: that of providing responsive office envi-
`
`ronments that automatically control conditions such as temperature and lighting condition in a manner
`
`that satisfies the occupants while conserving energy [Elrod 1993]. Several offices within Xerox PARC
`
`have been outfitted with temperature, light-level, occupancy, and active badge [Want 1992] sensors
`
`together with computer-controlled ventilation, heating, electrical outlets, and overhead lighting.
`
`These devices are connected to a conventional computerized building management system. Occu-
`
`pants of an office can control the lighting and temperature using a tab. By automatically shutting off
`
`lights and lowering the heating or cooling of rooms when they are unoccupied, energy savings can be
`
`realized.
`
`2.2 Location-independent Computing
`
`In general, users want their mobility to make as little difference as possible to the way they
`
`interact with their computing system. For this reason, location independence is already an important
`
`issue in current distributed systems and is likely to become even more important once mobile comput-
`
`ing devices become a common part of such systems. Some distributed file systems such as the
`
`Andrew File System [Howard 1988] provide location-independence by using a global name space.
`
`Others like the Prospero File System [Neuman 1992] provide a location-independent name space to
`
`each user but allow different users to have different name spaces. The Prospero Directory Service
`
`attempts to extend this user-centered location-independent view to computing resources other than
`
`just files [Neuman 1993].
`
`With Prospero, each user defines a virtual system which is a hierarchical name space for the
`
`available computing resources. Since a virtual system is customized for a particular user, different
`
`users see different name spaces. However, as a user moves from one location to another, he or she
`
`sees the same name space. Also, the binding of names to objects does not have to be static. Rather, a
`
`name can be used to refer to certain logical attributes so that as changes occur (such as in the location
`
`5
`
`

`

`of the user) the binding changes to the new object that satisfies those attributes.
`
`An example user virtual system is shown in Figure 1. The ROOT link refers to the root of the
`
`user’s virtual file system, which is a Prospero file system that provides the same representation regard-
`
`less of location. The SESSIONS link points to the collection of sessions the user has currently estab-
`
`lished. An entry is automatically added to the SESSIONS directory each time the user logs in. This
`
`entry will point to the virtual system of the platform on which the user logged in, which will contain
`
`various platform-specific information.
`
`ROOT
`
`SESSIONS
`
`CONFIG
`
`Virtual File System
`
`USERS
`
`SERVERS
`
`SAL-2.USC.EDU
`
`PRINTERS
`
`Platform-Info
`
`LINKS TO OTHER
`VIRTUAL SYSTEMS
`
`Symbolic link to
`SESSION#:CONFIG/SERVERS/PRINTERS
`Figure 1: An Example Prospero Virtual System
`
`The servers that the user has selected are included in the CONFIG/SERVERS directory. For
`
`example, the CONFIG/SERVERS/PRINTERS directory defines the available printers. These printers
`
`do not have to be explicitly defined. Instead a symbolic link to a directory of printers for the session
`
`currently being used can be defined using a virtual system alias. Such an alias ends with the string #:
`
`e.g. SESSION#:CONFIG/SERVERS/PRINTERS, which will be resolved by taking the sub-string fol-
`
`lowing the #: and resolving it in the virtual system of the user’s current session.
`
`Prospero also provides two useful features called union links and filters. When a union link is
`
`added to a directory, it results in a directory that is the union of the original directory and the directory
`
`pointed at by the union link. For example, a user could obtain a combined view of the printers at
`
`home and at office by creating union links to the individual directories representing these collections.
`
`6
`
`

`

`Filters are functions applied to a directory to select only a portion of the objects in it based on certain
`
`criteria. For example, an attribute() filter can be applied to a directory of printers to select only those
`
`printers that have the attribute POSTSCRIPT.
`
`2.3 Networking
`
`Much work needs to be done in the area of networking for mobile computers since the field of
`
`wireless networks is still in its infancy. Most of the current network protocols assume that all comput-
`
`ers are stationary. Also, a fairly large and constant bandwidth (10 Mb/s for Ethernet) is assumed. Fur-
`
`thermore, while there are capital costs incurred in setting up a network, operational costs are low and
`
`so network communication is assumed to be essentially free. None of these assumptions will continue
`
`to hold in the case of the wireless networks that will commonly be used by mobile computers. New
`
`network architectures and protocols must therefore be devised to deal with these changed conditions.
`
`One approach to dealing with mobility that seems to be gaining popularity is to have a proxy
`
`[Watson 1993] or agent [Adams 1993] [Athan 1993] for each mobile computer. This proxy resides at
`
`a fixed network address and is responsible for keeping track of the whereabouts of the mobile host.
`
`The mobile host is known to other hosts on the network only by its proxy’s address and so all mes-
`
`sages intended for it are sent to its proxy which then does the necessary forwarding.
`
`In [Bhagwat 1993], a scheme has been presented that uses an existing option in the Internet
`
`Protocol (IP) to provide transparent network access to mobile hosts. This option called the Loose
`
`Source Route (LSR) option provides a means for the source of a datagram to provide partial routing
`
`information that can be used by routers to forward it to the destination. Return traffic to the originator
`
`of an LSR packet is also sent with the LSR option by reversing the route taken by the incoming pack-
`
`ets. While the initial packets may have to travel by a sub-optimal route (because the current location
`
`of a mobile host is not known to the source), subsequent packets use the optimal route. It should be
`
`noted, however, that there are potential security problems associated with use of the LSR option.
`
`The system is organized in the following manner. Multiple subnets are reserved for mobile
`
`hosts. These subnets are logical and not physical. Each such subnet has a mobile router (MR) which
`
`keeps track of the current physical location of the MHs assigned to that subnet and routes packets des-
`
`tined for them. A mobile host (MH) must physically lie within the cell of a Mobile Access Station
`
`7
`
`

`

`(MAS) to communicate with hosts on the wired network. The MASs act as gateways between the
`
`wired and wireless parts of the network.
`
`When an MH initiates communication with a stationary host (SH), the packet goes to the
`
`MAS, which sends it to the SH by the optimal route since the SH’s location is fixed and well-known.
`
`The reply packets from the SH to the MH use the LSR option to reverse the route and so the optimal
`
`route is used in the reverse direction too. On the other hand, if an SH initiates communication with an
`
`MH, it will be unaware of the MH’s current location. Therefore, the initial packets will go to the MR
`
`responsible for that MH, which will forward it to the MH’s current MAS, which will in turn deliver it
`
`to the MH. Reply packets from the MH to the SH, however will be sent by the optimal route by the
`
`MAS using the LSR option. Once the SH receives such a reply packet, it sends subsequent packets to
`
`the MH along the optimal route by reversing the LSR option.
`
`When an MH (say MH1) initiates communication with another MH (say MH2), its MAS
`
`checks to see if MH2 is in the same cell. If so, the packets are sent directly to MH2 and reply packets
`
`use the reverse route back to MH1. (If the wireless technology supports direct MH to MH communi-
`
`cation, MH1 and MH2 can bypass the MAS once they learn they are in the same cell.) However, if
`
`MH2 was in different cell from MH1, the initial packets would be sent by MH1’s MAS (MAS1) to the
`
`MR for MH2, which would send it to the MH2’s MAS (MAS2). Reply packets would be sent by
`
`MAS2 by the optimal route to MAS1 and once such a packet is received by MAS1, it can send subse-
`
`quent packets destined for MH2 directly to MAS2.
`
`8
`
`

`

`3. Distributed File Systems
`
`Most work in the area of file systems for mobile computing has focussed on providing support
`
`for mobile computers within distributed file systems. This chapter will cover three such efforts: the
`
`Coda File System, the LITTLE WORK project’s support for disconnected operation for AFS, and the
`
`Ficus distributed file system.
`
`3.1 The Coda File System
`
`The Coda File System [Satyanarayanan 1990], developed at Carnegie Mellon University, is a
`
`distributed file system that provides support for portable computers. Coda bears a strong resemblance
`
`to its ancestor the Andrew File System (AFS) [Howard 1988] in many ways. Like AFS, it is designed
`
`for an environment consisting of a large number of untrusted Unix clients and a much smaller number
`
`of trusted Unix file servers. The servers collectively provide a single location-independent tree-struc-
`
`tured name space to clients. This name space is divided into sub-trees called volumes and storage of
`
`files at individual servers takes place at this granularity. Each client has a cache manager named
`
`Venus that caches files from the servers on its local disk in order to provide reasonable performance.
`
`AFS has been largely successful in meeting its design goals of providing secure, shared file
`
`access in a distributed system while scaling gracefully. Furthermore, while it was not designed to sup-
`
`port mobile computers, its provision of a location-independent name space was an important step
`
`towards support for mobile users. However, a major problem with it is that failures of servers or the
`
`network severely compromise availability of data. Coda seeks to address this problem through two
`
`mechanisms: server replication and disconnected operation [Kistler 92]. Server replication is a fea-
`
`ture whereby a single volume has read-write replicas at more than one server. The set of replication
`
`sites for a volume is called its volume storage group (VSG). The subset of the VSG currently accessi-
`
`ble at a client is that client’s accessible VSG (AVSG). As long as there is at least one server in a cli-
`
`ent’s AVSG, all files in that volume are available at that client for both reading and writing.
`
`Disconnected operation occurs when the AVSG becomes empty. This may be caused by
`
`server or network failure (an involuntary disconnection) or the unplugging of a portable computer
`
`9
`
`

`

`from the network (a voluntary disconnection). In either case, the client must rely on the current con-
`
`tents of its cache to service file system requests. Coda supports disconnected operation by pre-caching
`
`files the user is most likely to need while disconnected, allowing all operations on these files during
`
`disconnection and then reintegrating changes upon reconnection. Support for mobile computers has
`
`been treated as a special case of the general problem of supporting disconnected operation.
`
`Both server replication and disconnected operation are based on an optimistic replication strat-
`
`egy that allows updates in all partitions of a distributed system, with conflicts being detected and
`
`resolved after healing of partitions. The success of such a strategy depends on the actual occurrence
`
`of conflicts being relatively rare. Since concurrent write sharing is generally infrequent in Unix envi-
`
`ronments [Baker 1991] [Ousterhout 1985], such an assumption is in fact reasonable to make.
`
`It is Coda’s support for disconnected operation that is most interesting from the point of view
`
`of mobile computing and so it will be instructive to see in some detail how this support is provided.
`
`Most of the burden of providing this support is placed on Venus, the cache manager at each client.
`
`Venus rotates between three states: hoarding, emulation and reintegration. Hoarding is the normal
`
`state - here the client is connected and Venus is constantly hoarding files in its cache in preparation for
`
`possible disconnection. When disconnection actually occurs, Venus moves into the emulation state,
`
`so named because it must emulate certain server functions. Upon reconnection, it moves into the rein-
`
`tegration state, in which it resynchronizes its cache with the AVSG. When this has completed, it goes
`
`back into the hoarding state.
`
`3.1.1 Hoarding
`
`Traditionally, caching is used for reasons of performance. The objective of the cache manager
`
`is therefore to predict the data references that will be made in the immediate future and prefetch such
`
`data into the cache. In the case of Coda, the cache is being used for a second purpose - as a store for
`
`data that may not be referenced in the near future but whose availability is still critical. Therefore,
`
`while hoarding, Venus must balance these two possibly conflicting objectives while deciding which
`
`files to include in the cache. It does this by considering both objectives while assigning priorities to
`
`files and retaining the files with the highest priorities.
`
`Venus uses both implicit information and explicit hints from the user while assigning priori-
`
`10
`
`

`

`ties. The implicit information is the recent file reference history that is normally used for cache man-
`
`agement. The explicit hints are contained in a hoard database (HDB) residing on the client that
`
`indicates which file objects (files and directories) are critical to the user during disconnection and what
`
`their relative priorities, called hoard priorities, are. Entries in the HDB consist of pathnames of file
`
`objects along with their hoard priorities. The overall priority of a file object is a function of both its
`
`hoard priority and a measure that is based on its recent usage.
`
`The user modifies the HDB using command scripts called hoard profiles. A hoard profile
`
`specifies objects to be added and deleted from the HDB and their hoard priorities. There is also sup-
`
`port for meta-expansion of HDB entries i.e. one entry can specify an object together with all its chil-
`
`dren or all its descendants.
`
`The cache is said to be in equilibrium when no uncached object has a higher priority than a
`
`cached object. Routine file usage as well as modifications to the HDB result in changes to the priori-
`
`ties of objects, thereby upsetting equilibrium. Venus performs periodic hoard walks to restore equilib-
`
`rium. A hoard walk consists of first recomputing meta-expansions of HDB entries, then reevaluating
`
`priorities of all objects in the cache and finally replacing objects as necessary to restore equilibrium.
`
`3.1.2 Emulation
`
`Disconnection causes Venus to move into the emulation state. Since servers are inaccessible,
`
`Venus has to perform many of the functions usually performed by them, such as access checks. It also
`
`generates temporary file identifiers (fids) for new objects, which are converted to permanent ones dur-
`
`ing reintegration. Cache entries of deleted objects are freed while those of updated objects are given
`
`infinite priority so that they are not purged before reintegration. The changes made to the local cache
`
`must eventually make their way to the server upon reconnection. Venus must therefore keep a record
`
`of all mutating operations in sufficient detail that, later on, servers can validate these changes and then
`
`apply them to the server copies. Therefore, a log of all mutating operations, called a replay log, is
`
`maintained for each volume.
`
`However it is also important that Venus make the most efficient use of the limited local disk
`
`space while doing this, so several optimizations are used to keep the log small. One such optimization
`
`is to record the open, close and intervening write operations on a single file as a single store
`
`11
`
`

`

`operation that occurs at the time of the close. Also, when a new store record is appended to the
`
`log, all previous store records pertaining to that file can be discarded. Further, when one operation
`
`merely serves to nullify the effect of a previous operation, the records for both operations can be
`
`deleted from the log.
`
`The shutdown of a disconnected client should not result in loss of data and a crash should not
`
`result in more loss of data than if the machine were connected. Therefore, the cache contents as well
`
`as any meta-data must be kept in non-volatile storage. Venus uses a transaction facility called Recov-
`
`erable Virtual Memory (RVM) [Satyanarayanan 1993a] to provide persistent storage as well as a
`
`recovery mechanism for its meta-data. The meta-data is periodically flushed to disk with Venus able
`
`to schedule the flushes. During emulation, Venus plays safe by performing these flushes more fre-
`
`quently.
`
`3.1.3 Reintegration
`
`Upon reconnection with one or more servers, Venus must propagate to the servers the changes
`
`made locally while disconnected, as well as refresh its cache to reflect updates that have been made to
`
`the servers by other clients in the system. Reintegration is performed a volume at a time, with update
`
`activity to the volume being suspended during this time.
`
`Venus first replaces any temporary fids used in the replay log with permanent fids. It then
`
`ships the replay log in parallel to the AVSG. Each server performs the replay within a single transac-
`
`tion as follows. First, the transaction is begun, the log is parsed and all objects referenced by it are
`
`locked. Next, each operation is checked for conflict detection, protection, etc., and is executed if
`
`valid. In the case of store operations, everything except for actual data transfer is done in this step.
`
`The data transfers for all such operations are then performed in the next step. Finally, the transaction
`
`commits and all locks are released.
`
`If reintegration succeeds, Venus frees the replay log and resets the priority of the cached
`
`objects it referenced. Otherwise, it writes the log out to a local replay file and purges the log and the
`
`cache entries of referenced objects. A tool is provided to allow the user to inspect the contents of the
`
`replay file, compare it to the state at the AVSG, and replay it selectively or entirely.
`
`12
`
`

`

`The only conflicts Coda has to detect are write/write conflicts, since the UNIX file system has
`
`no notion of atomicity beyond the boundary of a single system call. Each object is tagged with a
`
`storeid that uniquely identifies the last update to it. When replaying the log, the server has only to
`
`compare the storeid mentioned in the log with the one for its own replica to tell whether a conflict
`
`exists or not. If a conflict occurs on a directory, it is usually due to two different entries in the direc-
`
`tory being updated concurrently; Coda can automatically resolve such conflicts by simply merging the
`
`two versions. However, in the case of files, resolution must be left to the user since Coda does not
`
`understand their semantic content.
`
`3.2 Disconnected Operation for AFS
`
`The LITTLE WORK project [Honeyman 1992] at the University of Michigan is an attempt to
`
`support portable computers within existing distributed computing environments. As part of this
`
`project, disconnected operation support for AFS has been developed through modifications to the
`
`cache manager at the AFS client [Huston 1993]. This work is quite similar to Coda in that it uses the
`
`client’s cache to store files t