State-of-the-art consensus protocols like Paxos reveal the values being agreed upon to all nodes, but some deployment scenarios involving a subset of nodes outsourced to public cloud providers motivate hiding the value. In this work, we present the primary-backup secret-shared state machine (PBSSM) architecture and an underlying consensus protocol Oblivious Paxos (OPaxos) that enable strong consistency, high availability, privacy, and fast common-case performance. OPaxos enables privacy-preserving consensus by allowing acceptors to safely agree on a secret-shared value without utrusted acceptors knowing the value. We also present Fast Oblivious Paxos (Fast-OPaxos), which enables consensus over secret-shares in three one-way delays under low concurrency settings. Our prototype-driven microbenchmarks and smarthome case study show that OPaxos induces a negligible latency overhead of at most 0.1 ms compared to Paxos while maintaining more than 85% of Paxos' capacity for small requests, and can provide lower latency and higher capacity compared to Paxos for large request sizes.

Managed DNS (MDNS) services today excel at providing a simple and cost-effective way to outsource domain management and ensure rapid lookup times for geo-distributed users. The intense focus on optimizing lookup performance coupled with DNS’ inherent expectations of weak consistency has had unfortunate side effects: updates are inexplicably slow and MDNS providers pay scant attention to consistency correctness. We conduct an empirical measurement-driven study of 8 top-tier managed DNS providers and find that inter-nameserver update propagation delays commonly take tens of seconds with little improvement over the last several years. Client-perceived inconsistency is rampant with roughly a third of end-users being vulnerable to TTL abuse by local DNS resolvers. Furthermore, we find that 6 of the 8 MDNS providers violate monotonic read consistency under frequent updates and at least one large MDNS provider appears to violate even eventual consistency.

Future Internet Architectures must support the rapid growth of traffic generated by mobile endpoints in a manner that is scalable and ensures low latency. We present a quantitative evaluation of three distinct approaches towards handling endpoint mobility: name-based forwarding, indirection and a global name service (GNS). Using a range of parameterized mobility distributions and real ISP topologies, we describe representative instantiations of each approach and evaluate their performance using four key metrics: update cost and update propagation cost in the control plane; and forwarding traffic cost and time-to-connect (TTC) in the data plane. (1) We show that by leveraging the fact that realistic endpoint mobility distributions show a high probability of being at a small subset of visited locations, name-based forwarding strategies can provide up to 60% improvement in control costs over simple best-port forwarding. (2) We show that the TTC in these name-based forwarding strategies is comparable to the TTC in the GNS. (3) Finally we show that a GNS-based approach offers the most suitable balance of total (combined data and control) cost to TTC across all approaches, all endpoint mobility distributions, and all ISP topologies considered.

Despite the explosive growth of mobile devices and applications in recent years, today's Internet provides little intrinsic support for seamless mobility. Prior solutions to addressing this problem either handle only a subset of endpoint mobility scenarios or require nontrivial changes to legacy infrastructure. In this paper, we present the design and implementation of msocket, a system that allows communicating endpoints to move across network locations arbitrarily while maintaining disruption-tolerant connectivity without any change to legacy operating systems or network infrastructure. msocket supports pre-lookup, connect-time, individual, and simultaneous mobility of one or both endpoints across multihomed network addresses, and enables seamless mobile-to-mobile communication despite the presence of address-translating middleboxes. We have implemented msocket as a user-level socket library and our evaluation shows that: (1) msocket recovers from mobility of one or both endpoint(s) in roughly two round-trips; (2) msocket's multipath scheduler greatly enhances user-perceived performance or power consumption in multihomed settings; and (3) msocket imposes little additional overhead over traditional TCP/IP sockets.

