We propose a new traceroute tool, FlashRoute for efficient large-scale topology discovery. FlashRoute reduces the time required for tracerouting the entire /24 IPv4 address space by a factor of three and half compared to previous state of the art. Additionally, we present a new technique to measure hop-distance to a destination using a single probe and uncover a bias of the influential ISI Census hitlist [18] in topology discovery.

We present an automatic tool to approximate curved geometries with piece-wise developable surfaces. At the center of our work is an algorithm that wraps a given 3D input surface with multiple developable patches, each modeled as a discrete orthogonal geodesic net. Our algorithm features a global optimization routine for effectively finding the placement of the developable patches. After wrapping the mesh, we use these patches and a non-linear projection step to generate a surface that approximates the original input, but is also amendable to simple and efficient fabrication techniques thanks to being piecewise developable. Our algorithm allows users to steer the trade-off between approximation power and the number of developable patches used. We demonstrate the effectiveness of our approach on a range of 3D shapes. Compared to previous approaches, our results exhibit a smaller or comparable error with fewer patches to fabricate.

The advent of ultrabroadband Internet connectivity brings a 2-3 orders of magnitude jump in the capacity of access networks (a.k.a. the "last mile"). Beyond mere capacity increase, this leap represents a qualitative shift in the overall Internet environment. Therefore, we argue that only by seizing the opportunity to re-think the way we structure network applications and services can we realize the full potential ultrabroadband provides. Specifically, with ultrabroadband residential networks, we have the opportunity to re-center our digital lives around our residence, similar to how our physical lives generally center around our homes. To this end, we introduce a new appliance in home networks-a "home point of presence"-that provides a variety of services to the users in the house regardless of where they are physically located and connected to the network. We illustrate the utility of this appliance by discussing a range of new services that both bring new functionality to the users and improve performance of existing applications.

Content delivery networks (CDNs) commonly use DNS to map end-users to the best edge servers. A recently proposed EDNS0-Client-Subnet (ECS) extension allows recursive resolvers to include end-user subnet information in DNS queries, so that authoritative DNS servers, especially those belonging to CDNs, could use this information to improve user mapping. In this paper, we study the ECS behavior of ECS-enabled recursive resolvers from the perspectives of the opposite sides of a DNS interaction, the authoritative DNS servers of a major CDN and a busy DNS resolution service. We find a range of erroneous (i.e., deviating from the protocol specification) and detrimental (even if compliant) behaviors that may unnecessarily erode client privacy, reduce the effectiveness of DNS caching, diminish ECS benefits, and in some cases turn ECS from facilitator into an obstacle to authoritative DNS servers' ability to optimize user-to-edge-server mappings.

We present a computational framework for interactive design and exploration of curved folded surfaces. In current practice, such surfaces are typically created manually using physical paper, and hence our objective is to lay the foundations for the digitalization of curved folded surface design. Our main contribution is a discrete binary characterization for folds between discrete developable surfaces, accompanied by an algorithm to simultaneously fold creases and smoothly bend planar sheets. We complement our algorithm with essential building blocks for curved folding deformations: objectives to control dihedral angles and mountain-valley assignments. We apply our machinery to build the first interactive freeform editing tool capable of modeling bending and folding of complicated crease patterns.

