In this paper, we present O3, a social link based private storage cloud for decentralized collaboration. O3allows users to share and collaborate on collections of files (shared folders) with others, in a decentralized manner, without the need for intermediaries (such as public cloud storage servers) to intervene. Thus, users can keep their working relationships (who they work with) and what they work on private from third parties. Using benchmarks and traces from real workloads, we experimentally evaluate O3and demonstrate that the system scales linearly when synchronizing increasing numbers of concurrent users, while performing on-par with the ext4 non-version-tracking filesystem.

In this paper, we present O3REAL, a privacy-preserving distributed middleware for real-time collaborative editing of documents. O3REAL introduces a novel approach for building peer-to-peer real-time collaborative applications, using a reliable broadcast channel mechanism for network communication, but at the same time provides for persistent storage management of collaborative documents using the filesystem interface of a POSIX compliant filesystem. This approach enables real-time, completely decentralized collaboration among users, without the need for a third party to intervene, and significantly simplifies the creation of peer-to-peer collaborative applications. We demonstrate that O3REAL scales well for real-time collaboration use-cases. For example, with 33 users simultaneously collaborating on a document in real time over a WAN with a 50 ms link delay, the average perceived latency is approximately 54 ms, which is very close to the optimal baseline. In comparison, Etherpad exhibits nearly twice the perceived latency.

Online publishing of news and information enables important content to reach a much larger audience than traditional paper publishing, but there is no guarantee of long-term, reliable, and persistent access to the content. Over time, links "decay" because they are not reliably updated when content changes location, or even worse, content is deliberately altered from its original published form or deleted altogether. We present the design of Watchdog, a permissioned distributed ledger that securely and reliably monitors and preserves dynamic web content such as government and news sites. Unlike prior preservation systems, our system design allows nodes to be dispersed across multiple administrative domains, thus eliminating single points of trust and at the same time, is the first to monitor how content changes both over time and across geographical location. Watchdog achieves Byzantine fault-tolerance via a novel interactive consistency algorithm that offers a twist on the traditional definition and use of interactive consistency; the algorithm enables a set of mutually suspicious nodes, with arbitrary-sized, potentially overlapping data collections, to efficiently agree on the exact data collection in possession by each node. We demonstrate how our algorithm enables Watchdog nodes to exchange and agree upon the content each has observed individually, in a fault-tolerant, tamper-proof manner.

Asynchronous rumor spreading, or epidemic algorithms, are a class of data dissemination protocols that have been used throughout the years for a large variety of distributed applications. The emergence of large-scale, public blockchains, such as Bitcoin and Ethereum, has reinvigorated research interest in these protocols as they are employed to disseminate pending transactions and confirmed blocks in their peer-to-peer (P2P) networks. Efficient, timely and fault-tolerant information dissemination is vital for blockchain networks as it affects issues ranging from security to block finality. Recent works have analyzed the structural properties of blockchain network overlay graphs. Their findings show that they have inherent similarities to those of social networks, such as power-law degree distributions, small diameters and star-like communities. In this work, we present an experimental analysis of the vanilla asynchronous push & pull rumor spreading protocol that is employed by public blockchains. This protocol, although robust and scalable, can be substantially improved. We demonstrate this by analyzing the effect that multiple parameters have on the protocol's performance, such as using memory to avoid contacting the same neighbor twice in a row, varying the stopping criteria of nodes to decide when to stop spreading the rumor, employing more sophisticated neighbor selection policies instead of the standard uniform random choice and others. Prior works have focused on either providing theoretical upper bounds on the number of rounds needed to spread the rumor to all nodes, or, propose improvements by adjusting isolated parameters. To our knowledge, our work is the first to study how multiple parameters affect the protocol's behavior both in isolation and combination and under a wide range of values. Moreover, prior theoretical works have studied rumor spreading only on bidirectional social topologies. Our study examines the behavior of the protocol in multiple topology classes. These include bidirectional, directed, and also a special type of social topologies, called signed topologies, which resemble more closely the topologies of blockchain P2P networks. Our work is the first to indicate and deal with how chains of communities that are sparsely connected to the core of the network can hamper the rumor's spreading. Thus, we complement prior theoretical work to shed light on how the protocol behaves in practical, real-world, large scale distributed systems. Finally, through our detailed analysis, we demonstrate how a few simple additions to the protocol deliver a percentage decrease of the time required to inform all nodes by a maximum of 99.69% and an average of 86.04%.