BGP is known to have many security vulnerabilities due to the very nature of its underlying assumptions of trust among independently operated networks. Most prior efforts have focused on attacks that can be addressed using traditional cryptographic techniques to ensure authentication or integrity, e.g., BGPSec and related works. Although augmenting BGP with authentication and integrity mechanisms is critical, they are, by design, far from sufficient to prevent attacks based on manipulating the complex BGP protocol itself. In this paper, we identify two serious attacks on two of the most fundamental goals of BGP-to ensure reachability and to enable ASes to pick routes available to them according to their routing policies-even in the presence of BGPSec-like mechanisms. Our key contributions are to (1) formalize a series of critical security properties, (2) experimentally validate using commodity router implementations that BGP fails to achieve those properties, (3) quantify the extent of these vulnerabilities in the Internet's AS topology, and (4) propose simple modifications to provably ensure that those properties are satisfied. Our experiments show that, using our attacks, a single malicious AS can cause thousands of other ASes to become disconnected from thousands of other ASes for arbitrarily long, while our suggested modifications almost completely eliminate such attacks.

Physical human mobility has played an important role in the design and operation of mobile networks. Physical mobility, however, differs from user identity (name) mobility in both traditional mobility management protocols such as Mobile-IP and in new architectures, such as XIA and MobilityFirst, that support identity mobility and location independence as first class objects. A multi-homed stationary user or a stationary user shifting among multiple devices attached to different networks will persistently keep his/her identity but will change access networks and the IP address to which his/her identity is associated. We perform a measurement study of such user transitioning among networks from a network-level point of view, characterizing the sequence of networks to which a user is attached and discuss insights and implications drawn from these measurements. We characterize network transitioning in terms of network residency time, degree of multi-homing, transition rates and more. We find that users typically spend time attached to a small number of access networks, and that a surprisingly large number of users access two networks contemporaneously. We develop and validate a parsimonious Markov chain model of canonical user transitioning among networks that can be used to provision network services and to analyze mobility protocols.

Distributed clouds offer a choice of data center locations to application providers to host their applications. In this paper we consider distributed clouds that host virtual desktops(VDs) which are then accessed by their users through remote desktop protocols. VDs have different sensitivities to latency, primarily determined by the types of applications running (games or video players are more sensitive to latency) and the end users' locations. We design VMShadow, a system to automatically optimize the location and performance of latency-sensitive VDs in the cloud. VMShadow performs black-box fingerprinting of a VM's network traffic to infer its latency-sensitivity and employs a greedy heuristic based algorithm to move highly latency-sensitive VMs to cloud sites that are closer to their end users. VMShadow employs WAN-based live migration and a new network connection migration protocol to ensure that the VM migration and subsequent changes to the VM's network address are transparent to end-users. We implement a prototype of VMShadow in a nested hypervisor and demonstrate its effectiveness for optimizing the performance of VM-based desktops in the cloud. Our experiments on a private and the public EC2 cloud show that VMShadow is able to discriminate between latency-sensitive and insensitive desktop applications and judiciously move only those VMs that will benefit the most. For desktop VMs with video activity, VMShadow improves VNC's refresh rate by 90%. Further our connection migration proxy, which utilizes dynamic rewriting of packet headers, imposes a rewriting overhead of only 13μs per packet. Trans-continental VM migrations take about 4 minutes.

This paper presents a quantitative methodology and results comparing different approaches for {\it location-independent} communication. Our approach is empirical and is based on real Internet topologies, routing tables from real routers, and a measured workload of the mobility of devices and content across network addresses today. We measure the extent of network mobility exhibited by mobile devices with a home-brewn Android app deployed on hundreds of smartphones, and measure the network mobility of Internet content from distributed vantage points. We combine this measured data with our quantitative methodology to analyze the different cost-benefit tradeoffs struck by location-independent network architectures with respect to routing update cost, path stretch, and forwarding table size. We find that more than 20% of users change over 10 IP addresses a day, suggesting that mobility is the norm rather than the exception, so intrinsic and efficient network support for mobility is critical. We also find that with purely name-based routing approaches, each event involving the mobility of a device or popular content may result in an update at up to 14% of Internet routers; but, the fraction of impacted routers is much smaller for the long tail of unpopular content. These results suggest that recent proposals for pure name-based networking are suitable for highly aggregateable content that does not move frequently but may need to be augmented with addressing-assisted approaches to handle device mobility.