It has been long observed that communication between a client and a content server using overlay detours may result in substantially better performance than a native path offered by IP routing. Yet the use of detours has been limited to distributed platforms such as Akamai. This paper poses a question - how can clients practically take advantage of overlay detours without modification to content servers (which are obviously outside clients' control)? We have posited elsewhere that the emergence of gigabit-to-the-home access networks would precipitate a new home network appliance, which would maintain permanent presence on the Internet for the users and have general computing and storage capabilities. Given such an appliance, our vision is that Internet users may form cooperatives in which members agree to serve as waypoints points to each other to improve each other's Internet experience. To make detours transparent to the server, we leverage MPTCP, which normally allows a device to communicate with the server on several network interfaces in parallel but we use it to communicate through external waypoint hosts. The waypoints then mimic MPTCP's subflows to the server, making the server oblivious to the overlay detours as long as it supports MPTCP.

We present a discrete theory for modeling developable surfaces as quadrilateral meshes satisfying simple angle constraints. The basis of our model is a lesser-known characterization of developable surfaces as manifolds that can be parameterized through orthogonal geodesics. Our model is simple and local, and, unlike in previous works, it does not directly encode the surface rulings. This allows us to model continuous deformations of discrete developable surfaces independently of their decomposition into torsal and planar patches or the surface topology. We prove and experimentally demonstrate strong ties to smooth developable surfaces, including a theorem stating that every sampling of the smooth counterpart satisfies our constraints up to second order. We further present an extension of our model that enables a local definition of discrete isometry. We demonstrate the effectiveness of our discrete model in a developable surface editing system, as well as computation of an isometric interpolation between isometric discrete developable shapes.

Discrete orthogonal geodesic nets (DOGs) are a quad mesh analogue of developable surfaces. In this work we study continuous deformations on these discrete objects. Our main theoretical contribution is the characterization of the shape space of DOGs for a given net connectivity. We show that generally, this space is locally a manifold of a fixed dimension, apart from a set of singularities, implying that DOGs are continuously deformable. Smooth flows can be constructed by a smooth choice of vectors on the manifold's tangent spaces, selected to minimize a desired objective function under a given metric. We show how to compute such vectors by solving a linear system, and we use our findings to devise a geometrically meaningful way to handle singular points. We base our shape space metric on a novel DOG Laplacian operator, which is proved to converge under sampling of an analytical orthogonal geodesic net. We further show how to extend the shape space of DOGs by supporting creases and curved folds and apply the developed tools in an editing system for developable surfaces that supports arbitrary bending, stretching, cutting, (curved) folds, as well as smoothing and subdivision operations.

We present a scalable approach for the optimization of flip-preventing energies in the general context of simplicial mappings and specifically for mesh parameterization. Our iterative minimization is based on the observation that many distortion energies can be optimized indirectly by minimizing a family of simpler proxy energies. Minimization of these proxies is a natural extension of the local/global minimization of the ARAP energy. Our algorithm is simple to implement and scales to datasets with millions of faces. We demonstrate our approach for the computation of maps that minimize a conformal or isometric distortion energy, both in two and three dimensions. In addition to mesh parameterization, we show that our algorithm can be applied to mesh deformation and mesh quality improvement.

With constant evolution of the Internet, many of its even well-established properties continue to change. This study re-evaluates the stability and diversity of Internet paths and whether it is affected by the widely deployed Multi-Protocol Label Switching (MPLS). In particular, using traceroutes between large number of source-destination pairs with the Internet Control Message Protocol (ICMP) extensions for the MPLS protocol, we study the stability and diversity of Internet paths as well as the amount of change in Round Trip Time (RTT) associated with a path change between a source-destination pair. Our results indicate that Internet routes are significantly less stable than previously reported. However, MPLS does not contribute significantly to this instability, and most path changes are associated with an insignificant change in RTT. While our route diversity results are not directly comparable with previous results, we find a great diversity of Internet routes: 60% of source-destination pairs in our experiments experienced 10 or more distinct routes in the course of 24 hours.

Today's Internet makes hosts and individual networks inherently insecure because permanent addresses turn destinations into permanent attack targets. This paper describes an Evasive Internet Protocol (EIP), a change to the data plane of the Internet that: 1) prevents senders from forging their identities while preserving the current Internet privacy paradigm; 2) gives recipients full control over who can communicate with them and for how long; 3) achieves the above features without requiring global signaling protocols; and 4) allows coexistence with and graceful introduction into the current Internet. We motivate our approach, present the architectural design, and evaluate it through trace-driven and synthetic simulations as well as prototype testing.

The Domain Name System (DNS) is a critical component of the Internet infrastructure that has many security vulnerabilities. In particular, shared DNS resolvers are a notorious security weak spot in the system. We propose an unorthodox approach for tackling vulnerabilities in shared DNS resolvers: removing shared DNS resolvers entirely and leaving recursive resolution to the clients. We show that the two primary costs of this approach---loss of performance and an increase in system load---are modest and therefore conclude that this approach is beneficial for strengthening the DNS by reducing the attack surface.

The Domain Name System (DNS) is a critical component of the Internet infrastructure. It allows users to interact with Web sites using human-readable names and provides a foundation for transparent client request distribution among servers in Web platforms, such as content delivery networks. In this paper, we present methodologies for efficiently discovering the complex client-side DNS infrastructure. We further develop measurement techniques for isolating the behavior of the distinct actors in the infrastructure. Using these strategies, we study various aspects of the client-side DNS infrastructure and its behavior with respect to caching, both in aggregate and separately for different actors.

We present a large-scale measurement of clusters of hosts sharing the same local DNS servers. We analyze properties of these "LDNS clusters" from the perspective of content delivery networks, which commonly use DNS for load distribution. We found that not only LDNS clusters differ widely in terms of their size and geographical compactness but that the largest clusters are actually extremely compact. This suggests potential benefits of a load distribution strategy with nuanced treatment of different LDNS clusters based on the combination of their size and compactness. We further observed interesting variations in LDNS setups including a wide use of "LDNS pools" (which as we explain in the paper are different from setups where end-hosts simply utilize multiple resolvers).

This paper discusses a way to communicate without relying on fixed infrastructure at some central hub. This can be useful for bootstrapping loosely connected peer-to-peer systems, as well as for circumventing egregious policy-based blocking (e.g., for censorship purposes). Our techniques leverage the caching and aging properties of DNS records to create a covert channel of sorts that can be used to store ephemeral information. The only requirement imposed on the actors wishing to publish and/or retrieve this information is that they share a secret that only manifests outside the system and is never directly encoded within the network itself. We conduct several experiments that illustrate the efficacy of our techniques to exchange an IP address that is presumed to be a rendezvous point for future communication.

This paper provides an indication that the distance between clients and their local DNS servers (LDNS) can have a significant negative impact on the performance of content delivery networks (CDNs). Consequently, we propose a novel peer-topeer client-side DNS mechanism that moves LDNS close to their clients while still allowing nearby clients to share the common DNS cache. Through trace-driven simulations and prototype testing, we show that our approach holds significant promise of facilitating better server selection by CDNs.

Content delivery networks (CDNs) have become a crucial part of the modern Web infrastructure. This paper studies the performance of the leading content delivery provider - Akamai. It measures the performance of the current Akamai platform and considers a key architectural question faced by both CDN designers and their prospective customers: whether the co-location approach to CDN platforms adopted by Akamai, which tries to deploy servers in numerous Internet locations, brings inherent performance benefits over a more consolidated data center approach pursued by other influential CDNs such as Limelight. We believe the methodology we developed for this study will be useful for other researchers in the CDN arena.

IP Anycast has many attractive features for any service that involve the replication of multiple instances across the Internet. IP Anycast allows multiple instances of the same service to be “naturally” discovered, and requests for this service to be delivered to the closest instance. However, while briefly considered as an enabler for content delivery networks (CDNs) when they first emerged, IP Anycast was deemed infeasible in that environment. The main reasons for this decision were the lack of load awareness of IP Anycast and unwanted side effects of Internet routing changes on the IP Anycast mechanism. In this article we re-evaluate IP Anycast for CDNs by proposing a load-aware IP Anycast CDN architecture. Our architecture is prompted by recent developments in route control technology, as well as better understanding of the behavior of IP Anycast in operational settings. Our architecture makes use of route control mechanisms to take server and network load into account to realize load-aware Anycast. We show that the resulting redirection requirements can be formulated as a Generalized Assignment Problem and present practical algorithms that address these requirements while at the same time limiting connection disruptions that plague regular IP Anycast. We evaluate our algorithms through trace based simulation using traces obtained from a production CDN network.

Multicast is an approach that uses network and server resources efficiently to distribute information to groups. As networks evolve to become information-centric, users will increasingly demand publish-subscribe based access to fine-grained information, and multicast will need to evolve to (i) manage an increasing number of groups, with a distinct group for each piece of distributable content; (ii) support persistent group membership, as group activity can vary over time, with intense activity at some times, and infrequent (but still critical) activity at others. These requirements raise scalability challenges that are not met by today's multicast techniques. In this paper, we propose the MAD (multicast with adaptive dual-state) architecture to provide efficient multicast service at massive scale. MAD can scalably support a vast number of multicast groups, with varying activity over time, based on two key novel ideas: (i) decouple group membership from forwarding information, and (ii) apply an adaptive dual-state approach to optimize for the different objectives of active and inactive groups. We focus on the scalability characteristics of MAD and demonstrate through analysis, simulation and implementation that the architecture achieves high performance and efficiency.

Web hosting providers are increasingly looking into dynamic hosting to reduce costs and improve the performance of their platforms. Instead of provisioning fixed resources to each customer, dynamic hosting maintains a variable number of application instances to satisfy current demand. While existing research in this area has mostly focused on the algorithms that decide on the number and location of application instances, we address the problem of efficient enactment of these decisions once they are made. We propose a new approach to application placement and experimentally show that it dramatically reduces the cost of application placement, which in turn improves the end-to-end agility of the hosting platform in reacting to demand changes.

Anycast-based content delivery networks (CDNs) have many properties that make them ideal for the large scale distribution of content on the Internet. However, because routing changes can result in a change of the endpoint that terminates the TCP session, TCP session disruption remains a concern for anycast CDNs, especially for large file downloads. In this paper we demonstrate that this problem does not require any complex solutions. In particular, we present the design of a simple, yet efficient, mechanism to handle session disruptions due to endpoint changes. With our mechanism, a client can continue the download of the content from the point at which it was before the endpoint change. Furthermore, CDN servers purge the TCP connection state quickly to handle frequent switching with low system overhead.

This paper describes an efficient and accurate approach to estimate the network distance between arbitrary Internet hosts. We use three landmark hosts forming a triangle in two-dimensional space to estimate the distance between arbitrary hosts with simple trigonometrical calculations. To improve the accuracy of estimation, we dynamically choose the best triangle for a given pair of hosts using a heuristic algorithm. Our experiments show that this approach achieves both lower computational and network probing cost over the classic landmarks-based approach while producing more accurate estimates.

Because it is an integral part of the Internet routing apparatus, and because it allows multiple instances of the same service to be "naturally" discovered, IP Anycast has many attractive features for any service that involve the replication of multiple instances across the Internet. While briefly considered as an enabler when content distribution networks (CDNs) first emerged, the use of IP Anycast was deemed infeasible in that environment. The main reasons for this decision were the lack of load awareness of IP Anycast and unwanted side effects of Internet routing changes on the IP Anycast mechanism. Prompted by recent developments in route control technology, as well as a better understanding of the behavior of IP Anycast in operational settings, we revisit this decision and propose a load-aware IP Anycast CDN architecture that addresses these concerns while benefiting from inherent IP Anycast features. Our architecture makes use of route control mechanisms to take server and network load into account to realize load-aware Anycast. We show that the resulting redirection requirements can be formulated as a Generalized Assignment Problem and present practical algorithms that address these requirements while at the same time limiting session disruptions that plague regular IP Anycast. We evaluate our algorithms through trace based simulation using traces obtained from an operation CDN network.

This paper describes our implementation of and initial experiences with DipZoom (for "Deep Internet Performance Zoom"), a novel approach to provide focused, on-demand Internet measurements. Unlike existing approaches that face a difficult challenge of building a measurement platform with sufficiently diverse measurements and measuring hosts, DipZoom implements a matchmaking service instead, which uses P2P concepts to bring together experimenters in need of measurements with external measurement providers. DipZoom offers the following two main contributions. First,since it is just a facilitator for an open community of participants, it promises unprecedented availability of diverse measurements and measuring points. Second, it can be used as a veneer over existing measurement platforms, automating the planning and execution of complex measurements.

This paper presents the architecture and the preliminary evaluation ofa request routing DNS server that decouples server selectionfrom the rest of DNS functionality. Our DNS server, which we refer toas MyXDNS, exposes well-defined APIs for uploading an externallycomputed server selection policy and for interacting with an external networkproximity service. With MyXDNS, researchers can explore their ownnetwork proximity metrics and request routing algorithms withouthaving to worry about DNS internals. Furthermore, MyXDNS is based onopen-source MyDNS and is available to public. Stress-testing of MyXDNSindicated that it achieves its flexibility at an acceptable cost: asingle MyXDNS running on a low-level server can process 3000 req/secwith sub-millisecond response even in the presence of continuousupdates to server selection policy.

This paper studies the conditions under which P2P sharing can increase the capacity of IPTV services over FTTN networks. For a typical FTTN network, our study shows a) P2P sharing is not beneficial when the total traffic in a local video office is low; b) P2P sharing increases the load on FTTN switches and routers in local video offices; c) P2P sharing is the most beneficial when the network bottleneck is experienced in the southbound segment of a local video office (equivalently a northbound segment of an FTTN switch); and d) sharing among all FTTN serving communities is not needed when network congestion problems are solved by using some other technologies such as program pre-caching or replication. Based on the analytical results, design for IPTV services which monitors FTTN network conditions and decides when and how to share videos among peers to maximize the service capacity. Simulations and bounds both validate the potential benefits of the MediaGrid IPTV service platform.