Modern computer systems now feature memory banks whose aggregate size ranges from tens to hundreds of GBs. In this context, contemporary workloads can and do often consume vast amounts of main memory. This upsurge in memory consumption routinely results in increased virtual-to-physical address translations, and consequently and more importantly, more translation misses. Both of these aspects collectively do hamper the performance of workload execution. A solution aimed at dramatically reducing the number of address translation misses has been to provide hardware support for pages with bigger sizes, termed huge pages. In this paper, we empirically demonstrate the benefits and drawbacks of using such huge pages. In particular, we show that it is essential for modern OS to refine their software mechanisms to more effectively manage huge pages. Based on our empirical observations, we propose and implement MEGA, a framework for huge page support for the Linux kernel. MEGA deploys basic tracking mechanisms and a novel memory compaction algorithm that jointly provide for the effective management of huge pages. We experimentally evaluate MEGA using an array of both synthetic and real workloads and demonstrate that our framework tackles known problems associated with huge pages including increased page fault latency, memory bloating as well as memory fragmentation, while at the same time it delivers all huge pages benefits.

We present the “It's My Data file system” (IMDfs), a personal, version-tracking, distributed file system that allows users to take custody of their cross-device data management needs, without depending on cloud storage providers. Such a system may be desirable to privacy-conscious users, who worry about the increasing number of cloud storage incidents involving data leakage and corruption, or simply want to synchronize their devices without depending on third parties. IMDfs provides a global, unified view of a user's distributed data collection from any device, user-controlled replication of data across devices, transparent remote access, and support for non-restrictive conflict management. IMDfs achieves all this without sacrificing fault-tolerance or performance and with modest storage overhead. We present the design, implementation, and detailed performance evaluation of IMDfs using benchmarks and traces from real workloads, and we demonstrate that: 1) IMDfs, as a local file system, has reasonable overhead compared with a FUSE loopback file system and Wayback, a local versioning file system, and 2) IMDfs, as a network file system, outperforms NFS and Ori, a state-of-the-art file system for cross-device data management.

Summary Digital repositories must periodically check the integrity of stored objects to assure users of their correctness. Prior solutions calculate integrity metadata and require the repository to store it alongside the actual data objects. To safeguard and detect damage to this metadata, prior solutions rely on widely visible media (unaffiliated third parties) to store and provide back digests of the metadata to verify it is intact. However, they do not address recovery of the integrity metadata in case of damage or adversarial attack. We introduce IntegrityCatalog, a novel software system that can be integrated into any digital repository. It collects all integrity‐related metadata in a single component and treats them as first class objects, managing both their integrity and their preservation. We introduce a treap‐based persistent authenticated dictionary managing arbitrary length key/value pairs, which we use to store all integrity metadata, accessible simply by object name. Additionally, IntegrityCatalog is a distributed system that includes a network protocol that manages both corruption detection and preservation of this metadata, using administrator‐selected network peers with 2 possible roles. Verifiers store and offer attestations on digests and have minimal storage requirements, while preservers efficiently synchronize a complete copy of the catalog to assist in recovery in case of a detected catalog compromise on the local system. We present our approach in developing the prototype implementation, measure its performance experimentally, and demonstrate its effectiveness in real‐world situations. We believe the implementation techniques of our open‐source IntegrityCatalog will be useful in the construction of next‐generation digital repositories.