Mobile devices dominate the Internet today, however the Internet rooted in its tethered origins continues to provide poor infrastructure support for mobility. Our position is that in order to address this problem, a key challenge that must be addressed is the design of a massively scalable global name service that rapidly resolves identities to network locations under high mobility. Our primary contribution is the design, implementation, and evaluation of auspice, a next-generation global name service that addresses this challenge. A key insight underlying auspice is a demand-aware replica {placement engine} that intelligently replicates name records to provide low lookup latency, low update cost, and high availability. We have implemented a prototype of auspice and compared it against several commercial managed DNS providers as well as state-of-the-art research alternatives, and shown that auspice significantly outperforms both. We demonstrate proof-of-concept that auspice can serve as a complete end-to-end mobility solution as well as enable novel context-based communication primitives that generalize name- or address-based communication in today's Internet.

We present VMShadow, a system that automatically optimizes the location and performance of applications based on their dynamic workloads. We prototype VMShadow and demonstrate its efficacy using VM-based desktops in the cloud as an example application. Our experiments on a private cloud as well as the EC2 cloud, using a nested hypervisor, show that VMShadow is able to discriminate between location-sensitive and location-insensitive desktop VMs and judiciously moves only those that will benefit the most from the migration. For example, VMShadow performs transcontinental VM migrations in ~ 4 mins and can improve VNC's video refresh rate by up to 90%.

Over more than a decade, researchers have studied a number of control and data plane attacks on BGP, the Internet's interdomain routing protocol, in the presence of malicious ASes. These prior efforts have largely focused on attacks that can be addressed using traditional cryptographic mechanisms to ensure authentication or integrity (e.g., S-BGP). Although augmenting BGP with authentication and integrity mechanisms is critical, it is far from sufficient to prevent attacks based on manipulating the complex BGP protocol itself. In this paper, we identify two serious protocol manipulation attacks that undermine the two most fundamental goals of the BGP control plane -- to ensure reachability and enable ASes to pick routes according to their routing policies -- despite the presence of S-BGP-like mechanisms. Our key contributions are to (1) formalize two critical security properties, (2) experimentally validate using commodity router implementations that BGP fails to achieve them, (3) quantify the extent of the resulting vulnerabilities in the Internet's AS topology, and (4) design and implement simple modifications to provably ensure that those properties are satisfied. Our experiments show that, a single malicious AS can cause thousands of other ASes to become disconnected from thousands of other ASes for arbitrarily long, while our proposed modifications almost completely eliminates such attacks.

Content Delivery Networks (CDNs) serve a large fraction of Internet traffic today improving user-perceived response time and availability of content. With tens of CDNs competing for content producers, it is important to understand the game played by these CDNs and whether the game is sustainable in the long term. In this paper, we formulate a game-theoretic model to analyze price competition among CDNs. Under this model, we propose an optimal strategy employed by two-CDN games. The strategy is incentive-compatible since any CDN that deviates from the strategy ends up with a lower utility. The strategy is also efficient since it produces a total utility that is at least two thirds of the social optimal utility. We formally derive the sufficient conditions for such a strategy to exist, and empirically show that there exists an optimal strategy for the games with more than two CDNs.

