Structured peer-to-peer overlay networks such as CAN, Chord, Pastry, and Tapestry can be used to implement Internet-scale application-level multicast. There are two general approaches to accomplishing this: tree building and flooding. This paper evaluates these two approaches using two different types of structured overlay: 1) overlays which use a form of generalized hypercube routing, e.g., Chord, Pastry and Tapestry, and 2) overlays which use a numerical distance metric to route through a Cartesian hyperspace, e.g., CAN. Pastry and CAN are chosen as the representatives of each type of overlay. To the best of our knowledge, this paper reports the first head-to-head comparison of CAN-style versus Pastry-style overlay networks, using multicast communication workloads running on an identical simulation infrastructure. The two approaches to multicast are independent of overlay network choice, and we provide a comparison of flooding versus tree-based multicast on both overlays. Results show that the tree-based approach consistently outperforms the flooding approach. Finally, for tree-based multicast, we show that Pastry provides better performance than CAN.

The Farsite distributed file system provides availability by replicating each file onto multiple desktop computers. Since this replication consumes significant storage space, it is important to reclaim used space where possible. Measurement of over 500 desktop file systems shows that nearly half of all consumed space is occupied by duplicate files. We present a mechanism to reclaim space from this incidental duplication to make it available for controlled file replication. Our mechanism includes: (1) convergent encryption, which enables duplicate files to be coalesced into the space of a single file, even if the files are encrypted with different users' keys; and (2) SALAD, a Self-Arranging Lossy Associative Database for aggregating file content and location information in a decentralized, scalable, fault-tolerant manner. Large-scale simulation experiments show that the duplicate-file coalescing system is scalable, highly effective, and fault-tolerant.

This paper indicates that a scalable fault-tolerant name service can be provided utilizing an overlay network and that such a name service can scale along a number of dimensions: it can be sized to support a large number of clients, it can allow large numbers of concurrent lookups on the same name or sets of names, and it can provide name lookup latencies measured in seconds. Furthermore, it can enable updates to be made pervasively visible in times typically measured in seconds for update rates of up to hundreds per second. We explain how many of these scaling properties for the name service are obtained by reusing some of the same mechanisms that allowed the underlying overlay network to scale. Finally, we observe that the overlay network is sensitive to bandwidth and CPU limitations.

This paper presents the design philosophy and initial design decisions of Herald: a highly scalable global event notification system that is being designed and built at Microsoft Research. Herald is a distributed system designed to transparently scale in all respects, including numbers of subscribers and publishers, numbers of event subscription points, and event delivery rates. Event delivery can occur within a single machine, within a local network or Intranet, and throughout the Internet. Herald tries to take into account the lessons learned from the successes of both the Internet and the Web. Most notably, Herald is being designed, like the Internet, to operate correctly in the presence of numerous broken and disconnected components. The Herald service will be constructed as a set of protocols governing a federation of machines within cooperating but mutually suspicious domains of trust. Like the Web, Herald will try to avoid, to the extent possible, the maintenance of globally consistent state and will make failures part of the client-visible interface.

We consider an architecture for a serverless distributed file system that does not assume mutual trust among the client computers. The system provides security, availability, and reliability by distributing multiple encrypted replicas of each file among the client machines. To assess the feasibility of deploying this system on an existing desktop infrastructure, we measure and analyze a large set of client machines in a commercial environment. In particular, we measure and report results on disk usage and content; file activity; and machine uptimes, lifetimes, and loads. We conclude that the measured desktop infrastructure would passably support our proposed system, providing availability on the order of one unfilled file request per user per thousand days.

Providing high availability and the ability to share data despite the weak connectivity of mobile computing raises the problem of trusting replicated data servers that may be corrupt. This is because servers must be run on portable computers, and these machines are less secure and thus less trustworthy than those traditionally used to run servers. We describe the kinds of problems one must be prepared to deal with, noting that even users of secured, non-portable computers are at risk if servers trust all authorized peers. We show that high availability through data replication on portable computers need not be mutually exclusive with various levels of data security one might want. We give three solutions to this trust problem, achieving progressively higher levels of security with progressively higher costs. 1. Introduction Several existing systems, such as Ficus [1], Lotus Notes [2], and Bayou [3, 4], address the weak connectivity characteristics of mobile computing environments by a...