Live VMmigration helps attain both cloud-wide load balancing and operational consolidation while the migrating VMs remain accessible to users. To avoid periods of high-load for the involved resources, IaaS-cloud operators assign specific time windows for such migrations to occur in an orderly manner. Moreover, providers typically rely on share-nothing architectures to attain scalability. In this paper, we focus on the real-time scheduling of live VM migrations in large share-nothing IaaS clouds, such that migrations are completed on time and without adversely affecting agreed-upon SLAs. We propose a scalable, distributed network of brokers that oversees the progress of all on-going migration operations within the context of a provider. Brokers make use of an underlying special purpose file system, termed MigrateFS, that is capable of both replicating and keeping in sync virtual disks while the hypervisor livemigrates VMs (i.e., RAM and CPU state). By limiting the resources consumed during migration, brokers implement policies to reduce SLA violations while seeking to complete all migration tasks on time. We evaluate two such policies, one based on task prioritization and a second that considers the financial implications set by migration deadline requirements. Using our MigrateFS prototype operating on a real cloud, we demonstrate the feasibility of performing migrations within time windows. By simulating large clouds, we assess the effectiveness of our proposed broker policies in a share-nothing configuration; we also demonstrate that our approach stresses 24 percent less an already saturated network if compared to an unsupervised set up.

E-voting systems have emerged as a powerful technology for improving democracy by reducing election cost, increasing voter participation, and even allowing voters to directly verify the entire election procedure. Prior internet voting systems have single points of failure, which may result in the compromise of availability, voter secrecy, or integrity of the election results. In this paper, we present the design, implementation, security analysis, and evaluation of D-DEMOS, a complete e-voting system that is distributed, privacy-preserving and end-to-end verifiable. Our system includes a fully asynchronous vote collection subsystem that provides immediate assurance to the voter her vote was recorded as cast, without requiring cryptographic operations on behalf of the voter. We also include a distributed, replicated and fault-tolerant Bulletin Board component, that stores all necessary election-related information, and allows any party to read and verify the complete election process. Finally, we also incorporate trustees, i.e., individuals who control election result production while guaranteeing privacy and end-to-end-verifiability as long as their strong majority is honest. Our system is the first e-voting system whose voting operation is human verifiable, i.e., a voter can vote over the web, even when her web client stack is potentially unsafe, without sacrificing her privacy, and still be assured her vote was recorded as cast. Additionally, a voter can outsource election auditing to third parties, still without sacrificing privacy. Finally, as the number of auditors increases, the probability of election fraud going undetected is diminished exponentially. We provide a model and security analysis of the system. We implement a prototype of the complete system, we measure its performance experimentally, and we demonstrate its ability to handle large-scale elections.

Interactive consistency is the problem in which n nodes, where up to t may be byzantine, each with its own private value, run an algorithm that allows all non-faulty nodes to infer the values of each other node. This problem is relevant to critical applications that rely on the combination of the opinions of multiple peers to provide a service. Examples include monitoring a content source to prevent equivocation or to track variability in the content provided, and resolving divergent state amongst the nodes of a distributed system. Previous works assume a fully synchronous system, where one can make strong assumptions such as negligible message delivery delays and/or detection of absent messages. However, practical, real-world systems are mostly asynchronous, i.e., they exhibit only some periods of synchrony during which message delivery is timely, thus requiring a different approach. In this paper, we present a thorough study on practical interactive consistency. We leverage the vast prior work on broadcast and byzantine consensus algorithms to design, implement and evaluate a set of algorithms, with varying timing assumptions and message complexity, that can be used to achieve interactive consistency in real-world distributed systems. We provide a complete, open-source implementation of each proposed interactive consistency algorithm by building a multi-layered stack of protocols that include several broadcast protocols, as well as a binary and a multi-valued consensus protocol. Most of these protocols have never been implemented and evaluated in a real system before. We analyze the performance of our suite of algorithms experimentally by engaging in both single instance and multiple parallel instances of each alternative.

