In this paper, we describe the design and use of Cimetric, a file synchronization application that supports scholarly collaboration. The system design incorporates results of earlier studies that suggest replicating content on a user's personal devices may have different characteristics than replicating content to share it with collaborators. To realize this distinction, Cimetric performs bi-level synchronization: it synchronizes local copies of a versioned repository among collaborators' computers, while it separately synchronizes private working files between each user's personal devices. Through a year's worth of in-house use of Cimetric in a variety of configurations, we were able to investigate key file synchronization issues, including the role of cloud storage given the ability to sync between peers; the strengths and weaknesses of a bi-level design; and which aspects of the synchronization process to reveal to users.

Work on delay tolerant networks (DTN) and peer-to-peer replication systems has made rapid advances with the similar goal of permitting reliable message delivery in challenged communication environments. Techniques developed for both types of systems also bear some similarity. Both exploit opportunistic connectivity to route messages and updates to their desired destinations while making minimal assumptions about end-to-end connectivity. However, they also have some unique characteristics. DTNs have recently incorporated forwarding algorithms that make use of historical information on past encounters between participants and predictions of future connectivity. Modern replication systems utilize protocols with low overheads that guarantee eventual consistency and at-most-once delivery while supporting content-based filters. In this paper, we show how a DTN-like messaging system can be readily built as a simple application on top of a peer-to-peer replication platform. To reduce delivery delays while retaining the desirable replication guarantees, we then extend the replication substrate to permit pluggable DTN routing protocols. We describe the implementation of four representative DTN schemes as replication policies and evaluate these extensions with emulations driven by traces of e-mail messaging and vehicular mobility. We conclude that DTNs and replication systems can benefit substantially from a cross-fertilization of ideas.

Docx2Go is a new framework to support editing of shared documents on mobile devices. Three high-level requirements influenced its design -- namely, the need to adapt content, especially textual content, on the fly according to the quality of the network connection and the form factor of each device; support for concurrent, uncoordinated editing on different devices, whose effects will later be merged on all devices in a convergent and consistent manner without sacrificing the semantics of the edits; and a flexible replication architecture that accommodates both device-to-device and cloud-mediated synchronization. Docx2Go supports on-the-go editing for XML documents, such as documents in Microsoft Word and other commonly used formats. It combines the best practices from content adaptation systems, weakly consistent replication systems, and collaborative editing systems, while extending the state of the art in each of these fields. The implementation of Docx2Go has been evaluated based on a workload drawn from Wikipedia.

Mobile devices often store data in reduced resolutions or custom formats in order to accommodate resource constraints and tailor-made software. The Polyjuz framework enables sharing and synchronization of data across a collection of personal devices that use formats of different fidelity. Layered transparently between the application and an off-the-shelf replication platform, Polyjuz bridges the isolated worlds of different data formats. With Polyjuz, data items created or updated on high-fidelity devices-such as laptops and desktops-are automatically replicated onto low-fidelity, mobile devices. Similarly, data items updated on low-fidelity devices are reintegrated with their high-fidelity counterparts when possible. Polyjuz performs these fidelity reductions and reintegrations as devices exchange data in a peer-to-peer manner, ultimately extending the eventual-consistency guarantee of the underlying replication platform to the multifidelity universe. In this paper, we present the design and implementation of Polyjuz and demonstrate its benefits for fidelity-aware contacts management and picture sharing applications.

Weakly consistent replication of data has become increasingly important both for loosely-coupled collections of personal devices and for large-scale infrastructure services. Unfortunately, automatic replication mechanisms are agnostic about the quality of the data they replicate. Inappropriate updates, whether malicious or simply the result of misuse, propagate automatically and quickly. The consequences may not be noticed until days later, when the corrupted data has been fully replicated, thereby deleting or overwriting all traces of the valid data. In this sort of situation, it can be hard or impossible to restore an entire distributed system to a clean state without losing data and disrupting users.