Several major Internet service providers today also offer content distribution services. The emergence of such "network-CDNs" (NCDNs) is driven both by market forces as well as the cost of carrying ever-increasing volumes of traffic across their backbones. An NCDN has the flexibility to determine both where content is placed and how traffic is routed within the network. However NCDNs today continue to treat traffic engineering independently from content placement and request redirection decisions. In this paper, we investigate the interplay between content distribution strategies and traffic engineering and ask whether or how an NCDN should address these concerns in a joint manner. Our experimental analysis, based on traces from a large content distribution network and real ISP topologies, shows that realistic (i.e., history-based) joint optimization strategies offer little benefit (and often significantly underperform) compared to simple and "unplanned" strategies for routing and placement such as InverseCap and LRU. We also find that the simpler strategies suffice to achieve network cost and user-perceived latencies close to those of a joint-optimal strategy with future knowledge.

BitTorrent, the immensely popular file swarming system, suffers a fundamental problem: content unavailability. Although swarming scales well to tolerate flash crowds for popular content, it is less useful for unpopular content as peers arriving after the initial rush find it unavailable. In this paper, we present a model to quantify content availability in swarming systems. We use the model to analyze the availability and the performance implications of bundling, a strategy commonly adopted by many BitTorrent publishers today. We find that even a limited amount of bundling exponentially reduces content unavailability. For swarms with highly unavailable publishers, the availability gain of bundling can result in a net decrease in average download time. We empirically confirm the model's conclusions through experiments on PlanetLab using the Mainline BitTorrent client.

We present BlockRate, a wireless bitrate adaptation algorithm designed for blocks, or large contiguous units of transmitted data, as opposed to small packets. Our work is motivated by the observation that recent research results suggest significant overhead amortization benefits of blocks. Yet state-of-the-art bitrate algorithms are optimized for adaptation on a per-packet basis, so they can either have the amortization benefits of blocks or high responsiveness to underlying channel conditions of packets, but not both.

The high replication cost of Byzantine fault-tolerance (BFT) methods has been a major barrier to their widespread adop-tion in commercial distributed applications. We present ZZ, a new approach that reduces the replication cost of BFT ser-vices from 2f + 1 to practically f + 1. The key insight in ZZ is to use f + 1 execution replicas in the normal case and to activate additional replicas only upon failures. In data cen-ters where multiple applications share a physical server, ZZ reduces the aggregate number of execution replicas running in the data center, improving throughput and response times. ZZ relies on virtualization—a technology already employed in modern data centers—for fast replica activation upon fail-ures, and enables newly activated replicas to immediately be-gin processing requests by fetching state on-demand. A pro-totype implementation of ZZ using the BASE library and Xen shows that, when compared to a system with 2f + 1 repli-cas, our approach yields lower response times and up to 33% higher throughput in a prototype data center with four BFT web applications. We also show that ZZ can handle simulta-neous failures and achieve sub-second recovery. 1

Traffic engineering (TE) has been long studied as a network optimization problem, but its impact on user-perceived application performance has received little attention. Our paper takes a first step to address this disparity. Using real traffic matrices and topologies from three ISPs, we conduct very large-scale experiments simulating ISP traffic as an aggregate of a large number of TCP flows. Our application-centric, empirical approach yields two rather unexpected findings. First, link utilization metrics, and MLU in particular, are poor predictors of application performance. Despite significant differences in MLU, all TE schemes and even a static shortest-path routing scheme achieve nearly identical application performance. Second, application adaptation in the form of location diversity, i.e., the ability to download content from multiple potential locations, significantly improves the capacity achieved by all schemes. Even the ability to download from just 2-4 locations enables all TE schemes to achieve near-optimal capacity, and even static routing to be within 30% of optimal. Our findings call into question the value of TE as practiced today, and compel us to significantly rethink the TE problem in the light of application adaptation.

Our work is motivated by a simple question: can we design a simple routing protocol that ensures robust performance across networks with diverse connectivity characteristics such as meshes, MANETs, and DTNs? We identify packet replication as a key structural difference between protocols designed for opposite ends of the connectivity spectrum---DTNs and meshes. We develop a model to quantify under what conditions and by how much replication improves packet delays, and use these insights to drive the design of R3, a routing protocol that self-adapts replication to the extent of uncertainty in network path delays. We implement and deploy R3 on a mesh testbed and a DTN testbed. To the best of our knowledge, R3 is the first routing protocol to be deployed and evaluated on both a DTN testbed and a mesh testbed. We evaluate its performance through deployment, trace-driven simulations, and emulation experiments. Our results show that R3 achieves significantly better delay and goodput over existing protocols in a variety of network connectivity and load conditions.