We describe DipZoom (for "deep Internet performance zoom"), an approach to provide focused, on-demand Internet measurements. Unlike existing approaches that face a difficult challenge of building a measurement platform with sufficiently diverse measurements and measuring hosts, DipZoom offers a matchmaking service instead, which uses P2P concepts to bring together experimenters in need of measurements with external measurement providers. It then harnesses market forces to orchestrate the supply and demand sides in the resulting open eco-system. This paper outlines the overall design of DipZoom, and discusses payment, trust and security issues in the resulting open system.

In file-sharing P2P networks, a fundamental problem is that of identifying databases that are relevant to user queries. This problem is referred to as the location problem in P2P literature. We propose a scalable solution to the location problem in a data-sharing P2P network, consisting of a network of XML database nodes and XML router nodes, and make the following contributions. We develop the internal organization and routing protocols for the XML router nodes, to enable scalable XPath query and update processing, under the open and the agreement cooperation models between nodes. Since router nodes tend to be memory constrained, we facilitate a space/performance tradeoff by permitting aggregated routing states, and developing algorithms for generating and using such aggregated information. We experimentally demonstrate the scalability of our approach, and the performance of our query and update protocols, using a detailed simulation model, varying key design parameters.

This paper presents a systematic study of the properties of a large number of Web sites hosted by a major ISP. To our knowledge, ours is the first comprehensive study of a large server farm that contains thousands of commercial Web sites. We also perform a simulation analysis to estimate potential performance benefits of content delivery networks (CDNs) for these Web sites, and validate our analysis for several sites by replaying our trace through a real cache. We make several interesting observations about the current usage of Web technologies and Web site performance characteristics. First, compared with previous client workload studies, the Web server farm workload contains a much higher degree of uncacheable responses and responses that require mandatory cache validations. A significant reason for this is that cookie use is prevalent among our population, especially among more popular sites. We found an indication of widespread indiscriminate usage of cookies, which unnecessarily impedes the use of many content delivery optimizations. We also found that most Web sites do not utilize the cache-control features of the HTTP 1.1 protocol, resulting in suboptimal performance. Moreover, the implicit expiration time in client caches for responses is strongly constrained by the maximum values allowed in the Squid proxy. Thus, supplying explicit expiration information would significantly improve Web sites'

