|A Brief Description||Why Aren't Existing Systems Good Enough?||What Does Roam Provide?|
|Published Papers||Current Status|
Replication is extremely important in mobile environments because nomadic users require local copies of important data. Replication is more important in mobile environments than it is in stationary environments, because mobile users are often disconnected from a network or pay a high price for a degraded network connection. While the stationary user has fast, cheap, and easy access to off-machine resources, the mobile user does not, and therefore needs to have important data replicated locally.
However, today's replication systems are not "mobile-ready." Instead of improving the mobile user's environment, current replication systems actually hinder mobility and complicate mobile operation. Designed for stationary environments, replication services do not and cannot provide mobile users with the capabilities they require. Instead, they often force users to behave as if they were stationary, requiring the user to make expensive, long-distance phone calls over low bandwidth links to synchronize data with the server back home.
Consider, for example, the case of two businesspeople who travel from Los Angeles to New York for a meeting. In their hotel rooms, they would like to and should be able to directly synchronize data on each of their laptops. However, existing client-server solutions require that first laptop A contact the Los Angeles server via a long-distance connection and upload the changes, and then laptop B can make the same connection and download the changes . . . even though the two laptops are physically only a few feet apart. Existing peer-to-peer solutions would enable such direct communication, but suffers from dramatic scaling problems in the number of replicas, limiting the number of overall users and impacting performance.
in mobile environments requires
different solutions than those previously proposed, because nomadicity
presents a fundamentally new and different computing paradigm. Roam
is a system designed to meet those requirements.
There are numerous examples, like the one above, that illustrate scenarios in which mobile users would like to work but cannot, given the restraints of the replication system. In general, one main reason for this disparity is that many of the replication systems and underlying algorithms were designed without considering mobile computing and the strains mobility places on the system.
mobile computing was a feasible
designers simply didn't design their systems to be mobile-enabled.
were largely stationary, so there was no need to consider what would
if it were easy for people to move around geographically. Consider the
case of mobile-IP. When the Internet Protocol (IP) was developed,
was not feasible, and therefore was not considered in the design. Now
mobility is a reality, many researchers are trying to fix or
IP to support real mobility. Like the mobile-IP case, the replication
software must also be redesigned to account for mobile computing.
Roam is built using the Ward Model---a new replication architecture that has been designed especially with mobility in mind, though of course it applies equally well to stationary environments. The Ward Model provides a new replication paradigm that is neither strictly peer nor client-server; rather, it is a hybrid model of the two that allows everyone to be effectively a peer while maintaining good scalability in the number of replicas.
Additionally, Roam provides a number of new distributed algorithms. For instance, Roam contains new and improved distributed algorithms for garbage collection (the deallocation of disk space occupied by unnameable files) and for dynamic management of the version vector, the main data structure behind most optimistic replication systems.
Overall, therefore, Roam provides:
|An optimistic replication system capable of supporting both stationary and mobile users|
|The ability for any-to-any communication and synchronization between any two replicas in the entire system|
|The ability to become mobile at any time without advance warning or required "pre-motion" operations|
|An architecture that scales well (hundreds of read-write replicas)|
|Algorithms for as-fast-as-possible garbage collection of user data while still maintaining understandable semantics and guaranteeing that user data will never be accidently lost due to hypothetical scenarios involving dynamic naming and communication delays|
|Algorithms for the dynamic maintenance of version vectors, allowing the version vector itself to scale much better|
|A solution that runs entirely at the application level with no kernel hooks or support, making it extremely portable|
|There are a number of published papers on Roam and its subsystems. A complete listing of LASR publications can be found on the LASR home page. Here is a listing of some of the Roam-specific publications:|
|D. Ratner, P. Reiher, G.J. Popek and R. Guy. Peer Replication with Selective Control. First International Conference on Mobile Data Access, December 16-17, 1999, Hong Kong. To appear in Lecture Notes on Computer Science. Available in postscript format.|
|D. Ratner, P. Reiher, G.J. Popek, and G.H. Kuenning. Replication Requirements in Mobile Environments. Dial M for Mobility: 1st International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, October 1st, 1997, Budapest Hungar. Held in conjuction with ACM/IEEE MobiCom'97. To appear in Mobile Networks and Applications. Available in postscript format.|
|D. Ratner, P. Reiher, and G. Popek, Dynamic Version Vector Maintenance. UCLA Technical Report CSD-970022. June, 1997. Available via ftp.|
|D. Ratner, G. Popek, and P. Reiher, The
A Scalable Replication Architecture for Mobility. Workshop on
Replication and Mobile Computing, October 1996. Available as wardworkshop.ps.
is currently demo-able software. It is
of Dave Ratner's Ph.D. research.
|Back to: Travler
Last modified: June 2006