We investigate if WiFi access can be used to augment 3G capacity in mobile environments. We rst conduct a detailed study of 3G and WiFi access from moving vehicles, in three different cities. We find that the average 3G and WiFi availability across the cities is 87% and 11%, respectively. WiFi throughput is lower than 3G through-put, and WiFi loss rates are higher. We then design a system, called Wiffler, to augments mobile 3G capacity. It uses two key ideas leveraging delay tolerance and fast switching -- to overcome the poor availability and performance of WiFi. For delay tolerant applications, Wiffler uses a simple model of the environment to predict WiFi connectivity. It uses these predictions to delays transfers to offload more data on WiFi, but only if delaying reduces 3G usage and the transfers can be completed within the application's tolerance threshold. For applications that are extremely sensitive to delay or loss (e.g., VoIP), Wiffler quickly switches to 3G if WiFi is unable to successfully transmit the packet within a small time window. We implement and deploy Wiffler in our vehicular testbed. Our experiments show that Wiffler significantly reduces 3G usage. For a realistic workload, the reduction is 45% for a delay tolerance of 60 seconds.

BitTorrent, the immensely popular file swarming system, suffers a fundamental problem: unavailability. Although swarming scales well to tolerate flash crowds for popular content, it is less useful for unpopular or rare files as peers arriving after the initial rush find the content unavailable.

In this paper, we present a measurement study of the energy consumption characteristics of three widespread mobile networking technologies: 3G, GSM, and WiFi. We find that 3G and GSM incur a high tail energy overhead because of lingering in high power states after completing a transfer. Based on these measurements, we develop a model for the energy consumed by network activity for each technology.Using this model, we develop TailEnder, a protocol that reduces energy consumption of common mobile applications. For applications that can tolerate a small delay such as e-mail, TailEnder schedules transfers so as to minimize the cumulative energy consumed meeting user-specified deadlines. We show that the TailEnder scheduling algorithm is within a factor 2x of the optimal and show that any online algorithm can at best be within a factor 1.62x of the optimal. For applications like web search that can benefit from prefetching, TailEnder aggressively prefetches several times more data and improves user-specified response times while consuming less energy. We evaluate the benefits of TailEnder for three different case study applications - email, news feeds, and web search - based on real user logs and show significant reduction in energy consumption in each case. Experiments conducted on the mobile phone show that TailEnder can download 60% more news feed updates and download search results for more than 50% of web queries, compared to using the default policy.

Mobile Internet users have several options today including high bandwidth cellular data services such as 3G, that may be the choice for many. However, the ubiquity and low cost of WiFi suggests an attractive alternative, namely, opportunistic use of open WiFi access points (APs) or planned municipal mesh networks. Unfortunately, for vehicular users, the intermittent nature of WiFi connectivity makes it challenging to support popular interactive applications such as Web search and browsing.

We ask if the ubiquity of WiFi can be leveraged to provide cheap connectivity from moving vehicles for common applications such as Web browsing and VoIP. Driven by this question, we conduct a study of connection quality available to vehicular WiFi clients based on measurements from testbeds in two different cities. We find that current WiFi handoff methods, in which clients communicate with one basestation at a time, lead to frequent disruptions in connectivity. We also find that clients can overcome many disruptions by communicating with multiple basestations simultaneously. These findings lead us to develop ViFi, a protocol that opportunistically exploits basestation diversity to minimize disruptions and support interactive applications for mobile clients. ViFi uses a decentralized and lightweight probabilistic algorithm for coordination between participating basestations. Our evaluation using a two-month long deployment and trace-driven simulations shows that its link-layer performance comes close to an ideal diversity-based protocol. Using two applications, VoIP and short TCP transfers, we show that the link layer performance improvement translates to better application performance. In our deployment, ViFi doubles the number of successful short TCP transfers and doubles the length of disruption-free VoIP sessions compared to an existing WiFi-style handoff protocol.

