Dave Ratner's Research

A ficus tree

Early Research

Dave has written and rewritten much of the guts of Ficus, including the directory and file manipulation code, as well as the very heart of Ficus: reconciliation. Of all contributors to Ficus, past and present, Dave is currently third in terms of number of current lines of code. Dave has hacked on most parts of Ficus at one time or another, but prefers spending his time down at the Ficus physical layer. Wouldn't you?

Masters Research: Selective Replication

Man and computer His masters thesis is in selective replication. The selective replication architecture provides fine-grain replication control within the volume structure. The peer model of Ficus is maintained, while files from volume replicas can be individually selected for replication control. Such a system allows for easier sharing of files between

Basically, the selective replication architecture provides an optimistic, peer replication service at a very fine granularity --- the file. This combines the replication flexibility of the client/server model (allowing clients to store subsets of data stored at the server) with the functionality of the peer-to-peer model (allowing anyone to communicate and synchronize with anyone else). More should eventually will be said here. The Masters Thesis is available by ftp, and a better-written paper is the UCLA technical report also available by ftp. Questions can be mailed to Dave.

PhD Research: Replication for Mobility

 Dave's PhD research is in replication for mobile environments. As of 26 July, 1995 he was officially made a PhD candidate. Guess his actual graduation date! The winner receives a six-pack of beer and whatever is laying behind his couch at the time.

The main thrust of the PhD is the construction of a replication system specifically for mobile use. This has several pieces:

The underlying architecture I have designed is called the Ward Model. The current best reference is a paper to be presented at the Dial M for Mobility Workshop in Budapest and to appear in a future issue of Mobile Networks and Applications, available in gzipped- Postscript.

Ward Model

The Ward model of replication is a replication architecture that is redesigned with mobility in mind, though of course it applies equally well to static machines. The name "ward" stands for Wide Area Replication Domain. Some notion of a peer-to-peer model is required when envisioning a mobile environment, because machines want the ability to directly synchronize with the other machines that are nearby. Having three portables at a conference, in a hotel room, or on an airplane and forcing them to exchange updates by in turn contacting some remote server (over a high cost, low bandwidth, high latency link) seems ludicrous. However, traditional peer models have suffered from severe scaling problems, and mobile environments clearly need the ability to scale well, given that a mobile machine without a local replica of the important data is almost worthless. The Ward model therefore contains a new form of the peer model, one that combines aspects of the traditional peer and client/server approaches. In this way we achieve both good scaling and the ability for any machine to directly synchronize and exchange updates with any other machine. It is currently being implemented at UCLA (by me).

Selective Replication

A second important aspect is the replication model as presented to the user. The selective replication work, described above, is a major part of this, as it becomes even more important in mobile environments where users are constrained by disk space, communication time, and communication cost. Regardless of the logical position objects in the namespace, the user wants to replicate just the set of objects he or she is currently interested in, because additional, "unwanted" objects How we detect what the user considers interesting objects is an entirely different matter, however, and is solved by Seer. Selective replication was implemented both in Ficus (by me) and in Rumor (also by me). Papers regarding selective replication can be found on my list of papers.

Other Distributed Algorithms

Of course, any large distributed project has its accompanying distributed algorithms. Of major note, I designed two. The first are algorithms to perform version vector compression. Version vectors are the entities used to perform versioning in the replication system. They guarantee to detect all updates, properly allow gossiping of updates between third-party sites, and detect all concurrent updates or conflicts. Unfortunately, they traditionally don't scale well, because one element of the vector is needed for each replica that has ever produced an update. My version vector compression algorithms allow the version vector to be shortened, meaning that only the "actively updating" replicas will have positions in the vector. Additionally, there are the algorithms to perform garbage collection---the deallocation of file system resources. Garbage collection must not prematurely release resources (such as disk space), because then users could lose data; however, users cannot reuse them until garbage collection completes, meaning that it is an important distributed algorithm to have operating quickly and efficiently. We improve on the algorithm from Ficus to lessen the impact on users from garbage collection. There is much to say here, but there is also much to do. You can read more about ROAM on ROAM's web page. Questions can be addressed to Dave.

Since you are here anyway, why don't you bug my advisor and tell him to graduate me already!

ratner@cs.ucla.edu
Last modified: Wed Mar 5 15:45:00 1997