Publications

Christos Chrysafis,
Ben Collins,
Scott Dugas,
Jay Dunkelberger,
Moussa Ehsan,
Scott Gray,
Alec Grieser,
Ori Herrnstadt,
Kfir LevAri,
Tao Lin,
Mike McMahon,
Nicholas Schiefer, and
Alexander Shraer,
“FoundationDB Record Layer: A MultiTenant Structured Datastore”,
to appear in
2019 International Conference on Management of Data, Industry Track (SIGMOD 2019),
2019.
Abstract
The FoundationDB Record Layer is an open source library that provides a recordoriented data store with semantics similar to a relational database implemented on top of FoundationDB, an ordered, transactional keyvalue store. The Record Layer provides a lightweight, highly extensible way to store structured data. It offers schema management and a rich set of query and indexing facilities, some of which are not usually found in traditional relational databases, such as nested record types, indexes on commit versions, and indexes that span multiple record types. The Record Layer is stateless and built for massive multitenancy, encapsulating and isolating all of a tenant's state, including indexes, into a separate logical database. We demonstrate how the Record Layer is used by CloudKit, Apple's cloud backend service, to provide powerful abstractions to applications serving hundreds of millions of users. CloudKit uses the Record Layer to host billions of independent databases, many with a common schema. Features provided by the Record Layer enable CloudKit to provide richer APIs and stronger semantics with reduced maintenance overhead and improved scalability.

Peter Ahrens,
Helen Xu, and
Nicholas Schiefer,
“A Fill Estimation Algorithm for Sparse Matrices and Tensors in Blocked Formats”,
2018 IEEE International Parallel and Distributed Processing Symposium (IPDPS 2018),
2018.
Abstract
Many sparse matrices and tensors from a variety of applications, such as finite element methods and computational chemistry, have a natural aligned rectangular nonzero block structure. Researchers have designed highperformance blocked sparse operations which can take advantage of this sparsity structure to reduce the complexity of storing the locations of nonzeros. The performance of a blocked sparse operation depends on how well the block size reflects the structure of nonzeros in the tensor. Sparse tensor structure is generally unknown until runtime, so block size selection must be efficient. The fill is a quantity which, for some block size, relates the number of nonzero blocks to the number of nonzeros. Many performance models use the fill to help choose a block size. However, the fill is expensive to compute exactly. We present a samplingbased algorithm called Phil to estimate the fill of sparse matrices and tensors in any format. We provide theoretical guarantees for sparse matrices and tensors, and experimental results for matrices. The existing stateoftheart fill estimation algorithm, which we will call OSKI, runs in time linear in the number of elements in the tensor. The number of samples Phil needs to compute a fill estimate is unrelated to the number of nonzeros and depends only on the order (number of dimensions) of the tensor, desired accuracy of the estimate, desired probability of achieving this accuracy, and number of considered block sizes. We compare Phil and OSKI on a suite of 42 matrices. On most inputs, Phil estimates the fill at least 2 times faster and often more than 20 times faster than OSKI. Phil consistently produced accurate estimates; in all cases that we tested Phil was faster and/or more accurate than OSKI. Finally, we find that Phil and OSKI produce comparable speedups in multicore blocked sparse matrixvector multiplication (SpMV) when the block size was chosen using fill estimates in a model due to Vuduc et al.

Nicholas Schiefer and
Erik Winfree, “Time Complexity of Computation and Construction in the Chemical Reaction NetworkControlled Tile Assembly Model”,
22nd International Conference on DNA Computing and Molecular Programming
(DNA22),
2016.
Abstract
In isolation, chemical reaction networks and tilebased selfassembly are wellstudied models of chemical computation. Previously, we introduced the chemical reaction networkcontrolled tile assembly model (CRNTAM), in which a stochastic chemical reaction network can act as a nonlocal control and signalling system for tilebased assembly, and showed that the CRNTAM can perform several tasks related to the simulation of Turing machines and construction of algorithmic shapes with lower space or program complexity than in either of its parent models. Here, we introduce a kinetic variant of the CRNTAM and investigate the time complexity of computation and construction. We analyze the time complexity of decision problems in the CRNTAM, and show that decidable languages can be decided as efficiently by CRNTAM programs as by Turing machines. We also give a lower bound for the spacetime complexity of CRNTAM computation that rules out efficient parallel stack machines. We provide efficient parallel implementations of nondeterministic computations, showing among other things that CRNTAM programs can decide languages in NTIME ∩ coNTIME(f(n)) in O(f(n) + n + log c) time with (1  exp (c)) probability, using volume exponential in n. Lastly, we provide basic mechanisms for parallel computations that share information and illustrate the limits of parallel computation in the CRNTAM.

Nicholas Schiefer and
Erik Winfree, “Universal Computation and Optimal Construction in the Chemical Reaction NetworkControlled Tile Assembly Model”,
21st International Conference on DNA Computing and Molecular Programming
(DNA21),
2015.
Abstract
Tilebased selfassembly and chemical reaction networks provide two wellstudied models of scalable DNAbased computation. Although tile selfassembly provides a powerful framework for describing Turinguniversal selfassembling systems, assembly logic in tile selfassembly is localized, so that only the nearby environment can affect the process of selfassembly. We introduce a new model of tilebased selfassembly in which a wellmixed chemical reaction network interacts with selfassembling tiles to exert nonlocal control on the selfassembly process. Through simulation of multistack machines, we demonstrate that this new model is efficiently Turinguniversal, even when restricted to unbounded space in only one spatial dimension. Using a natural notion of program complexity, we also show that this new model can produce many complex shapes with programs of lower complexity. Most notably, we show that arbitrary connected shapes can be produced by a program with complexity bounded by the Kolmogorov complexity of the shape, without the large scale factor that is required for the analogous result in the abstract tile assembly model. These results suggest that controlled selfassembly provides additional algorithmic power over tileonly selfassembly, and that nonlocal control enhances our ability to perform computation and algorithmically selfassemble structures from small input programs.
Contact
 Email: