Reasoning about the correctness of distributed systems is a significant challenge, with precise correctness specifications serving as an essential prerequisite to verification. However, identifying and formulating specifications remains a major hurdle for developers in practice. Specy addresses this challenge by automatically learning specifications from observable event traces generated by message exchanges in distributed systems. The system employs a specialized grammar tailored for event-based specifications, incorporating support for quantifiers over events - a capability essential for capturing the complex behavioral patterns inherent in distributed protocols. Specy utilizes a novel learning procedure that combines grammar-based enumerative search with dynamic learning from event traces, providing effective control over the specification search. We evaluated Specy on established distributed protocols and industrial case studies, demonstrating its ability to successfully learn important protocol specifications. Specy can discover previously unidentified specifications overlooked by developers, automatically derive inductive invariants that were previously constructed manually for verification purposes, and, through run-time monitoring in production systems, reveal gaps in testing coverage - highlighting opportunities to leverage specifications in practice.

In 2013, AmazonWeb Services revolutionized the data warehousing industry by launching Amazon Redshift, the first fully-managed, petabyte-scale, enterprise-grade cloud data warehouse. Amazon Redshift made it simple and cost-effective to efficiently analyze large volumes of data using existing business intelligence tools. This cloud service was a significant leap from the traditional on-premise data warehousing solutions, which were expensive, not elastic, and required significant expertise to tune and operate. Customers embraced Amazon Redshift and it became the fastest growing service in AWS. Today, tens of thousands of customers use Redshift in AWS's global infrastructure to process exabytes of data daily.

Rivulet is a fault-tolerant distributed platform for running smart-home applications; it can tolerate failures typical for a home environment (e.g., link losses, network partitions, sensor failures, and device crashes). In contrast to existing cloud-centric solutions, which rely exclusively on a home gateway device, Rivulet leverages redundant smart consumer appliances (e.g., TVs, Refrigerators) to spread sensing and actuation across devices local to the home, and avoids making the Smart-Home Hub a single point of failure. Rivulet ensures event delivery in the presence of link loss, network partitions and other failures in the home, to enable applications with reliable sensing in the case of sensor failures, and event processing in the presence of device crashes. In this paper, we present the design and implementation of Rivulet, and evaluate its effective handling of failures in a smart home.

Choosing a cloud storage system and specific operations for reading and writing data requires developers to make decisions that trade off consistency for availability and performance. Applications may be locked into a choice that is not ideal for all clients and changing conditions. Pileus is a replicated key-value store that allows applications to declare their consistency and latency priorities via consistency-based service level agreements (SLAs). It dynamically selects which servers to access in order to deliver the best service given the current configuration and system conditions. In application-specific SLAs, developers can request both strong and eventual consistency as well as intermediate guarantees such as read-my-writes. Evaluations running on a worldwide test bed with geo-replicated data show that the system adapts to varying client-server latencies to provide service that matches or exceeds the best static consistency choice and server selection scheme.

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

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

Combining access control with weakly consistent replication presents a challenge if the resulting system is to support eventual consistency. If authorization policy can be temporarily inconsistent, any given operation may be permitted at one node and yet denied at another. This is especially troublesome when the operation in question involves a change in policy. Without a careful design, permanently divergent state can result.

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

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

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

Mobile devices are increasingly equipped with hardware and software services allowing them to determine their locations, but support for building location-aware applications remains rudimentary. This paper proposes tracks of location coordinates as a high-level abstraction for a new class of mobile applications including ride sharing, location-based collaboration, and health monitoring. Each track is a sequence of entries recording a person's time, location, and application-specific data. StarTrack provides applications with a comprehensive set of operations for recording, comparing, clustering and querying tracks. StarTrack can efficiently operate on thousands of tracks.

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

Traditionally, designers organize software system as active end-points (e.g.applications) linked by passive infrastructures (e.g.networks).Increasingly, however, networks and infrastructures are becoming active components that contribute directly to application behavior.Amongst the various problems that this presents is the question of how such active infrastructures should be programmed.We have been developing an active document management system called Placeless Documents.Its programming model is organized in terms of properties that actively contribute to the functionality and behavior of the documents to which they are attached.This paper discusses active properties and their use as a programming model for active infrastructures.We have found that active properties enable the creation of persistent, autonomous active entities in document systems, independent of specific repositories and applications, but present challenges for managing problems of composition.