Today's HTTP carries Web interactions over client-initiated TCP connections. An important implication of using this transport method is that interception caches in the network violate the end-to-end principle of the Internet, which severely limits deployment options of these caches. Furthermore, while an increasing number of Web interactions are short, and in fact frequently carry only control information and no data, TCP is often inefficient for short interactions We propose a new transfer protocol for the Web, called Dual-Transport HTTP (DHTTP), which splits the traffic between UDP and TCP channels. When choosing the TCP channel, it is the server who opens the connection back to the client. Through server-initiated connections, DHTTP upholds the Internet end-to-end principle in the presence of interception caches, thereby allowing unrestricted caching within backbones. Moreover, the comparative performance study of DHTTP and HTTP using trace-driven simulation as well as testing real HTTP and DHTTP servers showed a significant performance advantage of DHTTP when the bottleneck is at the server and comparable performance when the bottleneck is in the network.

With a key component of latency on the Web being connection set up between clients and Web servers, several ways to avoid connections have been explored. While the work in recent years on Content Distribution Networks (CDNs) have moved some content 'closer' to users at the cost of increasing DNS traffic, they have not fully exploited the available unused potential of existing protocols. We explore ways by which a variety of Web responses can be piggybacked on DNS messages. While we evaluated our idea in the Web context, the approach is generic and not restricted to Web responses. We propose an architecture for HTTP piggybacking in DNS messages and carry out a detailed performance analysis based on a trace-driven simulation study. Our architecture requires minimal extensions to existing protocols, utilizing only the allowed optional fields for these extensions. It is fully compatible and can coexist with the current Web.