Cell phones connected to high-speed 3G networks constitute an increasingly important class of clients on the Internet. From the viewpoint of the servers they connect to, such devices are virtually indistinguishable from conventional end-hosts. In this study, we examine the IP addresses seen by Internet servers for cell phone clients and make two observations. First, individual cell phones can expose different IP addresses to servers within time spans of a few minutes, rendering IP-based user identification and blocking inadequate. Second, cell phone IP addresses do not embed geographical information at reasonable fidelity, reducing the effectiveness of commercial geolocation tools used by websites for fraud detection, server selection and content customization. In addition to these two observations, we show that application-level latencies between cell phones and Internet servers can differ greatly depending on the location of the cell phone, but do not vary much at a given location over short time spans; as a result, they provide fine-grained location information that IPs do not.

Mobile devices often store data in reduced resolutions or custom formats in order to accommodate resource constraints and tailor-made software. The Polyjuz framework enables sharing and synchronization of data across a collection of personal devices that use formats of different fidelity. Layered transparently between the application and an off-the-shelf replication platform, Polyjuz bridges the isolated worlds of different data formats. With Polyjuz, data items created or updated on high-fidelity devices-such as laptops and desktops-are automatically replicated onto low-fidelity, mobile devices. Similarly, data items updated on low-fidelity devices are reintegrated with their high-fidelity counterparts, when the application permits it. Polyjuz performs these fidelity reductions and reintegrations as devices exchange data in a peer-to-peer manner, ultimately extending the eventual-consistency guarantee of the underlying replication platform to the multi-fidelity universe.

Kinesis is a novel data placement model for distributed storage systems. It exemplifies three design principles: structure (division of servers into a few failure-isolated segments), freedom of choice (freedom to allocate the best servers to store and retrieve data based on current resource availability), and scattered distribution (independent, pseudo-random spread of replicas in the system). These design principles enable storage systems to achieve balanced utilization of storage and network resources in the presence of incremental system expansions, failures of single and shared components, and skewed distributions of data size and popularity. In turn, this ability leads to significantly reduced resource provisioning costs, good user-perceived response times, and fast, parallelized recovery from independent and correlated failures. This article validates Kinesis through theoretical analysis, simulations, and experiments on a prototype implementation. Evaluations driven by real-world traces show that Kinesis can significantly outperform the widely used Chain replica-placement strategy in terms of resource requirements, end-to-end delay, and failure recovery.

We introduce a novel measure called ε-four-pointscondition (ε-4PC), which assigns a value ε ∈ [0,1] to every metric space quantifying how close the metric is to a tree metric. Data-sets taken from real Internet measurements indicate remarkable closeness of Internet latencies to tree metrics based on this condition. We study embeddings of ε-4PC metric spaces into trees and prove tight upper and lower bounds. Specifically, we show that there are constants c1 and c2 such that, (1) every metric (X,d) which satisfies the ε-4PC can be embedded into a tree with distortion (1+ε)c1log|X|, and (2) for every ε ∈: [0,1] and any number of nodes, there is a metric space (X,d) satisfying the ε-4PC that does not embed into a tree with distortion less than (1+ε)c2log|X|. In addition, we prove a lower bound on approximate distance labelings of ε-4PC metrics, and give tight bounds for tree embeddings with additive error guarantees.

Correctness of a fault-tolerant system hinges on the failure model, which typically constrains the number of concurrent failures in the system. These assumptions are sometimes violated in practice, inevitably leading to degraded system behavior that deviates from the system's specification and even causing complete unavailability of the system.

CobWeb is an open-access content distribution network (CDN) that provides low latency lookups, resilience to flash crowds, and optimal utilization of network resources. Unlike traditional Web caches and CDNs, which rely on ad hoc heuristics for replica placement and cache management, CobWeb achieves superior performance through a unique analysis driven approach. CobWeb derives the optimal replica placement strategy by posing the fundamental performance-overhead tradeoff as a resource constraint problem. Analytically modeling the costs and performance benefits of replicas enables CobWeb to convert the systems problem to an optimization problem. The optimization problem can then be solved to provide, for instance, minimal lookup latency while achieving a targeted bandwidth cost, or to achieve a targeted lookup performance while minimizing bandwidth consumption. CobWeb is currently deployed on Planet-Lab and is available for open access through an intuitive easy-to-use interface.