Background transfers, or transfers that humans do not actively wait on, dominate the Internet today. In today's best-effort Internet, background transfers can interfere with foreground transfers causing long wait times, thereby hurting human productivity. In this paper, we present the design and implementation of a background network, Harp, that addresses this problem. Harp has three significant advantages over recent end-host based background transport protocols; Harp (i) uses multiple paths to exploit path diversity and load imbalance in the Internet to tailor network resource allocation to human needs, (ii) provides better fairness and utilization compared to unipath end-host protocols, and (ill) can be deployed at either end-hosts or enterprise gateways, thereby aligning the incentive for deployment with the goals of network customers. Our evaluation using simulations and a prototype on Planetlab suggests that Harp improves foreground TCP transfer time by a factor of five and background transfer time by a factor of two using just two extra paths per connection.

In this paper, we investigate the problem of highly available, massive-scale file distribution in the Internet. To this end, we conduct a large-scale measurement study of BitTorrent, a popular class of systems that use swarms of actively downloading peers to assist each other in file distribution. The first generation of BitTorrent systems used a central tracker to enable coordination among peers, resulting in low availability due to the tracker's single point of failure. Our study analyzes the prevalence and impact of two recent trends to improve BitTorrent availability: (i) use of multiple trackers, and (ii) use of Distributed Hash Tables (DHTs), both of which also help to balance load better. The study considered more than 1,400 trackers and 24,000 DHT nodes (extracted from about 20,000 torrents) over a period of two months. We find that both trends improve availability, but for different and somewhat unexpected reasons. Our findings include: (i) multiple trackers improve availability, but the improvement largely comes from the choice of a single highly available tracker, (ii) such improvement is reduced by the presence of correlated failures, (iii) multiple trackers can significantly reduce the connectivity of the overlay formed by peers, (iv) the DHT improves information availability, but induces a higher response latency to peer queries.

A fundamental challenge in Internet computing (IC) is to efficiently schedule computations having complex inter job dependencies, given the unpredictability of remote machines, in availability and time of access. The recent IC scheduling theory focuses on these sources of unpredictability by crafting schedules that maximize the number of executable jobs at every point in time. In this paper, we experimentally investigate the key question: does IC scheduling yield significant positive benefits for real IC? To this end, we develop a realistic computation model to match jobs to client machines and conduct extensive simulations to compare IC-optimal schedules against popular, intuitively compelling heuristics. Our results suggest that for a large range of computation-dags, client availability patterns, and two quite different performance metrics, IC-optimal schedules significantly outperform schedules produced by popular heuristics, by as much as 10-20%.

In this paper, we focus on a network of rich sensors that are geographically distributed and argue that the design of such networks poses very different challenges from traditional mote-class sensor network design. We identify the need to handle the diverse requirements of multiple users to be a major design challenge, and propose a utility-driven approach to maximize data sharing across users while judiciously using limited network and computational resources. Our utility-driven architecture addresses three key challenges for such rich multi-user sensor networks: how to define utility functions for networks with data sharing among end-users, how to compress and prioritize data transmissions according to its importance to end-users, and how to gracefully degrade end-user utility in the presence of bandwidth fluctuations. We instantiate this architecture in the context of geographically distributed wireless radar sensor networks for weather, and present results from an implementation of our system on a multi-hop wireless mesh network that uses real radar data with real end-user applications. Our results demonstrate that our progressive compression and transmission approach achieves an order of magnitude improvement in application utility over existing utility-agnostic non-progressive approaches, while also scaling better with the number of nodes in the network.