Bayou's anti-entropy protocol for update propagation between weakly consistent storage replicas is based on pair-wise communication, the propagation of write operations, and a set of ordering and closure.constraints on the propagation of the writes.The simplicity of the design makes the protocol very flexible, thereby providing support for diverse networking environments and usage scenarios.It accommodates a variety of policies for when and where to propagate updates.It operates over diverse network topologies, including low-bandwidth links.It is incremental.It enables replica convergence, and updates can be propagated using floppy disks and similar transportable media.Moreover, the protocol handles replica creation and retirement in a light-weight manner.Each of these features is enabled by only one or two of the protocol's design choices, and can be independently incorporated in other systems.This paper presents the anti-entropy protocol in detail, describing the design decisions and resulting features.

Asynchronous collaboration is characterized by the degree of independence collaborators have from one another.In particular, collaborators working asynchronously typically have little need for frequent and finegrained coordination with one another, and typically do not need to be notified immediately of changes made by others to any shared artifacts they are working with.We present an infrastructure, called Bayou, designed to support the construction of asynchronous collaborative applications.Bayou provides a replicated, weakly-consistent, data storage engine to application writers.The system supports a number of mechanisms for leveraging application semantics; using these mechanisms, applications can implement complex conflict detection and resolution policies, and choose the level of consistency and stability they will see in their databases.We present a number of applications we have built or are building using the Bayou system, and examine how these take advantage of the Bayou architecture.

article Free Access Share on Managing update conflicts in Bayou, a weakly connected replicated storage system Authors: D. B. Terry Computer Science Laboratory, Xerox Palo Alto Research Center, Palo Alto, California Computer Science Laboratory, Xerox Palo Alto Research Center, Palo Alto, CaliforniaView Profile , M. M. Theimer Computer Science Laboratory, Xerox Palo Alto Research Center, Palo Alto, California Computer Science Laboratory, Xerox Palo Alto Research Center, Palo Alto, CaliforniaView Profile , Karin Petersen Computer Science Laboratory, Xerox Palo Alto Research Center, Palo Alto, California Computer Science Laboratory, Xerox Palo Alto Research Center, Palo Alto, CaliforniaView Profile , A. J. Demers Computer Science Laboratory, Xerox Palo Alto Research Center, Palo Alto, California Computer Science Laboratory, Xerox Palo Alto Research Center, Palo Alto, CaliforniaView Profile , M. J. Spreitzer Computer Science Laboratory, Xerox Palo Alto Research Center, Palo Alto, California Computer Science Laboratory, Xerox Palo Alto Research Center, Palo Alto, CaliforniaView Profile , C. H. Hauser Computer Science Laboratory, Xerox Palo Alto Research Center, Palo Alto, California Computer Science Laboratory, Xerox Palo Alto Research Center, Palo Alto, CaliforniaView Profile Authors Info & Claims ACM SIGOPS Operating Systems ReviewVolume 29Issue 5Dec. 3, 1995 pp 172–182https://doi.org/10.1145/224057.224070Online:03 December 1995Publication History 630citation5,089DownloadsMetricsTotal Citations630Total Downloads5,089Last 12 Months311Last 6 weeks48 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

To take full advantage of the promise of mobile/ubiquitous computing requires the availability and use of location information about the various physical objects and persons in an environment. At the same time, indiscriminant use of location information for people can result in an invasion of privacy and provides the potential for abuse by third parties. In this article we describe a suite of useful location-based applications and discuss architectural considerations for supporting them in a scalable, secure fashion.>

We describe the results of examining two large research and commercial systems for the ways that they use threads. We used three methods: analysis of macroscopic thread statistics, analysis the microsecond spacing between thread events, and reading the implementation code. We identify ten different paradigms of thread usage: defer work, general pumps, slack processes, sleepers, one-shots, deadlock avoidance, rejuvenation, serializers, encapsulated fork and exploiting parallelism. While some, like defer work, are well known, others have not been previously described. Most of the paradigms cause few problems for programmers and help keep the resulting system implementation understandable. The slack process paradigm is both particularly effective in improving system performance and particularly difficult to make work well. We observe that thread priorities are difficult to use and may interfere in unanticipated ways with other thread primitives and paradigms. Finally, we glean from the practices in this code several possible future research topics in the area of thread abstractions.

