Search

Strongly consistent distributed systems are easy to reason about but face fundamental limitations in availability and performance. Weakly consistent systems can be implemented with very high performance but place a burden on the application developer to reason about complex interleavings of execution. Invariant confluence provides a formal framework for understanding when we can get the best of both worlds. An invariant confluent object can be efficiently replicated with no coordination needed to preserve its invariants. However, actually determining whether or not an object is invariant confluent is challenging. In this paper, we establish conditions under which a commonly used sufficient condition for invariant confluence is both necessary and sufficient, and we use this condition to design (a) a general-purpose interactive invariant confluence decision procedure and (b) a novel sufficient condition that can be checked automatically. We then take a step beyond invariant confluence and introduce a generalization of invariant confluence, called segmented invariant confluence, that allows us to replicate non-invariant confluent objects with a small amount of coordination. We implemented these formalisms in a prototype called Lucy and found that our decision procedures efficiently handle common real-world workloads including foreign keys, rollups, escrow transactions, and more. We also found that segmented invariant confluent replication can deliver up to an order of magnitude more throughput than linearizable replication for low contention workloads and comparable throughput for medium to high contention workloads.

In emails, information abounds. Whether it be a bill reminder, a hotel confirmation, or a shipping notification, our emails contain useful bits of information that enable a number of applications. Most of this email traffic is machine-generated, sent from a business to a human. These business-to-consumer emails are typically instantiated from a set of email templates, and discovering these templates is a key step in enabling a variety of intelligent experiences. Existing email information extraction systems typically separate information extraction into two steps: an offline template discovery process (called template induction) that is periodically run on a sample of emails, and an online email annotation process that applies discovered templates to emails as they arrive. Since information extraction requires an email's template to be known, any delay in discovering a newly created template causes missed extractions, lowering the overall extraction coverage. In this paper, we present a novel system called Crusher that discovers templates completely online, reducing template discovery delay from a week (for the existing MapReduce-based batch system) to minutes. Furthermore, Crusher has a resource consumption footprint that is significantly smaller than the existing batch system. We also report on the surprising lesson we learned that conventional stream processing systems do not present a good framework on which to build Crusher. Crusher delivers an order of magnitude more throughput than a prototype built using a stream processing engine. We hope that these lessons help designers of stream processing systems accommodate a broader range of applications like online template induction in the future.

Quorum systems are a powerful mechanism for ensuring the consistency of replicated data. Production systems usually opt for majority quorums due to their simplicity and fault tolerance, but majority quorum systems provide poor throughput and scalability. Alternatively, researchers have invented a number of theoretically "optimal" quorum systems, but the underlying theory ignores many practical complexities such as machine heterogeneity and workload skew. In this paper, we conduct a pragmatic re-examination of quorum systems. We enrich the current theory on quorum systems with a number of practical refinements to find quorum systems that provide higher throughput, lower latency, and lower network load. We also develop a library Quoracle that precisely quantifies the available trade-offs between quorum systems to empower engineers to find optimal quorum systems, given a set of objectives for specific deployments and workloads. Our tool is available online at: https://github.com/mwhittaker/quoracle., To be published in PaPoC 2021 (https://papoc-workshop.github.io/2021/)

Traditionally, the high cost of network communication between servers has hidden the impact of cross-core coordination in replicated systems. However, new technologies, like kernel-bypass networking and faster network links, have exposed hidden bottlenecks in distributed systems. This paper explores how to build multicore-scalable, replicated storage systems. We introduce a new guideline for their design, called the Zero-Coordination Principle. We use this principle to design a new multicore-scalable, in-memory, replicated, key-value store, called Meerkat. Unlike existing systems, Meerkat eliminates all cross-core and cross-replica coordination, both of which pose a scalability bottleneck. Our experiments found that Meerkat is able to scale up to 80 hyper-threads and execute 8.3 million transactions per second. Meerkat represents an improvement of 12X on state-of-the-art, fault-tolerant, in-memory, transactional storage systems built using leader-based replication and a shared transaction log.

Protein aggregation into amyloid fibrils is a ubiquitous phenomenon across the spectrum of neurodegenerative disorders and type 2 diabetes. A common strategy against amyloidogenesis is to minimize the populations of toxic oligomers and protofibrils by inhibiting protein aggregation with small molecules or nanoparticles. However, melanin synthesis in nature is realized by accelerated protein fibrillation to circumvent accumulation of toxic intermediates. Accordingly, we designed and demonstrated the use of star-shaped poly(2-hydroxyethyl acrylate) (PHEA) nanostructures for promoting aggregation while ameliorating the toxicity of human islet amyloid polypeptide (IAPP), the peptide involved in glycemic control and the pathology of type 2 diabetes. The binding of PHEA elevated the β-sheet content in IAPP aggregates while rendering a new morphology of "stelliform" amyloids originating from the polymers. Atomistic molecular dynamics simulations revealed that the PHEA arms served as rodlike scaffolds for IAPP binding and subsequently accelerated IAPP aggregation by increased local peptide concentration. The tertiary structure of the star nanoparticles was found to be essential for driving the specific interactions required to impel the accelerated IAPP aggregation. This study sheds new light on the structure-toxicity relationship of IAPP and points to the potential of exploiting star polymers as a new class of therapeutic agents against amyloidogenesis.

Systematically reasoning about the fine-grained causes of events in a real-world distributed system is challenging. Causality, from the distributed systems literature, can be used to compute the causal history of an arbitrary event in a distributed system, but the event's causal history is an over-approximation of the true causes. Data provenance, from the database literature, precisely describes why a particular tuple appears in the output of a relational query, but data provenance is limited to the domain of static relational databases. In this paper, we present wat-provenance: a novel form of provenance that provides the benefits of causality and data provenance. Given an arbitrary state machine, wat-provenance describes why the state machine produces a particular output when given a particular input. This enables system developers to reason about the causes of events in real-world distributed systems. We observe that automatically extracting the wat-provenance of a state machine is often infeasible. Fortunately, many distributed systems components have simple interfaces from which a developer can directly specify wat-provenance using a technique we call wat-provenance specifications. Leveraging the theoretical foundations of wat-provenance, we implement a prototype distributed debugging framework called Watermelon.

The utility of biodegradable nanosized drug carriers for the local and controlled delivery of therapeutics to the lungs has prompted significant interest in the development of inhalable nanomedicines. Still, little is known about how these systems are cleared from the lungs, including the kinetics of the structural lipids. Most preclinical and clinical studies to date have evaluated the lung clearance of loaded drugs, which in many cases poorly reflects the kinetics of the nanocarrier, or the bulk-labelled particles. This study therefore aimed to describe and compare the pulmonary pharmacokinetic behaviour and patterns of lung clearance of two commonly explored inhalable nanocarriers (anionic ∼150 nm liposomes and solid lipid nanoparticles [SLNs]) in rats by following the

Network measurement is an essential component of many SDN applications, but most existing controller platforms force programmers to implement measurement tasks by installing fine-grained forwarding rules on switches---an approach that significantly increases configuration and management complexity. This paper proposes a radically different approach: rather than implementing measurement tasks directly on network switches, we argue for pushing measurement to the edge and utilizing the abundant resources available on end hosts. At a technical level, our approach is based on two key ideas: (i) we express measurement tasks using programs in a high-level, declarative query language, and (ii) we use program analysis to calculate predicates that can be used to answer queries at the edge of the network. We present an implementation of our approach on top of the NetKAT framework, we develop case studies illustrating the benefits of our approach, and we conduct experiments that quantify performance on realistic benchmarks.