Both economic reasons and interoperation requirements necessitate the deployment of IaaS-clouds based on a share-nothing architecture. Here, live VM migration becomes a major impediment to achieving cloud-wide load balancing via selective and timely VM-migrations. Our approach is based on copying virtual disk images and keeping them synchronized during the VM migration operation. In this way, we ameliorate the limitations set by shared storage cloud designs as we place no constraints on the cloud's scalability and load-balancing capabilities. We propose a special-purpose file system, termed MigrateFS, that performs virtual disk replication within specified time-constraints while avoiding internal network congestion. Management of resource consumption during VM migration is supervised by a low-overhead and scalable distributed network of brokers. We show that our approach can reduce up to 24% the stress of already saturated physical network links during load balancing operations.

One of the most appealing characteristics of unstructured P2P overlays is their enhanced self-* properties, which results from their loose, random structure. In addition, most of the algorithms which make searching in unstructured P2P systems scalable, such as dynamic querying and 1-hop replication, rely on the random nature of the overlay to function efficiently. The underlying communications network (i.e., the Internet), however, is not as randomly constructed. This leads to a mismatch between the distance of two peers on the overlay and the hosts they reside on at the IP layer, which in turn leads to its misuse. The crux of the problem arises from the fact that any effort to provide a better match between the overlay and the IP layer will inevitably lead to a reduction in the random structure of the P2P overlay, with many adverse results. With this in mind, we propose ITA, an algorithm which creates a random overlay of randomly connected neighborhoods providing topology awareness to P2P systems, while at the same time has no negative effect on the self-* properties or the operation of the other P2P algorithms. Using extensive simulations, both at the IP router level and autonomous system level, we show that ITA reduces communication latencies by as much as 50 percent. Furthermore, it not only reduces by 20 percent the number of IP network messages which is critical for ISPs carrying the burden of transporting P2P traffic, but also distributes the traffic load more evenly on the routers of the IP network layer.

Infrastructure-as-a-Service clouds offer entire virtual infrastructures for distributed processing while concealing all physical underlying machinery. Current cloud interface abstractions restrict users from providing information regarding usage patterns of their requested virtual machines (VMs). In this paper, we propose Nefeli, a virtual infrastructure gateway that lifts this restriction. Through Nefeli, cloud consumers provide deployment hints on the possible mapping of VMs to physical nodes. Such hints include the collocation and anticollocation of VMs, the existence of potential performance bottlenecks, the presence of underlying hardware features (e.g., high availability), the proximity of certain VMs to data repositories, or any other information that would contribute in a more effective placement of VMs to physical hosting nodes. Consumers designate only properties of their virtual infrastructure and remain at all times agnostic to the cloud internal physical characteristics. The set of consumer-provided hints is augmented with high-level placement policies specified by the cloud administration. Placement policies and hints form a constraint satisfaction problem that when solved, yields the final VM-to-host placement. As workloads executed by the cloud may change over time, VM-to-host mappings must follow suit. To this end, Nefeli captures such events, changes VM deployment, helps avoid bottlenecks, and ultimately, improves the quality of the rendered services. Using our prototype, we examine overheads involved and show significant improvements in terms of time needed to execute scientific and real application workloads. We also demonstrate how power-aware policies may reduce the energy consumption of the physical installation. Finally, we compare Nefeli's placement choices with those attained by the open-source cloud middleware, OpenNebula.

Modern frameworks, such as Hadoop, combined with abundance of computing resources from the cloud, offer a significant opportunity to address long standing challenges in distributed processing. Infrastructure-as-a-Service clouds reduce the investment cost of renting a large data center while distributed processing frameworks are capable of efficiently harvesting the rented physical resources. Yet, the performance users get out of these resources varies greatly because the cloud hardware is shared by all users. The value for money cloud consumers achieve renders resource sharing policies a key player in both cloud performance and user satisfaction. In this paper, we employ microeconomics to direct the allotment of cloud resources for consumption in highly scalable master-worker virtual infrastructures. Our approach is developed on two premises: the cloud-consumer always has a budget and cloud physical resources are limited. Using our approach, the cloud administration is able to maximize per-user financial profit. We show that there is an equilibrium point at which our method achieves resource sharing proportional to each user's budget. Ultimately, this approach allows us to answer the question of how many resources a consumer should request from the seemingly endless pool provided by the cloud.

