We present Charlotte, a framework for composable, Authenticated Distributed Data Structures (ADDSs). Charlotte data is stored in blocks that reference each other by hash. Together, all Charlotte blocks form a directed acyclic graph, the blockweb; all observers and applications use subgraphs of the blockweb. Unlike in prior systems, Charlotte data structures are composable: applications and data structures can operate fully independently when possible, but can also share blocks when desired. To support this composability, we define a language-independent format for Charlotte blocks and a network API for Charlotte servers.

ADDSs guarantee that data is immutable and self-authenticating: data referenced will be unchanged when it is retrieved. Charlotte extends traditional ADDS guarantees by allowing applications to plug in their own mechanisms for ensuring availability and integrity of data structures. Unlike most traditional distributed systems, including blockchains, Charlotte supports heterogeneous trust: different observers may have their own beliefs about who might fail, and how. Despite heterogeneity of trust, Charlotte presents each observer with a consistent, available view of data.

We demonstrate the flexibility of Charlotte by implementing a variety of integrity mechanisms, including Consensus and Proof-of-Work. We study the power of disentangling availability and integrity mechanisms by building a variety of applications. The results from these example applications suggest that future ADDS developers can use Charlotte to build flexible, fast, composable applications with strong guarantees.

In distributed systems, a group of learners achieve consensus when, by observing the output of some acceptors, they all arrive at the same value. Consensus is crucial for ordering transactions in failure-tolerant systems. Traditional consensus algorithms are homogeneous in three ways:

• all learners are treated equally,
• all acceptors are treated equally, and
• all failures are treated equally.

These assumptions, however, are unsuitable for cross-domain applications, including blockchains, where not all acceptors are equally trustworthy, and not all learners have the same assumptions and priorities. We present the first consensus algorithm to be heterogeneous in all three respects. Learners set their own mixed failure tolerances over differently trusted sets of acceptors. We express these assumptions in a novel Learner Graph, and demonstrate sufficient conditions for consensus. We present Heterogeneous Paxos: an extension of Byzantine Paxos. Heterogeneous Paxos achieves consensus for any viable Learner Graph in best-case three message sends, which is optimal. We present a proof-of-concept implementation, and demonstrate how tailoring for heterogeneous scenarios can save resources and latency.

Modern applications often operate on data in multiple administrative domains. In this federated setting, participants may not fully trust each other. These distributed applications use transactions as a core mechanism for ensuring reliability and consistency with persistent data. However, the coordination mechanisms needed for transactions can both leak confidential information and allow unauthorized influence.

By implementing a simple attack, we show these side channels can be exploited. However, our focus is on preventing such attacks. We explore secure scheduling of atomic, serializable transactions in a federated setting. While we prove that no protocol can guarantee security and liveness in all settings, we establish conditions for sets of transactions that can safely complete under secure scheduling. Based on these conditions, we introduce staged commit, a secure scheduling protocol for federated transactions. This protocol avoids insecure information channels by dividing transactions into distinct stages. We implement a compiler that statically checks code to ensure it meets our conditions, and a system that schedules these transactions using the staged commit protocol. Experiments on this implementation demonstrate that realistic federated transactions can be scheduled securely, atomically, and efficiently.

Blockchains offer a useful abstraction: a trustworthy, decentralized log of totally ordered transactions. Traditional blockchains have problems with scalability and efficiency, preventing their use for many applications. These limitations arise from the requirement that all participants agree on the total ordering of transactions. To address this fundamental shortcoming, we introduce Charlotte, a system for maintaining decentralized, authenticated data structures, including transaction logs. Each data structure – indeed, each block – specifies its own availability and integrity properties, allowing Charlotte applications to retain the full benefits of permissioned or permissionless blockchains. In Charlotte, a block can be atomically appended to multiple logs, allowing applications to be interoperable when they want to, without inefficiently forcing all applications to share one big log. We call this open graph of interconnected blocks a blockweb. We allow new kinds of blockweb applications that operate beyond traditional chains. We demonstrate the viability of Charlotte applications with proof-of-concept servers running interoperable blockchains. Using performance data from our prototype, we estimate that when compared with traditional blockchains, Charlotte offers multiple orders of magnitude improvement in speed and energy efficiency.