No abstract available.

The paper studies two types of events that often overload Web sites to a point when their services are degraded or disrupted entirely - flash events (FEs) and denial of service attacks (DoS). The former are created by legitimate requests and the latter contain malicious requests whose goal is to subvert the normal operation of the site. We study the properties of both types of events with a special attention to characteristics that distinguish the two. Identifying these characteristics allows a formulation of a strategy for Web sites to quickly discard malicious requests. We also show that some content distribution networks (CDNs) may not provide the desired level of protection to Web sites against flash events. We therefore propose an enhancement to CDNs that offers better protection and use trace-driven simulations to study the effect of our enhancement on CDNs and Web sites.

Today's Web interactions are frequently short, with an increasing number of responses carrying only control information and no data. While HTTP uses client-initiated TCP for all Web interactions, TCP is not always well-suited for short interactions. Furthermore, client-initiated TCP handicaps the deployment of interception caches in the network because of the possibility of disrupted connections when some client packets bypass the cache on their way to the server. We propose a new transfer protocol for Web traffic, called dual-transport HTTP (DHTTP), which splits the traffic between UDP and TCP channels. When choosing the TCP channel, it is the server who opens the connection back to the client. Among important aspects of DHTTP are adapting to bottleneck shifts between a server and the network and coping with the unreliable nature of UDP. The comparative performance study of DHTTP and HTTP using trace-driven simulation as well as testing real HTTP and DHTTP servers showed a significant performance advantage of DHTTP when the bottleneck is at the server and comparable performance when the bottleneck is in the network. By using server-initiated TCP, DHTTP also eliminates the possibility of disrupted TCP connections in the presence of interception caches thereby allowing unrestricted caching within backbones.