Document properties are a compelling infrastructure on which to develop document management applications. A property-based approach avoids many of the problems of traditional heierarchical storage mechanisms, reflects document organizations meaningful to user tasks, provides a means to integrate the perspectives of multiple individuals and groups, and does this all within a uniform interaction framework. Document properties can reflect not only categorizations of documents and document use, but also expressions of desired system activity, such as sharing criteria, replication management, and versioning. Augmenting property-based document management systems with active properties that carry executable code enables the provision of document-based services on a property infrastructure. The combination of document properties as a uniform mechanism for document management, and active properties as a way of delivering document services, represents a new paradigm for document management infrastructures. The Placeless Documents system is an experimental prototype developed to explore this new paradigm. It is based on the seamless integration of user-specific, active properties. We present the fundamental design approach, explore the challenges and opportunities it presents, and show our architectures deals with them.

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

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.>

In a database to which data is continually added, users may wish to issue a permanent query and be notified whenever data matches the query. If such continuous queries examine only single records, this can be implemented by examining each record as it arrives. This is very efficient because only the incoming record needs to be scanned. This simple approach does not work for queries involving joins or time. The Tapestry system allows users to issue such queries over a database of mail and bulletin board messages. The user issues a static query, such as “show me all messages that have been replied to by Jones,” as though the database were fixed and unchanging. Tapestry converts the query into an incremental query that efficiently finds new matches to the original query as new messages are added to the database. This paper describes the techniques used in Tapestry, which do not depend on triggers and thus be implemented on any commercial database that supports SQL. Although Tapestry is designed for filtering mail and news messages, its techniques are applicable to any append-only database.

Thevoice managerin the Etherphone system provides facilities for recording, editing, and playing stored voice in a distributed personal-computing environment. It provides the basis for applications such as voice mail, annotation of multimedia documents, and voice editing using standard text-editing techniques. To facilitate sharing, the voice manager stores voice on a special voice file server that is accessible via the local internet. Operations for editing a passage of recorded voice simply build persistent data structures to represent the edited voice. These data structures, implementing an abstraction calledvoice ropes, are stored in a server database and consist of lists of intervals within voice files. Clients refer to voice ropes solely by reference.Interests, additional persistent data structures maintained by the server, serve two purposes: First, they provide a sort of directory service for managing the voice ropes that have been created. More importantly, they provide a reliable reference-counting mechanism, permitting the garbage collection of voice ropes that are no longer needed. These interests are grouped into classes; for some important classes, obsolete interests can be detected and deleted by a class-specific algorithm that runs periodically.

Whru a dilt~lhSC is replicated at, many sites2 maintaining mutual consistrnry among t,he sites iu the fac:e of updat,es is a signitirant problem.This paper descrikrs several randomized algorit,hms for dist,rihut.ingupdates and driving t,he replicas toward consist,c>nc,y.The algorit Inns are very simple and require few guarant,ees from the underlying conllllunicat.iollsystem, yc+ they rnsutc t.hat.the off(~c~t, of ('very update is evcnt,uwlly rf+irt-ted in a11 rq1ica.s.The cost, and parformancc of t,hr algorithms arc tuned I>? c%oosing appropriat,c dist,rilMions in t,hc randoinizat,ioii step.TIN> idgoritlmls ilr(' c*los~*ly analogoIls t,o epidemics, and t,he epi-dcWliolog)-litc\ratiirc, ilitlh iii Illld~~rsti4lldill~ tlicir bc*liavior.One of tlW i$,oritlims 11&S brc>n implrmcWrd in the Clraringhousr sprv(brs of thr Xerox C'orporat~c~ Iiitcrnc4, solviiig long-standing prol>lf~lns of high traffic and tlatirl>ilsr inconsistcllcp.

The Etherphone™ system was developed at Xerox PARC to explore methods of integrating voice into existing distributed personal computing environments. An important component of the Etherphone system, the voice manager, provides operations for recording, playing, editing, and otherwise manipulating digitized voice based on an abstraction that we call voice ropes. It was designed to allow:

Caching reduces the average cost of retrieving data by amortizing the lookup cost over several references to the data. Problems with maintaining strong cache consistency in a distributed system can be avoided by treating cached information as hints. A new approach to managing caches of hints suggests maintaining a minimum level of cache accuracy, rather than maximizing the cache hit ratio, in order to guarantee performance improvements. The desired accuracy is based on the ratio of lookup costs to the costs of detecting and recovering from invalid cache entries. Cache entries are aged so that they get purged when their estimated accuracy falls below the desired level. The age thresholds are dictated solely by clients' accuracy requirements instead of being suggested by data storage servers or system administrators.

Contemporary distributed office systems rely heavily on communication between workstations, file servers, printers, and other computerized components.The COSIE Communication Subsystem has been developed for an office system internetwork consisting of local networks of varying technologies.The communication facilities provide for the transmission of self-contained messages to mailboxes, which are referenced by capabilities and may be shared.A generalized method for pairing requests with responses supports a variety of communication paradigms, while a flexible routing algorithm permits diverse network topologies.The main emphasis in the design of the COSIE Communication Subsystem was on presenting simple mechanisms that allow more general policies and protocols to be explored.