1,721,031 research outputs found
A Programming Paradigm for Building Disaggregated Applications for the Heterogeneous Computing Environment
No full text138 pagesWith the rise of cloud computing, many applications have transitioned to the cloud. However, various domain-specific tasks require specialized hardware to expedite computation, rather than relying solely on CPUs. This has transformed the cloud into a heterogeneous computing environment, composed of a variety of domain-specific specialized accelerators. Examples include GPUs for image classification and video processing, TPUs for artificial intelligence and machine learning tasks, and ASICs for blockchain mining. There are also specialized hardware pieces, such as smartNICs and smartSSDs, which can unlock more of the underlying hardware’s potential.Nonetheless, the existing programming paradigm for applications is CPU-centric, meaning that specialized hardware is bound to a CPU host rather than being a first- class programmable abstraction. This can cause issues such as restricted scalability of accelerators on a single host, increased system complexity when managing multiple nodes, among other problems. In this dissertation, we propose a programming paradigm that consists of actors and shared logs to provide a resource-egalitarian abstraction, simplifying the development of applications within a heterogeneous computing environment. We present two frame- works following this programming paradigm to assist application developers in build- ing applications in both a partitioned network IoT context and a resource-disaggregated cloud context
Compositional Security for Smart Contracts
No full text162 pagesSecuring smart contracts remains a fundamental challenge. At its core, it is a question of building software that is secure in composition with untrusted code, which extends far beyond the blockchain setting. We introduce SCIF, a language for building smart contracts that are compositionally secure. SCIF is based on the fundamentally compositional principle of secure information flow, but extends this core mechanism to be the first language to include protection against reentrancy attacks, confused deputy attacks, and improper error handling, even in the presence of malicious contracts that do not follow the rules of SCIF. SCIF proposes a novel and principled way to understand and prevent reentrancy attacks and confused deputy attacks. Additionally, SCIF supports a rich ecosystem of interacting principals with partial trust through its mechanisms for dynamic trust management. SCIF has been implemented as a compiler to Solidity. We describe the SCIF language, including its static checking rules and its runtime system. Finally, we implement several applications requiring intricate security reasoning, showing how SCIF supports building complex smart contracts securely and provides the programmer with accurate diagnostics about potential security bugs
Formal Modeling Languages For High-assurance Domain-specific Systems
No full text200 pagesSoftware systems today struggle to behave as intended in deployment. The problem is made worse by the ever-increasing complexity of systems resulting from the rapid expansion of modern-day software. For instance, almost all systems nowadays utilize concurrency, and unexpected behaviors such as race conditions are quite common. In this case and many others, the number of possible program behaviors suffers from combinatorial explosion, which renders conventional testing insufficient to provide enough assurance at a feasible cost.This dissertation explores alternative approaches that guarantee high assurance systematically and foundationally by building and analyzing formal models of those systems through domain-specific languages. While real-world systems often involve components of many different domains, as a first step, we choose three mission-critical domains as targets: fault-tolerant distributed protocols, concurrent programs, and parsers. For each of those domains, a new language for formally modeling domain-specific systems is proposed. Meta-theoretic analyses of those languages illustrate the relationships between models built in those languages and the realistic behaviors of the systems those models describe, guaranteeing that all those formal models are adequate for analyzing system behaviors. Case studies of systems modeled and analyzed using those languages are also presented to demonstrate the effectiveness of this approach and the developed tools in constructing high-assurance domain-specific systems
RDMA-Accelerated State Machine for Cloud Services
No full text305 pagesWith the advent of RDMA, networks that provide upward of 100Gbps data-transfer speeds and sub-microsecond latencies have become widely available. These high speeds and low delays are a disruptive departure from prior capabilities, and force a redesign of the systems and applications running above them. In this dissertation, we tackle a core question: optimal support for systems that employ data or state machine replication for strong consistency. Such systems are common and vital in the cloud, and state machine replication is a building block for stronger higher level guarantees such as the ones commonly sought in database applications. Advances thus have the potential for broad impact. This dissertation focuses on the design and implementation of Derecho, a user-space library written in C++ that offers fault-tolerant state machine replication to application subgroups. We motivate Derecho's unusual design, and show that the system's in-memory replication performs close to the network capacity for a variety of application scenarios and cluster settings. We demonstrate that the system is reliable, both through proofs and experiments: replicas maintain the same state through crash failures and network partitions, and the system will only restart correctly, after first repairing any damaged durable state on persistent storage. Derecho reexpresses Paxos protocols in a novel manner that allows replicas to agree on state updates asynchronously, resulting in continuous, non-blocking data paths. Derecho's in-memory replication outperforms traditional Paxos systems on TCP by a factor of 80X and a modern Paxos system on RDMA by a factor of 25X. Theoretical study reveals that Derecho's protocols are optimal under a model put forward by the theory community more than a decade ago, but never previously viewed as a practical goal that might be of value in deployed systems. Although the focus of the author has been quite practical throughout his work (a focus reflected in the choices of material included in this dissertation), this optimality confirms our intuition about the style of knowledge-based programming best matched to the shared state table (SST) abstraction proposed by this author, around which Derecho was built. Specifically, Derecho expresses atomic multicast and Paxos protocols using a form of coding best understood as epistemic (temporal) logic programming, which in turn is expressed over a monotonic table encoding system state that is continuously extended in a lock-free, asynchronous, uncoordinated manner. For a variety of actions important in atomic multicast or Paxos, our protocols are designed to deduce the point at which those actions can be safely taken. We think of the shared system state as a monotonic knowledge representation in which new information extends but never invalidates past information. Efficiency, for a protocol of this kind, centers on making such deductions as soon as it is safe to do so, and then ensuring that the protocols themselves impose what might be termed {\em knowledge-minimal} requirements: they should await the weakest condition adequate for safe progress. The SST design was carefully optimized to run protocols expressed this way as efficiently as possible, hence effort invested to tune and optimize protocols expressed over the SST leads to the same place that an effort to derive an optimal formulation would have arrived at. This fortuitous insight is simply that the shift in style compelled by RDMA, because of its specific latency and throughput properties, happens to favor the network model within which optimality becomes the most natural coding style! Our goals in creating Derecho were primarily practical, and it is in some ways surprising to realize that simply by setting out to build a fast data replication tool for extremely fast network hardware, we arrived at a design point in which the most optimal protocol designs from a performance perspective also would turn out to be optimal in a more formal sense. We had not anticipated this when we started the project. It is perhaps surprising that this alignment was not previously noticed by the theory community: the state machine replication as a model can be traced back to papers written 40 years ago, and there have been hundreds (if not thousands) of research papers and systems implementing the model. However, the same properties that make RDMA so disruptive for systems builders also are disruptive relative to classical ways of modeling and abstracting networks: RDMA forces us to think about shared memory models rather than purely in terms of message passing. Surely this explains why even the most efficient of the previous generation of Paxos solutions turns out to be one or more orders of magnitude slower than our Derecho protocols. What we encountered in our work should be of relevance in many other kinds of systems, protocols and distributed algorithms. We hope that future researchers will pick up the thread and carry it even further: what we achieved for atomic multicast and state machine replication would surely be possible in many other settings
Towards Accurate and Scalable Performance Modeling and Benchmarking of Cloud Applications
No full text165 pagesCloud computing now powers a significant portion of global computation, supporting everything from latency-sensitive interactive services to artificial intelligence (AI) models. As these applications continue to shape the future of cloud infrastructures, understanding their behavior is critical. In this context, accurate and scalable performance modeling and benchmarking have become essential for optimizing system performance and guiding the development of cloud infrastructure. Agile, efficient, and precise modeling and benchmarking tools can provide invaluable insights for fleet design and optimizing efficiency. Within a cloud provider, these tools can support hardware and system optimization (e.g., GPU or ASIC accelerator design), performance characterization and analysis, design space exploration, and bug reproduction. Furthermore, they can be shared with external hardware vendors for early-stage performance testing, evaluation, and joint hardware/software co-design, all while requiring minimal infrastructure support and enabling a streamlined IP-sharing framework. The highly diverse and rapidly evolving landscape of cloud applications presents significant challenges in developing modeling and benchmarking tools that accurately capture performance characteristics. For instance, while open-source benchmarks have seen significant advancements, their update speed, application diversity, and complexity cannot keep pace with the constantly changing and varied applications in real cloud deployments. As a result, engineers and researchers have to manually adapt existing production or open-source workloads into forms suitable for benchmarking. This process requires substantial expertise and a deep understanding of the workloads, making it a non-trivial investment. Consequently, maintaining and updating these benchmarks to keep up with the fast pace of cloud application development incurs high costs. Therefore, there is a strong need for new methodologies that enable efficient and accurate modeling and benchmarking of cloud applications. This thesis presents novel solutions to address these challenges. We first introduce Ditto, an automated cloning framework for end-to-end interactive cloud services, including both monolithic applications and microservices. It begins by capturing the dependency graph across services using distributed tracing, then reconstructs the high-level control and data flow within each service. Finally, Ditto generates system calls and user-level assembly to capture both on-CPU and off-CPU behavior. This process is fully automated, allowing users to clone and benchmark services without needing expertise in their implementation. Our evaluation demonstrates that synthetic applications generated by Ditto respond to changes in input load, platform, resource allocation, and deployment configuration in the same way as the original workloads. Next, we present Mystique, an efficient and scalable framework for generating AI benchmarks. By leveraging execution traces directly captured from production workflows, Mystique generates benchmarks using a "replay-as-benchmark" approach. The trace records runtime information of a model at the operator level, and Mystique faithfully replays it to accurately reproduce the original performance. We demonstrate that our methodology generates AI benchmarks that closely mirror the original applications, both in terms of execution time and system-level metrics, while remaining easy to use and portable across platforms without the need for regeneration. We also highlight several use cases for Mystique, including early-stage platform evaluation, subtrace replay, and scaled-down performance testing. Finally, we discuss Lumos, a trace-driven performance modeling and estimation toolkit for large-scale training of large language models (LLMs). By leveraging built-in profiling tools from machine learning (ML) frameworks, Lumos constructs a comprehensive execution graph to capture the runtime behaviors of LLMs and build accurate performance models. It also provides users with a convenient way to explore various model and deployment configurations through graph manipulation and simulation, streamlining the exploration process. We evaluate Lumos using various GPT-3 model variants on a production-scale cluster and demonstrate that it accurately reproduces and predicts execution times and detailed performance characteristics across different models and configurations
Towards Efficient And Reliable Publish-Subscribe For Geo-Distributed Datacenters
No full textTopic-based publish-subscribe systems have become an increasingly critical part of infrastructure that supports today's cloud-based services. Such systems collect, store, and disseminate log records over many datacenters across the globe, each containing thousands of inexpensive fault-prone machines. Reliability, scalability, and high performance are all desirable. Achieving all these properties at the same time is a significant research challenge. Scaling out data collection and dissemination naively could bring about unconventionally high bandwidth over-subscription and network congestion. Storing data for reliability comes with the cost of storage capacity and potential system slowdown. This thesis seeks to meet the challenge by providing novel building blocks for topic-based publish-subscribe systems. We introduce the Sprinkler reliable broadcast facility that scales out data dissemination over geo-distributed datacenters. We propose a storage framework that supports the concept of rediversification to scale up the storage. We present a structure called funnelling trees to scale out data collection. We show the design and implementation of a novel form of garbage collection, a technique that can be incorporated with all three tasks to reduce stress brought by high workload. Under typical web caching workloads, the benefit of garbage collection is significant. Together with these components, this thesis provides a complete picture including frameworks, protocols, and implementations. We address all three ele- ments in a topic-based publish-subscribe service-data collection, storage, and dissemination. Sprinkler achieves both reliability and scalability across geodistributed datacenters under sustained high workload
Building a Scalable Shared Log
No full text115 pagesThe shared log paradigm is at the heart of modern distributed applications in the growing cloud computing industry. Often, application logs must be stored durably for analytics, regulations, or failure recovery, and their smooth operation depends closely on how the log is implemented. An ideal implementation of the shared log abstraction should be capable of growing elastically in response to the needs of its client applications, without compromising availability; recover quickly from failures; adopt the data layout that best matches the performance requirement of its clients; scale write throughput without giving up on total order; and offer a low latency that satisfies applications' requirements. Unfortunately, no single shared log today can offer this combination of features. In particular, no shared log provides both total order and seamless reconfiguration, i.e., the capability to reconfigure the service without compromising its global availability. Additionally, no shared log provides both total order and low latency. In this dissertation, we analyze the challenges of achieving both total order and seamless reconfiguration, and of attaining both total order and low latency. Based on this analysis, we have built and evaluated two systems, Scalog and Ziplog, to demonstrate how to address these challenges. Scalog is a new implementation of the shared log abstraction that offers an unprecedented combination of features for continuous smooth delivery of service: Scalog allows applications to customize data placement, supports reconfiguration with no loss in availability, and recovers quickly from failures. At the same time, Scalog provides high throughput and total order. At its core is a novel ordering protocol that (1) efficiently merges the order in which records are stored at each shard to produce a single global order across shards, and (2) collates and processes records in the same batch that may originate from any client and be stored at any shard. This novel design enables Scalog to scale to thousands of shards while providing seamless reconfiguration, flexible data placement, and quick failure recovery. Ziplog is a new implementation of a totally ordered shared log that achieves latency and throughput comparable to what today can only be delivered by systems that optimize only one of these metrics at the expense of the other. Ziplog achieves these results through a new API that, instead of adding new records to the log through a linearizable Append operation, relies on a linearizable InsertAfter operation that specifies the log position past which the new record should be inserted. This new API allows Ziplog to totally order records across shards without needing cross-shard coordination and with an average latency of fewer than three message delays
Scaling Searchable and Transactional Storage Systems
Get PDFData is the lifeblood of modern computing and the systems that store it have
taken a prominent place in the infrastructure of practically every modern
startup, business, or research application. Not-so-recent trends in
distributed storage systems have removed features---such as secondary
attribute search or transactions---that applications used to take for granted.
These missing features must be reimplemented at the application level, or the
application must be carefully constructed to work around their absence.
This thesis explores work on four systems that represent advances in reversing
this trend. First, it looks at HyperDex, a system which provides efficient
secondary attribute search. Second, it presents two transactional storage
systems, Warp and Consus. Warp targets a single data center environment while
Consus targets a geo-replicated deployment and the differences in their design
reflect these two considerations. Finally, this thesis presents the Warp
Transactional Filesystem that shows a positive example of how the
transactional properties of Warp can be extended to provide application-level
transactional guarantees. Finally, the thesis looks at the broader impact of
these systems and how the evolution of the systems could be used to inform the
development of future distributed systems
Reducing Costs Of Byzantine Fault Tolerant Distributed Applications
Get PDFByzantine fault tolerance (BFT) is a powerful technique for building software that tolerates arbitrary failures. The technique has been developed since the 70s and has a rich research literature. Yet no production system has adopted the technique, despite an increasing need from today's large and complex systems. An important reason is that a BFT system incurs significantly higher costs than a crash-tolerant counterpart. The costs include developmental costs, as a BFT system is harder to design and implement correctly, and operational costs, as a BFT system requires to run on more machines, employs more expensive cryptographic operations, and sends more and larger messages. This dissertation attempts to reduce both developmental and operational costs of BFT distributed applications. In the first part, we propose an approach to translate existing crash-tolerant systems to Byzantine-fault-tolerant. Our approach makes fewer assumptions about the source crash-tolerant distributed applications, and thus it is applicable to a larger set of applications than existing approaches. We propose and prove correct our basic approach. Then we extend the basic approach to large scale distributed applications and propose additional mechanisms to deal with practical problems in such settings-namely, replication and host churns. We evaluate our scalable translation approach by a simulation and case studies. The second part of the dissertation presents a novel Byzantine replication approach that focuses on reducing resource costs (but can also be used as a translation). By leveraging an external reconfiguration service, our replication approach requires only t + 1 replicas and t witnesses (lighter hosts) to tolerate t Byzantine faults. Our approach also uses inexpensive HMAC signatures and imposes a chain communication pattern between the replicas to reduce CPU and network consumptions. We also propose a variation of the approach, in which Byzantine hosts do not forge CRC checksums, to further reduce the resource costs. In particular, it uses t + 1 replicas, CRC checksums, and t fewer rounds of communication. We evaluate the performance of a prototype of each variation in the common case, when it runs without failures
Towards A Secure Federated Information System
Get PDFWe are entering an era in which federated information systems are widely used to share information and computation. Federated systems support new services and capabilities by integrating computer systems across independent administrative domains. Each domain has policies for security, but does not fully trust other domains to enforce them. This dissertation explores, in two parts, the challenge of designing and building federated information systems that are secure and reliable while supporting mutually distrusting participants. First, this dissertation presents Fabric, a new system and language for building secure federated information systems. Fabric allows heterogeneous network nodes to securely share information and computation despite mutual distrust. It uses optimistic, nested transactions to ensure global consistency, and has a peerto-peer dissemination layer for better availability and load balancing. Fabric's high-level programming language provides a rich, Java-like object model, and keeps distribution and persistence largely transparent to programmers. It supports data shipping and function shipping: both information and computation can move between nodes to meet security requirements or to improve performance. Confidentiality and integrity policies on objects are enforced through a combination of compile-time and run-time mechanisms. Results from building Fabric applications suggest that Fabric has a clean and concise programming model, offers good performance, and enforces security. Next, this dissertation examines the security implications of providing referential integrity in a federated system. Referential integrity ensures that named resources can be accessed when needed. This is an important property for re- liability and security. However, the attempt to provide referential integrity can itself lead to security vulnerabilities that are currently not well understood. This dissertation identifies three such referential security vulnerabilities, and formalizes security conditions corresponding to their absence. A language model captures key aspects of programming distributed systems with named, persistent resources in the presence of an adversary. A new type system is proved to enforce the conditions for referential security
- …