A foundational issue underlying many overlay network applications ranging from routing to peer-to-peer file sharing is that of the network formation, i.e., folding new arrivals into an existing overlay, and rewiring to cope with changing network conditions. Previous work has considered the problem from two perspectives: devising practical heuristics for the case of cooperative peers and performing game-theoretic analysis for the case of selfish peers. In this paper, we unify the aforementioned thrusts by defining and studying the selfish neighbor selection (SNS) game and its application to overlay routing. At the heart of SNS stands the restriction that peers are allowed up to a certain number of neighbors. This makes SNS substantially different from existing network formation games that impose no bounds on peer degrees. Having bounded degrees has important practical consequences as it permits the creation of overlay structures that requireO(n) instead ofO(n2) link monitoring overhead. We show that a node's “best response” wiring strategy amounts to solving ak-median problem on asymmetric distance. Best-response wirings have substantial practical utility as they permit selfish nodes to reap substantial performance benefits when connecting to overlays of nonselfish nodes. A more intricate consequence is that even nonselfish nodes can benefit from the existence of some selfish nodes since the latter, via their local optimizations, create a highly optimized backbone, upon which even simple heuristic wirings yield good performance. To capitalize on the above properties, we design, build, and deploy EGOIST, an SNS-inspired prototype overlay routing system for PlanetLab. We demonstrate that EGOIST outperforms existing heuristic overlays on a variety of performance metrics, including delay, available bandwidth, and node utilization, while it remains competitive with an optimal but unscalable full-mesh overlay.

Virtualization of computer systems has made feasible the provision of entire distributed infrastructures in the form of services. Such services do not expose the internal operational and physical characteristics of the underlying machinery to either users or applications. In this way, infrastructures including computers in data-centers, clusters of workstations, and networks of machines are shrouded in "clouds". Mainly through the deployment of virtual machines, such networks of computing nodes become cloud-computing environments. In this paper, we propose Nefeli, a virtual infrastructure gateway that is capable of effectively handling diverse workloads of jobs in cloud environments. By and large, users and their workloads remain agnostic to the internal features of clouds at all times. Exploiting execution patterns as well as logistical constraints, users provide Nefeli with hints for the handling of their jobs. Hints provide no hard requirements for application deployment in terms of pairing virtual-machines to specific physical cloud elements. Nefeli helps avoid bottlenecks within the cloud through the realization of viable virtual machine deployment mappings. As the types of jobs change over time, deployment mappings must follow suit. To this end, Nefeli offers mechanisms to migrate virtual machines as needed to adapt to changing performance needs. Using our prototype system, we show significant improvements in overall time needed and energy consumed for the execution of workloads in both simulated and real cloud computing environments.

In an n-way broadcast application, each one of n overlay nodes wants to push its own distinct large data file to all other n-1 destinations as well as download their respective data files. BitTorrent-like swarming protocols are ideal choices for handling such massive data volume transfers. The original BitTorrent targets one-to-many broadcasts of a single file to a very large number of receivers, and thus, by necessity, employs a suboptimized overlay topology. n-way broadcast applications, on the other hand, owing to their inherent complexity, are realizable only in small to medium scale networks. In this paper, we show that we can leverage this scale constraint to construct optimized overlay topologies that take into consideration the end-to-end characteristics of the network and as a consequence deliver far superior performance compared to random and myopic (greedy) approaches. We present the Max-Min and Max-Sum peer-selection policies used by individual nodes to select their neighbors. The first one strives to maximize the available bandwidth to the slowest destination, while the second maximizes the aggregate output rate. We design a swarming protocol suitable for n-way broadcast and operate it on top of overlay graphs formed by nodes that employ Max-Min or Max-Sum policies. Using measurements from a PlanetLab prototype implementation and trace-driven simulations, we demonstrate that the performance of swarming protocols on top of our constructed topologies is far superior to the performance of random and myopic overlays.