This paper proposes a protocol suite for dynamic replication and migration of Internet objects. It consists of an algorithm for deciding on the number and location of object replicas and an algorithm for distributing requests among currently available replicas. Our approach attempts to place replicas in the vicinity of a majority of requests while ensuring at the same time that no servers are overloaded. The request distribution algorithm uses the same simple mechanism to take into account both server proximity and load, without actually knowing the latter. The replica placement algorithm executes autonomously on each node, without the knowledge of other object replicas in the system. The proposed algorithms rely on the information available in databases maintained by Internet routers. A simulation study using synthetic workloads and the network backbone of UUNET, one of the largest Internet service providers, shows that the proposed protocol is effective in eliminating hot spots and ...

Much work on the performance of Web proxy caching has focused on high-level metrics such as hit rates, but has ignored low level details such as "cookies", aborted connections, and persistent connections between clients and proxies as well as between proxies and servers. These details have a strong impact on performance, particularly in heterogeneous bandwidth environments where network speeds between clients and proxies are significantly different than speeds between proxies and servers. We evaluate through detailed simulations the latency and bandwidth effects of Web proxy caching in such environments. We drive our simulations with packet traces from two scenarios: clients connected through slow dialup modems to a commercial ISP, and clients on a fast LAN in an industrial research lab. We present three main results. First, caching persistent connections at the proxy can improve latency much more than simply caching Web data. Second, aborted connections can waste more bandwidth than that saved by caching data. Third, cookies can dramatically reduce hit rates by making many documents effectively uncacheable.

