Bücher von Dennis Shasha

Blockchains are meant to provide an append-only sequence (ledger) of transactions. Security commonly relies on a consensus protocol in which forks in the sequence are either prevented completely or are exponentially unlikely to last more than a few blocks. This monograph proposes the design of algorithms and a system to achieve high performance (a few seconds from the time of initiation for transactions to enter the blockchain), the absence of forks, and a very low energy cost (a per transaction cost that is a factor of a billion or more less than bitcoin). The foundational component of this setup is a group of satellites whose blockchain protocol code can be verified and burned into read-only memory. Because such satellites can perhaps be destroyed but cannot be captured (unlike even fortified terrestrial servers), a reasonable assumption is that the blockchain protocol code in the satellites may fail to make progress either permanently or intermittently but will not be traitorous. A second component of this setup is a group of terrestrial sites whose job is to broadcast information about blocks and to summarize the blockchain ledger. These can be individuals who are eager to get a fee for service. Even if many of these behave traitorously (against their interests as fee-collectors), a small number of honest ones is sufficient to ensure safety and liveness. The third component of this setup is a Mission Control entity which will act very occasionally to assign roles to terrestrial sites and time slots to satellites. These assignments will be multi-signed using the digital signatures of a widely distributed group of human governors. Given these components and these reasonable assumptions, the protocol described in this monograph, called Bounce, will achieve ledger functionality for arbitrarily sized blocks at under five seconds per block and at negligible energy cost. This monograph will discuss the overall architecture and algorithms of such a system, the assumptions it makes, and the guarantees it gives.

Computational analysis of natural science experiments often confronts noisy data due to natural variability in environment or measurement. Drawing conclusions in the face of such noise entails a statistical analysis. Parametric statistical methods assume that the data is a sample from a population that can be characterized by a specific distribution (e.g., a normal distribution). When the assumption is true, parametric approaches can lead to high confidence predictions. However, in many cases particular distribution assumptions do not hold. In that case, assuming a distribution may yield false conclusions. The companion book Statistics is Easy, gave a (nearly) equation-free introduction to nonparametric (i.e., no distribution assumption) statistical methods. The present book applies data preparation, machine learning, and nonparametric statistics to three quite different life science datasets. We provide the code as applied to each dataset in both R and Python 3. We also include exercises for self-study or classroom use.

Statistics is the activity of inferring results about a population given a sample. Historically, statistics books assume an underlying distribution to the data (typically, the normal distribution) and derive results under that assumption. Unfortunately, in real life, one cannot normally be sure of the underlying distribution. For that reason, this book presents a distribution-independent approach to statistics based on a simple computational counting idea called resampling. This book explains the basic concepts of resampling, then system atically presents the standard statistical measures along with programs (in the language Python) to calculate them using resampling, and finally illustrates the use of the measures and programs in a case study. The text uses junior high school algebra and many examples to explain the concepts. Th e ideal reader has mastered at least elementary mathematics, likes to think procedurally, and is comfortable with computers. Table of Contents: The Basic Idea / Pragmatic Considerations when Using Resampling / Terminology / The Essential Stats / Case Study: New Mexico's 2004 Presidential Ballots / References / Bias Corrected Confidence Intervals / Appendix B

Search structures support the fundamental data storage primitives on key-value pairs: insert a pair, delete by key, search by key, and update the value associated with a key. Concurrent search structures are parallel algorithms to speed access to search structures on multicore and distributed servers. These sophisticated algorithms perform fine-grained synchronization between threads, making them notoriously difficult to design correctly. Indeed, bugs have been found both in actual implementations and in the designs proposed by experts in peer-reviewed publications. The rapid development and deployment of these concurrent algorithms has resulted in a rift between the algorithms that can be verified by the state-of-the-art techniques and those being developed and used today. The goal of this book is to show how to bridge this gap in order to bring the certified safety of formal verification to high-performance concurrent search structures. Similar techniques and frameworks can be applied to concurrent graph and network algorithms beyond search structures.

In the history of modern computation, large mechanical calculators preceded computers. A person would sit there punching keys according to a procedure and a number would eventually appear. Once calculators became fast enough, it became obvious that the critical path was the punching rather than the calculation itself. That is what made the stored program concept vital to further progress. Once the instructions were stored in the machine, the entire computation could run at the speed of the machine. This book shows how to do the same thing for DNA computing. Rather than asking a robot or a person to pour in specific strands at different times in order to cause a DNA computation to occur (by analogy to a person punching numbers and operations into a mechanical calculator), the DNA instructions are stored within the solution and guide the entire computation. We show how to store straight line programs, conditionals, loops, and a rudimentary form of subroutines. To achieve this goal, the book proposes a complete language for describing the intrinsic topology of DNA complexes and nanomachines, along with the dynamics of such a system. We then describe dynamic behavior using a set of basic transitions, which operate on a small neighborhood within a complex in a well-defined way. These transitions can be formalized as purely syntactical functions of the string representations. Building on that foundation, the book proposes a novel machine motif which constitutes an instruction stack, allowing for the clocked release of an arbitrary sequence of DNA instruction or data strands. The clock mechanism is built of special strands of DNA called "e;"e;tick"e;"e; and "e;"e;tock."e;"e; Each time a "e;"e;tick"e;"e; and "e;"e;tock"e;"e; enter a DNA solution, a strand is released from an instruction stack (by analogy to the way in which as a clock cycle in an electronic computer causes a new instruction to enter a processing unit). As long as there remain strands on the stack, the next cycle will release a new instruction strand. Regardless of the actual strand or component to be released at any particular clock step, the "e;"e;tick"e;"e; and "e;"e;tock"e;"e; fuel strands remain the same, thus shifting the burden of work away from the end user of a machine and easing operation. Pre-loaded stacks enable the concept of a stored program to be realized as a physical DNA mechanism. A conceptual example is given of such a stack operating a walker device. The stack allows for a user to operate such a clocked walker by means of simple repetition of adding two fuel types, in contrast to the previous mechanism of adding a unique fuel -- at least 12 different types of strands -- for each step of the mechanism. We demonstrate by a series of experiments conducted in Ned Seeman's lab that it is possible to "e;"e;initialize"e;"e; a clocked stored program DNA machine. We end the book with a discussion of the design features of a programming language for clocked DNA programming. There is a lot left to do. Table of Contents: Introduction / Notation / A Topological Description of DNA Computing / Machines and Motifs / Experiment: Storing Clocked Programs in DNA / A Clocked DNA Programming Language