To take full advantage of the promise of ubiquitous computing requires the use of location information, yet people should have control over who may know their whereabouts. We present an architecture that achieves these goals for an interesting set of applications. Personal information is managed by User Agents, and a partially decentralized Location Query Service is used to facilitate location-based operations. This architecture gives users primary control over their location information, at the cost of making more expensive certain queries, such as those wherein location and identity closely interact. We also discuss various extensions to our architecture that offer users additional trade-offs between privacy and efficiency. Finally, we report some measurements of the unextended system in operation, focusing on how well the system is actually able to track people. Our system uses two kinds of location information, which turn out to provide partial and complementary coverage.

Access control programs (ACPs), which permit controlled delegation of access rights to untrusted computer hosts, are discussed. Existing delegation protocols for distributed systems provide a way for a client to transfer its access rights to an intermediary, but provide only limited facilities for restricting the rights granted to the intermediary. ACPs are small programs that encode arbitrary specifications of delegated access rights. They are created and digitally signed by a client and passed to a server through an intermediary. When processing a request from the intermediary, the server executes the access control program to decide whether or not to grant the intermediary's request. Examples of ACPs used in a variety of applications are presented. A sample implementation of ACPs in the Andrew File System is described.>

An approach to heterogeneous process migration that involves building a machine-independent migration program that specifies the current code and data state of the process to be migrated is described. When this program is compiled and executed on the target machine, it will first reconstruct the process's state and then continue the normal execution of the now-migrated process. The principal advantage of this approach is that it hides the details of code and data translation in the compilers for each machine.>

QuickSilver is a distributed operating system that is intended for large, geographically dispersed systems. The authors describe how clients and data servers interact in the QuickSilver system to access distributed data in the context of large, geographically dispersed systems in which there are many different kinds of data servers. An interface is defined that provides a uniform way for clients and servers to exchange information about each other and to access data objects. The interface attempts to minimize the number of messages needed for this. It supports efficient interaction with higher-level client and server semantics by appropriate use of high-level abstractions and operations, and by selectively exposing the parameters governing communication connections to higher layers of the software.>

The authors describe the design and performance of scheduling facilities for finding idle hosts in a workstation-based distributed system. They focus on the tradeoffs between centralized and decentralized architectures with respect to scalability, fault tolerance, and simplicity of design, as well as several implementation issues of interest when multicast communication is used. They conclude that the principal tradeoff between the two approaches is that a centralized architecture can be scaled to a significantly greater degree and can more easily monitor global system statistics whereas a decentralized architecture is simpler to implement.>

The design and performance of scheduling facilities for finding idle hosts in a workstation-based distributed system are described. The focus is on the tradeoffs between centralized and decentralized architectures with respect to scalability, fault tolerance, and simplicity of design, as well as several implementation issues of interest when using multicast communication. It is concluded that the principal tradeoff between the two approaches is that a centralized architecture can be scaled to a significantly greater degree and can more easily monitor global system statistics, while a decentralized architecture is simpler to implement.>

Article Free Access Share on Preemptable remote execution facilities for the V-system Authors: Marvin M. Theimer Computer Science Department, Stanford University, Stanford, CA Computer Science Department, Stanford University, Stanford, CAView Profile , Keith A. Lantz Computer Science Department, Stanford University, Stanford, CA Computer Science Department, Stanford University, Stanford, CAView Profile , David R. Cheriton Computer Science Department, Stanford University, Stanford, CA Computer Science Department, Stanford University, Stanford, CAView Profile Authors Info & Claims SOSP '85: Proceedings of the tenth ACM symposium on Operating systems principlesDecember 1985 Pages 2–12https://doi.org/10.1145/323647.323629Published:01 December 1985Publication History 227citation736DownloadsMetricsTotal Citations227Total Downloads736Last 12 Months33Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

A major reason for the rarity of distributed applications, despite the proliferation of networks, is the sensitivity of their performance to various aspects of the network environment. We demonstrate that distributed applications can run faster than local ones, using common hardware. We also show that the primary factors affecting performance are, in approximate order of importance: speed of the user's workstation, speed of the remote host (if any), and the high-level (above the transport level) protocols used. In particular, the use of batching, pipelining, and structure in high-level protocols reduces the degradation often experienced between different bandwidth networks. Less significant, but still noticeable improvements result from proper design and implementation of the underlying transport protocols. Ultimately, with proper application of these techniques, network bandwidth is rendered virtually insignificant.