Fast encounter-based synchronization for mobile devices

The large and growing number of computing devices used by individuals has caused the challenges of distributed storage to take on increased importance. In addition to desktops and laptops, portable devices, such as cell phones, digital cameras, iPods, and PDAs are capable of storing and sharing data. These devices’ mobility coupled with wireless networking capabilities allows them to opportunistically propagate data to other devices they might encounter, even if connectivity is unplanned and transient. To take advantage of such ad hoc connectivity, devices must have an efficient method for determining which files they hold in common and which versions must be propagated to achieve consistency. This paper presents new techniques for reducing the cost of this data synchronization operation by over an order of magnitude in many situations.