We present an efficient protocol for multi-version concurrency control in distributed databases. The protocol creates no more than three versions of any data item, while guaranteeing that: update transactions never interfere with read-only transactions; the version advancement mechanism is completely asynchronous with (both update and read-only) user transactions; and read-only transactions do not acquire locks and do not write control information into the data items being read. This is an improvement over existing multi-versioning schemes for distributed databases, which either require a potentially unlimited number of versions, or require coordination between version advancement and user transactions. Our protocol can be applied in a centralized system also, where the improvement over existing techniques is in reducing the number of versions from four to three. The proposed protocol is valuable in large applications that currently shut off access to the system while managing version advancement manually, but now have a need for automating this process and providing continuous access to the data.

The title of this panel alludes to the comment by David DeWitt at VLDB-95 that the database community missed its opportunity to contribute to the Internet revolution. The plan is to discuss if there was the boat to begin with, and if so, can we still jump on it. Consequently, broad questions we will try to address include: If WWW did not exist and we were just designing it now, what would we do differently? In today' s WWW, what are research areas where the database community could contribute?

Presents a multiversioning scheme for a distributed system with the workload consisting of read-only transactions and update transactions, (most of) which commute on individual nodes. The scheme introduces a version advancement protocol that is completely asynchronous with user transactions, thus allowing the system to scale to very high transaction rates and frequent version advancements. Moreover, the scheme never creates more than three copies of a data item. Combined with existing techniques to avoid global concurrency control for commuting transactions that execute in a particular version, our multiversioning scheme results in a protocol where no user transaction on a node can be delayed by any activity (either version advancement or another transaction) occurring on another node. Non-commuting transactions are gracefully handled. Our technique is of particular value to distributed recording systems where guaranteeing global serializability is often desirable, but rarely used because of the high performance cost of running distributed transactions. Examples include calls on a telephone network, inventory management in a "point-of-sale" system, operations monitoring systems in automated factories, and medical information management systems.

We present a new replica control technique targeted at replicated systems in which write operations update a portion of the information in the data item rather than replacing it entirely. The existing protocols capable of supporting partial writes must either perform the writes on all accessible replicas of the data item, or always apply the writes to the same group (quorum set) of replicas. In the former case, the system incurs high message overhead. In the latter case, if any of the replicas in this group fail, additional replicas must be synchronously brought up-to-date during the write operation causing delay to the operation. Also, in both cases, the system loses the advantage of load sharing provided by replication. Our protocol avoids performing the write on all nodes while preserving load sharing and reducing greatly the risk of having to propagate updates synchronously. We describe the protocol, prove it correct, and present a comparative performance study of our protocol and the existing alternatives.>

Recently, there has been considerable interest in the study of replica-control protocols which are based on organizing several copies of an object into logical structures, such as rectangular grids. In addition to high availability, another objective in exploiting such structures is to improve the degree of load sharing in a system. The authors extend the scope of grid structures to general grids, which allow holes in various positions of a rectangular structure and are useful to consider because they often produce availabilities that are higher than solid grids, where every position must be occupied by a node. In addition to proposing an improvement to the existing grid protocol, new insights are offered into the performance of the grids, from both availability and load sharing points of view. Algorithms for designing grids to maximize availability independently and also in conjunction with a load sharing constraint are given.>

When failures occur during the execution of distributed commit protocols, the protocols may block in some partitions to avoid inconsistent termination of the transaction, thus making data items in these partitions unavailable for accesses. We present a protocol that incorporates two new ideas with the goal of improving data availability. First, a new two-level voting scheme is proposed for deciding in which partitions to terminate the transaction. In this scheme, a choice is made based on the number of data items available in the partition rather than on the number of individual nodes. Indeed, in replicated systems, a criterion based on the number of nodes may be misleading. Second, we propose a way to reduce blocking caused by accumulating network fragmentation. The idea employs the views mechanism previously used in replica management.

This paper presents a new technique for efficiently controlling replicas in distributed systems. Conventional structured coterie protocols are efficient but incur a penalty of reduced availability in exchange for the performance gain. Further, the performance advantage can only be fully realized when write operations always replace the old data item with the new value instead of updating a portion of the data item. Our new approach significantly improves availability while allowing partial write operations.