The emerging of rich sensor networks poses very different design challenges from traditional "mote-class" sensor networks. One important challenge is that these networks are designed to handle the diverse requirements of multiple users. In this work, we demonstrate how multiple end user needs are handled in rich sensor networks using a utility-driven architecture. We instantiate this architecture in the context of geographically distributed wireless radar sensor networks for weather, and demonstrate the real-time operation of the prototype on a radar testbed in Okalahoma.

Many DTN routing protocols use a variety of mechanisms, including discovering the meeting probabilities among nodes, packet replication, and network coding. The primary focus of these mechanisms is to increase the likelihood of finding a path with limited information, so these approaches have only an incidental effect on such routing metrics as maximum or average delivery latency. In this paper, we present RAPID, an intentional DTN routing protocol that can optimize a specific routing metric such as worst-case delivery latency or the fraction of packets that are delivered within a deadline. The key insight is to treat DTN routing as a resource allocation problem that translates the routing metric into per-packet utilities which determine how packets should be replicated in the system.

Several models have been recently proposed for predicting the latency of end to end Internet paths. These models treat the Internet as a black-box, ignoring its internal structure. While these models are simple, they can often fail systematically; for example, the most widely used models use metric embeddings that predict no benefit to detour routes even though half of all Internet routes can benefit from detours.In this paper, we adopt a structural approach that predicts path latency based on measurements of the Internet's routing topology, PoP connectivity, and routing policy. We find that our approach outperforms Vivaldi, the most widely used black-box model. Furthermore, unlike metric embeddings, our approach successfully predicts 65% of detour routes in the Internet. The number of measurements used in our approach is comparable with that required by black box techniques, but using traceroutes instead of pings.

We address a hierarchical generalization of the well-known disk paging problem. In the hierarchical cooperative caching problem, a set of n machines residing in an ultrametric space cooperate with one another to satisfy a sequence of read requests to a collection of (read-only) files. A seminal result in the area of competitive analysis states that LRU (the widely-used deterministic online paging algorithm based on the "least recently used" eviction policy) is constant-competitive if it is given a constant-factor blowup in capacity over the offline algorithm. Does such a constant-competitive deterministic algorithm (with a constant-factor blowup in the machine capacities) exist for the hierarchical cooperative caching problem? The main contribution of the present paper is to answer this question in the negative. More specifically, we establish an Ω(log log n) lower bound on the competitive ratio of any online hierarchical cooperative caching algorithm with capacity blowup O((log n)1-ε), where ε denotes an arbitrarily small positive constant.

We describe a new architecture for Byzantine fault tolerant state machine replication that separates agreement that orders requests from execution that processes requests. This separation yields two fundamental and practically significant advantages over previous architectures. First, it reduces replication costs because the new architecture can tolerate faults in up to half of the state machine replicas that execute requests. Previous systems can tolerate faults in at most a third of the combined agreement/state machine replicas. Second, separating agreement from execution allows a general privacy firewall architecture to protect confidentiality through replication. In contrast, replication in previous systems hurts confidentiality because exploiting the weakest replica can be sufficient to compromise the system. We have constructed a prototype and evaluated it running both microbenchmarks and an NFS server. Overall, we find that the architecture adds modest latencies to unreplicated systems and that its performance is competitive with existing Byzantine fault tolerant systems.

In this paper, we examine the bandwidth-constrained placement problem, focusing on trade-offs appropriate for wide area network (WAN) environments. The goal is to place copies of objects at a collection of distributed caches to minimize expected access times from distributed clients to those objects subject to a maximum bandwidth constraint at each cache. We develop a simple algorithm to generate a bandwidth-constrained placement by hierarchically refining an initial per-cache greedy placement. We prove that this hierarchical algorithm generates a placement whose expected access time is within a constant factor of the optimal placement's expected access time. We then proceed to extend this algorithm to compute close to optimal placement strategies for dynamic environments.