The robustness of distributed systems is usually phrased in terms of the number of failures of certain types that they can withstand. However, these failure models are too crude to describe the different kinds of trust and expectations of participants in the modern world of complex, integrated systems extending across different owners, networks, and administrative domains. Modern systems often exist in an environment of heterogeneous trust, in which different participants may have different opinions about the trustworthiness of other nodes, and a single participant may consider other nodes to differ in their trustworthiness. We explore how to construct distributed protocols that meet the requirements of all participants, even in heterogeneous trust environments. The key to our approach is using lattice-based information flow to analyse and prove protocol properties. To demonstrate this approach, we show how two earlier distributed algorithms can be generalized to work in the presence of heterogeneous trust: first, Heterogeneous Fast Consensus, an adaptation of the earlier Bosco Fast Consensus protocol; and second, Nysiad, an algorithm for converting crash-tolerant protocols to be Byzantine-tolerant. Through simulations, we show that customizing a protocol to a heterogeneous trust configuration yields performance improvements over the conventional protocol designed for homogeneous trust.

We present a method for identifying the authorship of online visual media. Leveraging webcomics as a source of large numbers of images from the same author, we train learning algorithms to classify imagery from ten different webcomics. We propose a set of hand-coded image features, motivated by the various artistic elements, from color palette to line style, that are considered by the author. In so doing, we aim to learn classifications that robustly generalize to new samples of the same comics and which capture similar judgments of style as are made by human viewers. We evaluate the accuracy of our system using various learning algorithms, finding that it successfully classifies novel samples with up to 94% accuracy. To test whether the judgments of our system correspond to human perceptions of composition and style, we use our trained system to classify imagery from untrained webcomics and qualitatively evaluate the similarity of the untrained comics to their returned classifications.

Paxos is a family of widely adopted distributed, crash-failure tolerant consensus protocols. While it can be proven correct, it is by not guaranteed to operate at a steady rate. While it is true that no fault-tolerant deterministic consensus protocol can be sure to arrive at any decision in finite time, certain real-world concessions are often made to at least bound delays. Under certain conditions, however, an otherwise reliable and speedy implementation of Paxos can delay dramatically. For example, if a small group of “acceptor” processes acts slower than the majority, they can find themselves with a backlog of old inputs to process should they ever be needed for a quorum. If the delay is in the line of communication, a such backlog is avoidable by replacing traditional FIFO channels (such as TCP) with channels more likely to deliver recent requests, even while older ones are in transit. If the acceptors themselves are queueing up information to process, a leader can increase the speed and stability of the protocol by sending proposals first to a quorum of acceptors which have been fastest recently, and to the remainder only if necessary. We provide a theoretical basis for quantifying these problems, as well as a test implementation demonstrating such delays as well as these solutions.

We consider anonymous communication between pairs of nodes in the presence of an adversary who can observe all network traffic. Existing schemes involve partially trusted central servers, a large amount of cover traffic, or high latency. We propose a scheme which improves upon the trade-off, in which messages require only logarithmic time to deliver, as well as computational time to send. In this scheme, any node receiving a message applies a private decryption key to discover content, or instructions to forward the message to zero or more other nodes. Furthermore, when a node applies its decryption key to a message not encrypted with that node’s encryption key, the result is indistinguishable from a message with forwarding instructions. A sender wraps a message in an onion route of logarithmic length, branching (forwarding to multiple nodes) at random points, resulting in a tree of forwarded messages. Nodes wait to initiate messages of their own until they have received a message, so it is indistinguishable whether they are sending or forwarding. Through analysis and simulation, we show this system preserves a high degree of sender and receiver anonymity, as well as unlinkability between communicating pairs.

The NuSTAR (Nuclear Spectroscopic Telescope ARray) spacecraft, set to launch in February 2012, will be capable of performing some of the most detailed X-Ray astronomical observations ever made in the 5-80 keV energy range. The source positioning accuracy of the telescope is limited by the ability to correct for thermal distortions and movement of the optics relative to the focal plane, as well as the overall aspect of the optics bench. These are more than average for space-based observatories, because a ten meter deployable mast, utilized to reduce the size of the launch vehicle, allows for significant thermal distortions. In order to predict the on-orbit performance of the instrument, the NuSTAR team has developed NuSIM, a software based simulation of NuSTAR. My SURF has consisted mainly of the generation of parametrically-changing databases of the mast geometry in order to interrogate the robustness of the on-orbit accuracy of the science system’s data reconstruction algorithms within NuSIM. This method has been used to test the Finite Element Model (FEM) simulation results of the observatory’s structure, by using a conceptual model of the mast geometry. Furthermore, I have explored additional possible sources of error, such as calculating light scattering from the simulated optics. This project has contributed to the verification of key science requirements of NuSTAR in advance, most notably the level one requirement on localization of a point source in celestial coordinates.