The random nature of unstructured P2P overlays imbues them with enhanced self-*properties. Most of the algorithms which make searching in unstructured P2P systems scalable, such as dynamic querying and 1-hop replication, rely on the random nature of the overlay to function efficiently. However, they do not take into account the structure of the underlying physical communications network, which is anything but random. Efforts to provide topology awareness to unstructured P2P systems often result to clustered graphs which affect negatively algorithms that rely on random overlays. In this paper, we propose ITA, an algorithm which creates a random overlay of randomly connected neighborhoods providing topology awareness to P2P systems, while at the same time has no negative effect on the self-*properties or the operation of the other P2P algorithms. Using extensive simulations, we demonstrate that ITA reduces communication latency by as much as 50% which is important for P2P users. Furthermore, it reduces by 20% the number of IP network messages which is critical for ISPs carrying the burden of transporting P2P traffic. Finally, ITA is shown to reduce significantly the load imposed on the routers of the IP network layer.

A foundational issue underlying many overlay network applications ranging from routing to peer-to-peer file sharing is that of connectivity management, i.e., folding new arrivals into an existing overlay, and re-wiring to cope with changing network conditions. Previous work has considered the problem from two perspectives: devising practical heuristics for specific applications designed to work well in real deployments, and providing abstractions for the underlying problem that are analytically tractable, especially via game-theoretic analysis. In this paper, we unify these two thrusts by using insights gleaned from novel, realistic theoretic models in the design of EGOIST -- a distributed overlay routing system that we implemented, deployed, and evaluated on PlanetLab. Using extensive measurements of paths between nodes, we demonstrate that EGOIST'S neighbor selection primitives significantly outperform existing heuristics on a variety of performance metrics, including delay, available bandwidth, and node utilization. Moreover, we demonstrate that EGOIST is competitive with an optimal, but unscalable full-mesh approach, remains highly effective under significant churn, is robust to cheating, and incurs minimal overhead. Finally, we use a multiplayer peer-to-peer game to demonstrate the value of EGOIST to end-user applications.

In an n-way broadcast application each one of n overlay nodes wants to push its own distinct large data file to all other n-1 destinations as well as download their respective data files. BitTorrent-like swarming protocols are ideal choices for handling such massive data volume transfers. The original BitTorrent targets one-to-many broadcasts of a single file to a very large number of receivers and thus, by necessity, employs an almost random overlay topology, n-way broadcast applications on the other hand, owing to their inherent n-squared nature, are realizable only in small to medium scale networks. In this paper, we show that we can leverage this scale constraint to construct optimized overlay topologies that take into consideration the end-to-end characteristics of the network and as a consequence deliver far superior performance compared to random and myopic (local) approaches. We present the Max-Min and Max- Sum peer-selection policies used by individual nodes to select their neighbors. The first one strives to maximize the available bandwidth to the slowest destination, while the second maximizes the aggregate output rate. We design a swarming protocol suitable for n-way broadcast and operate it on top of overlay graphs formed by nodes that employ Max-Min or Max-Sum policies. Using trace-driven simulation and measurements from a PlanetLab prototype implementation, we demonstrate that the performance of swarming on top of our constructed topologies is far superior to the performance of random and myopic overlays. Moreover, we show how to modify our swarming protocol to allow it to accommodate selfish nodes.

Emerging Web services, such as email, photo sharing, and web site archives, must preserve large volumes of quickly accessible data indefinitely into the future. The costs of doing so often determine whether the service is economically viable. We make the case that these applications' demands on large scale storage systems over long time horizons require us to reevaluate traditional system designs. We examine threats to long-lived data from an end-to-end perspective, taking into account not just hardware and software faults but also faults due to humans and organizations. We present a simple model of long-term storage failures that helps us reason about various strategies for addressing some of these threats. Using this model we show that the most important strategies for increasing the reliability of long-term storage are detecting latent faults quickly, automating fault repair to make it cheaper and faster, and increasing the independence of data replicas.