Name services are critical for mapping logical resource names to physical resources in large-scale distributed systems. The Domain Name System (DNS) used on the Internet, however, is slow, vulnerable to denial of service attacks, and does not support fast updates. These problems stem fundamentally from the structure of the legacy DNS.This paper describes the design and implementation of the Cooperative Domain Name System (CoDoNS), a novel name service, which provides high lookup performance through proactive caching, resilience to denial of service attacks through automatic load-balancing, and fast propagation of updates. CoDoNS derives its scalability, decentralization, self-organization, and failure resilience from peer-to-peer overlays, while it achieves high performance using the Beehive replication framework. Cryptographic delegation, instead of host-based physical delegation, limits potential malfeasance by namespace operators and creates a competitive market for namespace management. Backwards compatibility with existing protocols and wire formats enables CoDoNS to serve as a backup for legacy DNS, as well as a complete replacement. Performance measurements from a real-life deployment of the system in PlanetLab shows that CoDoNS provides fast lookups, automatically reconfigures around faults without manual involvement and thwarts distributed denial of service attacks by promptly redistributing load across nodes.

A central challenge in ad hoc networks is the design of routing protocols that can adapt their behavior to frequent and rapid changes in the network. The performance of proactive and reactive routing protocols varies with network characteristics, and one protocol may outperform the other in different network conditions. The optimal routing strategy depends on the underlying network topology, rate of change, and traffic pattern, and varies dynamically. This paper introduces the Sharp Hybrid Adaptive Routing Protocol (SHARP), which automatically finds the balance point between proactive and reactive routing by adjusting the degree to which route information is propagated proactively versus the degree to which it needs to be discovered reactively. SHARP enables each node to use a different application-specific performance metric to control the adaptation of the routing layer. This paper describes application-specific protocols built on top of SHARP for minimizing packet overhead, bounding loss rate, and controlling jitter. Simulation studies show that the resulting protocols outperform the purely proactive and purely reactive protocols across a wide range of network characteristics.

Several routing protocols for mobile ad hoc networks work efficiently only in bidirectional networks. Unidirectional links may exist in a real network due to variations in transmission power of different nodes, noise or other signal propagation phenomena, and heterogeneity in the transmission hardware of nodes in the network. We introduce a sub-layer called sub routing layer, SRL, between the network and the MAC layer to provide a bidirectional abstraction of the unidirectional network to the routing protocols. We present a scalable and efficient way to provide this abstraction by finding and maintaining multi-hop reverse routes to each unidirectional link. We simulate SRL and a modified version of AODV (ad hoc on demand distance vector) that uses SRL to route packets in a unidirectional network. We observed that with SRL, the packet delivery of AODV in unidirectional networks increases substantially. Further our simulations indicate that reverse routes are often only a few hops long and hence the overhead of using SRL is very low.

In recent years, a number of applications of ad-hoc networks have been proposed. Many of them are based on the availability of a robust and reliable multicast protocol. We address the issue of reliability and propose a scalable method to improve packet delivery of multicast routing protocols and decrease the variation in the number of packets received by different nodes. The proposed protocol works in two phases. In the first phase, any suitable protocol is used to multicast a message to the group, while in the second concurrent phase, the gossip protocol tries to recover lost messages. Our proposed gossip protocol is called Anonymous Gossip (AG) since nodes need not know the other group members for gossip to be successful. This is extremely desirable for mobile nodes, that have limited resources, and where the knowledge of group membership is difficult to obtain. As a first step, anonymous gossip is implemented over MAODV without much overhead and its performance is studied. Simulations show that the packet delivery of MAODV is significantly improved and the variation in number of packets delivered is decreased.