To use their pool of resources efficiently, distributed stream-processing systems push query operators to nodes within the network. Currently, these operators, ranging from simple filters to custom business logic, are placed manually at intermediate nodes along the transmission path to meet application-specific performance goals. Determining placement locations is challenging because network and node conditions change over time and because streams may interact with each other, opening venues for reuse and repositioning of operators. This paper describes a stream-based overlay network (SBON), a layer between a stream-processing system and the physical network that manages operator placement for stream-processing systems. Our design is based on a cost space, an abstract representation of the network and on-going streams, which permits decentralized, large-scale multi-query optimization decisions. We present an evaluation of the SBON approach through simulation, experiments on PlanetLab, and an integration with Borealis, an existing stream-processing engine. Our results show that an SBON consistently improves network utilization, provides low stream latency, and enables dynamic optimization at low engineering cost.

The LOCKSS project has developed and deployed in a world-wide test a peer-to-peer system for preserving access to journals and other archival information published on the Web. It consists of a large number of independent, low-cost, persistent Web caches that cooperate to detect and repair damage to their content by voting in “opinion polls.” Based on this experience, we present a design for and simulations of a novel protocol for voting in systems of this kind. It incorporates rate limitation and intrusion detection to ensure that even some very powerful adversaries attacking over many years have only a small probability of causing irrecoverable damage before being detected.

The LOCKSS (Lots Of Copies Keep Stuff Safe) system allows users to store and preserve electronic content through a system of inexpensive computers arranged in an ad hoc peer-to-peer network. These peers cooperate to detect and repair damage by voting in "opinion polls." We develop a more accurate view of how the network will perform over time by simulating the system's behavior using dynamic models in which peers can be subverted and repaired. These models take into account a variety of parameters, including the rate of peer subversion, the rate of repair, the extent of subversion, and the responsiveness of each peer's system administrator. These models reveal certain systemic vulnerabilities not apparent in our static simulations: a typical adversary that begins with a small foothold within the system (e.g., 20 percent of the population) will completely dominate the voting process within 10 years, even if he only exploits one vulnerability each year. In light of these results, we propose and evaluate countermeasures. One technique, ripple healing, performs remarkably well. For models in which all system administrators are equally likely to repair their systems, it eliminates nearly systemic levels of corruption within days. For models in which some administrators are more likely to repair their systems, ripple healing limits corruption, but proves less effective, since these models already demonstrate superior performance

The LOCKSS project has developed and deployed in a world-wide test a peer-to-peer system for preserving access to journals and other archival information published on the Web. It consists of a large number of independent, low-cost, persistent web caches that cooperate to detect and repair damage to their content by voting in "opinion polls." Based on this experience, we present a design for and simulations of a novel protocol for voting in systems of this kind. It incorporates rate limitation and intrusion detection to ensure that even some very powerful adversaries attacking over many years have only a small probability of causing irrecoverable damage before being detected.

We are facing a growing user demand for ubiquitous Internet access. As result, network ports and wireless LANs are becoming common in public spaces inside buildings such as lounges, conference rooms and lecture halls. This introduces the problem of protecting networks accessible through these public ports from unauthorized use. In this paper, we study the problem of access control through public network ports. We view this problem as a special case of the more general problem of access control for a service on a network. We present an access control model on which we base our solution. This model has three components: authentication, authorization, and access verification. We describe the design and implementation of a system that allows secure network access through public network ports and wireless LANs. The design requires no special hardware or custom client software, resulting in minimal deployment cost and maintenance overhead. The system has a user-friendly, Web-based interface, offers good security, and scales to a campus-sized community.

The data cube is an aggregate operator which has been shown to be very powerful for On Line Analytical Processing (OLAP) in the context of data warehousing. It is, however, very expensive to compute, access, and maintain. In this paper we define the “cubetree” as a storage abstraction of the cube and realize in using packed R-trees for most efficient cube queries. We then reduce the problem of creation and maintenance of the cube to sorting and bulk incremental merge-packing of cubetrees. This merge-pack has been implemented to use separate storage for writing the updated cubetrees, therefore allowing cube queries to continue even during maintenance. Finally, we characterize the size of the delta increment for achieving good bulk update schedules for the cube. The paper includes experiments with various data sets measuring query and bulk update performance.