Publications

Informally, a distributed system is grassroots if it is permissionless and can have autonomous, independently-deployed instances - geographically and over time - that may interoperate voluntarily once interconnected. More formally, in a grassroots system the set of all correct behaviors of a set of agents P is strictly included in the set of the correct behaviors of P when they are embedded within a larger set of agents P' ⊃ P. Grassroots systems are potentially important as they may allow communities to conduct their social, economic, civic, and political lives in the digital realm solely using their members' networked computing devices (e.g., smartphones), free of third-party control, surveillance, manipulation, coercion, or rent seeking (e.g., by global digital platforms such as Facebook or Bitcoin). Client-server/cloud computing systems are not grassroots, and neither are systems designed to have a single global instance (Bitcoin/Ethereum with hardwired seed miners/bootnodes), and systems that rely on a single global data structure (IPFS, DHTs). An example grassroots system would be a serverless smartphone-based social network supporting multiple independently-budding communities that can merge when a member of one community becomes also a member of another. Here, we formalize the notion of grassroots distributed systems; describe a grassroots dissemination protocol for the model of asynchrony and argue its safety, liveness, and being grassroots; extend the implementation to mobile (address-changing) devices that communicate via an unreliable network (e.g. smartphones using UDP); and discuss how grassroots dissemination can realize grassroots social networking and grassroots cryptocurrencies. The mathematical construction employs distributed multiagent transition systems to define the notions of grassroots protocols, to specify the grassroots dissemination protocols, and to prove their correctness. The protocols use the blocklace - a distributed, partially-ordered counterpart of the replicated, totally-ordered blockchain.

Preventing fake or duplicate digital identities (aka sybils) from joining a digital community may be crucial to its survival, especially if it utilizes a consensus protocol among its members or employs democratic governance, where sybils can undermine consensus, tilt decisions, or even take over. Here, we explore the use of a trust-graph of identities, with edges representing trust among identity owners, to allow a community to grow indefinitely without increasing its sybil penetration. Since identities are admitted to the digital community based on their trust by existing digital community members, corrupt identities, which may trust sybils, also pose a threat to the digital community. Sybils and their corrupt perpetrators are together referred to as byzantines, and the overarching aim is to limit their penetration into a digital community. We propose two alternative tools to achieve this goal. One is graph conductance, which works under the assumption that honest people are averse to corrupt ones and tend to distrust them. The second is vertex expansion, which relies on the assumption that there are not too many corrupt identities in the community. Of particular interest is keeping the fraction of byzantines below one third, as it would allow the use of Byzantine Agreement (Lamport et al., 1982) for consensus as well as for sybil-resilient social choice (Shahaf et al., 2019). This paper considers incrementally growing a trust graph and shows that, under its key assumptions and additional requirements, including keeping the conductance or vertex expansion of the community trust graph sufficiently high, a community may grow safely, indefinitely.

The recent advent of CRISPR and other molecular tools enabled the reconstruction of cell lineages based on induced DNA mutations and promises to solve the ones of more complex organisms. To date, no lineage reconstruction algorithms have been rigorously examined for their performance and robustness across dataset types and number of cells. To benchmark such methods, we decided to organize a DREAM challenge using in vitro experimental intMEMOIR recordings and in silico data for a C. elegans lineage tree of about 1,000 cells and a Mus musculus tree of 10,000 cells. Some of the 22 approaches submitted had excellent performance, but structural features of the trees prevented optimal reconstructions. Using smaller sub-trees as training sets proved to be a good approach for tuning algorithms to reconstruct larger trees. The simulation and reconstruction methods here generated delineate a potential way forward for solving larger cell lineage trees such as in mouse.

Cell lineage analysis aims to uncover the developmental history of an organism back to its cell of origin. Recently, novel in vivo methods utilizing genome editing enabled important insights into the cell lineages of animals. In contrast, human cell lineage remains restricted to retrospective approaches, which still lack resolution and cost-efficient solutions. Here, we demonstrate a scalable platform based on short tandem repeats targeted by duplex molecular inversion probes. With this human cell lineage tracing method, we accurately reproduced a known lineage of DU145 cells and reconstructed lineages of healthy and metastatic single cells from a melanoma patient who matched the anatomical reference while adding further refinements. This platform allowed us to faithfully recapitulate lineages of developmental tissue formation in healthy cells. In summary, our lineage discovery platform can profile informative somatic mutations efficiently and provides solid lineage reconstructions even in challenging low-mutation-rate healthy single cells.

Preventing fake or duplicate e-identities (aka sybils) from joining an e-community may be crucial to its survival, especially if it utilizes a consensus protocol among its members or employs democratic governance, where sybils can undermine consensus, tilt decisions, or even take over. Here, we explore the use of a trust graph of identities, with trust edges representing trust among identity owners, to allow a community to grow without increasing its sybil penetration. Since identities are admitted to the e-community based on their trust by existing e-community members, corrupt identities, which may trust sybils, also pose a threat to the e-community. Sybils and their corrupt perpetrators are together referred to as Byzantines, and our overarching aim is to limit their penetration into an e-community. Our key tool in achieving this is graph conductance, and our key assumption is that honest people are averse to corrupt ones and tend to distrust them. Of particular interest is keeping the fraction of Byzantines below one third, as it would allow the use of Byzantine Agreement (see Lamport et al. The Byzantine generals problem, ACM Transactions on Programming Languages and Systems, 4(3):382-401, 1982) for consensus as well as for sybil-resilient social choice (see Shahaf et al., Sybil-resilient reality-aware social choice, arXiv preprint arXiv:1807.11105, 2019). We consider sequences of incrementally growing trust graphs and show that, under our key assumption and additional requirements, including keeping the conductance of the community trust graph sufficiently high, a community may grow safely.

Short tandem repeats (STRs) are polymorphic genomic loci valuable for various applications such as research, diagnostics and forensics. However, their polymorphic nature also introduces noise duringin vitroamplification, making them difficult to analyze. Although it is possible to overcome stutter noise by using amplification-free library preparation, such protocols are presently incompatible with single cell analysis and with targeted-enrichment protocols. To address this challenge, we have designed a method for direct measurement of in vitro noise. Using a synthetic STR sequencing library, we have calibrated a Markov model for the prediction of stutter patterns at any amplification cycle. By employing this model, we have managed to genotype accurately cases of severe amplification bias, and biallelic STR signals, and validated our model for several high-fidelity PCR enzymes. Finally, we compared this model in the context of a naive STR genotyping strategy against the state-of-the-art on a benchmark of single cells, demonstrating superior accuracy.

Considering the possibility of achieving an e-democracy based on long-established foundations that strengthen both real-world democracies and virtual Internet communities.

Three recent single-cell papers use novel CRISPR-Cas9-sgRNA genome editing methods to shed light on the zebrafish cell lineage tree.

Background: We have previously presented a formal language for describing population dynamics based on environment-dependent Stochastic Tree Grammars (eSTG). The language captures in broad terms the effect of the changing environment while abstracting away details on interaction among individuals. An eSTG program consists of a set of stochastic tree grammar transition rules that are context-free. Transition rule probabilities and rates, however, can depend on global parameters such as population size, generation count and elapsed time. In addition, each individual may have an internal state, which can change during transitions. Results: This paper presents eSTGt (eSTG tool), an eSTG programming and simulation environment. When executing a program, the tool generates the corresponding lineage trees as well as the internal states values, which can then be analyzed either through the tool's GUI or using MATLAB's command-line environment. Conclusions: The presented tool allows researchers to use existing biological knowledge in order to model the dynamics of a developmental process and analyze its behavior throughout the historical events. Simulated lineage trees can be used to validate various hypotheses in silico and to predict the behavior of dynamical systems under various conditions. Written under MATLAB environment, the tool also enables to easily integrate the output data within the user's downstream analysis.

Background: Precise description of the dynamics of biological processes would enable the mathematical analysis and computational simulation of complex biological phenomena. Languages such as Chemical Reaction Networks and Process Algebras cater for the detailed description of interactions among individuals and for the simulation and analysis of ensuing behaviors of populations. However, often knowledge of such interactions is lacking or not available. Yet complete oblivion to the environment would make the description of any biological process vacuous. Here we present a language for describing population dynamics that abstracts away detailed interaction among individuals, yet captures in broad terms the effect of the changing environment, based on environment-dependent Stochastic Tree Grammars (eSTG). It is comprised of a set of stochastic tree grammar transition rules, which are context-free and as such abstract away specific interactions among individuals. Transition rule probabilities and rates, however, can depend on global parameters such as population size, generation count, and elapsed time. Results: We show that eSTGs conveniently describe population dynamics at multiple levels including cellular dynamics, tissue development and niches of organisms. Notably, we show the utilization of eSTG for cases in which the dynamics is regulated by environmental factors, which affect the fate and rate of decisions of the different species. eSTGs are lineage grammars, in the sense that execution of an eSTG program generates the corresponding lineage trees, which can be used to analyze the evolutionary and developmental history of the biological system under investigation. These lineage trees contain a representation of the entire events history of the system, including the dynamics that led to the existing as well as to the extinct individuals. Conclusions: We conclude that our suggested formalism can be used to easily specify, simulate and analyze complex biological systems, and supports modular description of local biological dynamics that can be later used as \u201cblack boxes\u201d in a larger scope, thus enabling a gradual and hierarchical definition and simulation of complex biological systems. The simple, yet robust formalism enables to target a broad class of stochastic dynamic behaviors, especially those that can be modeled using global environmental feedback regulation rather than direct interaction between individuals.

FMS-like tyrosine kinase 3 receptor internal tandem duplication (FLT3-ITD) commonly occurs in acute myeloid leukemia and is considered rare in acute lymphocytic leukemia. Acute leukemia has poor prognosis, mainly due to relapse. Standard FLT3-ITD diagnostic techniques are based on genomic polymerase chain reaction and have recently incorporated GeneScan (Applied Biosystems, Foster City, CA) to identify variations of the FLT3 gene. As this is an average-based assay utilized in a heterogeneous leukemic cell population, we hypothesized that cells of acute leukemia, considered FLT3-ITD-negative by standard methods, could possess a fraction of FLT3-ITD-positive cells. The present study employed single cell mutation analysis to evaluate the FLT3-ITD status in newly diagnosed acute myeloid leukemia (n = 5) and acute lymphocytic leukemia (n = 3) patients. A total of 541 single leukemic cells and 36 mononuclear cells from healthy volunteers were analyzed. Seven patients, considered FLT3-ITD-negative according to bulk DNA analysis, appeared to possess a small fraction of FLT3-ITD-positive cells based on single cell analysis. Moreover, this approach revealed the heterogeneity of the tumor as evident by different FLT3-ITD mutations present in the same patient. The presence of a minor clone carrying FLT3-ITD in almost all patients tested provides evidence that this lesion is a common late event in leukemogenesis. Additionally, 3 relapsed patients demonstrated loss of heterozygosity of the normal allele, affecting 25 %-100% of the cells found to be FLT3-ITD-positive. Though further clinical testing is warranted, these findings may have implications on the prognostic significance of FLT3-ITD and the use of targeted therapy.

Organism cells proliferate and die to build, maintain, renew and repair it. The cellular history of an organism up to any point in time can be captured by a cell lineage tree in which vertices represent all organism cells, past and present, and directed edges represent progeny relations among them. The root represents the fertilized egg, and the leaves represent extant and dead cells. Somatic mutations accumulated during cell division endow each organism cell with a genomic signature that is unique with a very high probability. Distances between such genomic signatures can be used to reconstruct an organism's cell lineage tree. Cell populations possess unique features that are absent or rare in organism populations (e. g., the presence of stem cells and a small number of generations since the zygote) and do not undergo sexual reproduction, hence the reconstruction of cell lineage trees calls for careful examination and adaptation of the standard tools of population genetics. Our lab developed a method for reconstructing cell lineage trees by examining only mutations in highly variable microsatellite loci (MS, also called short tandem repeats, STR). In this study we use experimental data on somatic mutations in MS of individual cells in human and mice in order to validate and quantify the utility of known lineage tree reconstruction algorithms in this context. We employed extensive measurements of somatic mutations in individual cells which were isolated from healthy and diseased tissues of mice and humans. The validation was done by analyzing the ability to infer known and clear biological scenarios. In general, we found that if the biological scenario is simple, almost all algorithms tested can infer it. Another somewhat surprising conclusion is that the best algorithm among those tested is Neighbor Joining where the distance measure used is normalized absolute distance. We include our full dataset in Tables S1, S2, S3, S4, S5 to enable further analysis of this data by others.

DNA molecules can be programmed to execute any dynamic process of chemical kinetics and can implement an algorithm for achieving consensus between multiple agents.

Here we report highlights of discussions and results presented at an International Workshop on Concepts and Models of Stem Cell Organization held on July 16th and 17th, 2012 in Dresden, Germany. The goal of the workshop was to undertake a systematic survey of state-of-the-art methods and results of clonality studies of tissue regeneration and maintenance with a particular emphasis on the hematopoietic system. The meeting was the 6th in a series of similar conceptual workshops, termed StemCellMathLab,. ²2Previous StemCellMathLabs were held in 2001, 2005, 2007 (Leipzig, Germany), 2008 [1] (London, UK), and 2010 [2] (Dresden, Germany). all of which have had the general objective of using an interdisciplinary approach to discuss specific aspects of stem cell biology. The StemCellMathLab 2012, which was jointly organized by the Institute for Medical Informatics and Biometry, Medical Faculty Carl Gustav Carus, Dresden University of Technology and the Institute for Medical Informatics, Statistics and Epidemiology, Medical Faculty, University of Leipzig, brought together 32 scientists from 8 countries, with scientific backgrounds in medicine, cell biology, virology, physics, computer sciences, bioinformatics and mathematics. The workshop focused on the following questions: (1) How heterogeneous are stem cells and their progeny? and (2) What are the characteristic differences in the clonal dynamics between physiological and pathophysiological situations? In discussing these questions, particular emphasis was placed on (a) the methods for quantifying clones and their dynamics in experimental and clinical settings and (b) general concepts and models for their description. In this workshop summary we start with an introduction to the current state of clonality research and a proposal for clearly defined terminology. Major topics of discussion include clonal heterogeneity in unperturbed tissues, clonal dynamics due to physiological and pathophysiological pressures and conceptual and technical issues of clone quantification. We conclude that an interactive cross-disciplinary approach to research in this field will continue to promote a conceptual understanding of tissue organization.

The extraordinary fidelity, sensory and regulatory capacity of natural intracellular machinery is generally confined to their endogenous environment. Nevertheless, synthetic bio-molecular components have been engineered to interface with the cellular transcription, splicing and translation machinery in vivo by embedding functional features such as promoters, introns and ribosome binding sites, respectively, into their design. Tapping and directing the power of intracellular molecular processing towards synthetic bio-molecular inputs is potentially a powerful approach, albeit limited by our ability to streamline the interface of synthetic components with the intracellular machinery in vivo. Here we show how a library of synthetic DNA devices, each bearing an input DNA sequence and a logical selection module, can be designed to direct its own probing and processing by interfacing with the bacterial DNA mismatch repair (MMR) system in vivo and selecting for the most abundant variant, regardless of its function. The device provides proof of concept for programmable, function-independent DNA selection in vivo and provides a unique example of a logical-functional interface of an engineered synthetic component with a complex endogenous cellular system. Further research into the design, construction and operation of synthetic devices in vivo may lead to other functional devices that interface with other complex cellular processes for both research and applied purposes.

Human cancers display substantial intratumoral genetic heterogeneity, which facilitates tumor survival under changing microenvironmental conditions. Tumor substructure and its effect on disease progression and relapse are incompletely understood. In the present study, a high-throughput method that uses neutral somatic mutations accumulated in individual cells to reconstruct cell lineage trees was applied to hundreds of cells of human acute leukemia harvested from multiple patients at diagnosis and at relapse. The reconstructed cell lineage trees of patients with acute myeloid leukemia showed that leukemia cells at relapse were shallow (divide rarely) compared with cells at diagnosis and were closely related to their stem cell subpopulation, implying that in these instances relapse might have originated from rarely dividing stem cells. In contrast, among patients with acute lymphoid leukemia, no differences in cell depth were observed between diagnosis and relapse. In one case of chronic myeloid leukemia, at blast crisis, most of the cells at relapse were mismatch-repair deficient. In almost all leukemia cases, > 1 lineage was observed at relapse, indicating that diverse mechanisms can promote relapse in the same patient. In conclusion, diverse relapse mechanisms can be observed by systematic reconstruction of cell lineage trees of patients with leukemia.

We describe a working mechanical device that embodies the theoretical computing machine of Alan Turing, and as such is a universal programmable computer. The device operates on three-dimensional building blocks by applying mechanical analogues of polymer elongation, cleavage and ligation, movement along a polymer, and control by molecular recognition unleashing allosteric conformational changes. Logically, the device is not more complicated than biomolecular machines of the living cell, and all its operations are part of the standard repertoire of these machines; hence, a biomolecular embodiment of the device is not infeasible. If implemented, such a biomolecular device may operate in vivo, interacting with its biochemical environment in a program-controlled manner. In particular, it may 'compute' synthetic biopolymers and release them into its environment in response to input from the environment, a capability that may have broad pharmaceutical and biological applications.

Making faultless complex objects from potentially faulty building blocks is a fundamental challenge in computer engineering, nanotechnology, and synthetic biology. We developed an error-correcting recursive construction procedure that attempts to address this challenge. Making DNA molecules from synthetic oligonucleotides using the procedure described here surpasses existing methods for de novo DNA synthesis in speed, precision, and amenability to automation. It provides for the first time a unified DNA construction platform for combining synthetic and natural DNA fragments, for constructing designer DNA libraries, and for making the faultless long synthetic DNA building blocks needed for de novo genome construction.

Stem cell dynamics in vivo are often being studied by lineage tracing methods. Our laboratory has previously developed a retrospective method for reconstructing cell lineage trees from somatic mutations accumulated in microsatellites. This method was applied here to explore different aspects of stem cell dynamics in the mouse colon without the use of stem cell markers. We first demonstrated the reliability of our method for the study of stem cells by confirming previously established facts, and then we addressed open questions. Our findings confirmed that colon crypts are monoclonal and that, throughout adulthood, the process of monoclonal conversion plays a major role in the maintenance of crypts. The absence of immortal strand mechanism in crypts stem cells was validated by the age-dependent accumulation of microsatellite mutations. In addition, we confirmed the positive correlation between physical and lineage proximity of crypts, by showing that the colon is separated into small domains that share a common ancestor. We gained new data demonstrating that colon epithelium is clustered separately from hematopoietic and other cell types, indicating that the colon is constituted of few progenitors and ruling out significant renewal of colonic epithelium from hematopoietic cells during adulthood. Overall, our study demonstrates the reliability of cell lineage reconstruction for the study of stem cell dynamics, and it further addresses open questions in colon stem cells. In addition, this method can be applied to study stem cell dynamics in other systems.

Bacterial cloning was first introduced over a century ago and has since become one of the most useful procedures in biological research, perhaps paralleled in its ubiquity only by PCR and DNA sequencing. However, unlike PCR and sequencing, cloning has generally remained a manual, labor-intensive, low-throughput procedure. Here we address this issue by developing an automated, computer-aided bacterial cloning method using liquid medium that is based on the principles of (i) limiting dilution of bacteria, (ii) inference of colony forming units (CFUs) based on optical density (OD) readings, and (iii) verification of monoclonality using a mixture of differently colored fluorescently labeled bacteria for transformation. We demonstrate the high-throughput utility of this method by employing it as a cloning platform for a DNA synthesis process.

A system based on RNA can perform simple logical computations within a living cell, marking a step toward programming cell behavior.

Synaptic wiring of neurons in Caenorhabditis elegans is largely invariable between animals. It has been suggested that this feature stems from genetically encoded molecular markers that guide the neurons in the final stage of synaptic formation. Identifying these markers and unraveling the logic by which they direct synapse formation is a key challenge. Here, we address this task by constructing a probabilistic model that attempts to explain the neuronal connectivity diagram of C. elegans as a function of the expression patterns of its neurons. By only considering neuron pairs that are known to be connected by chemical or electrical synapses, we focus on the final stage of synapse formation, in which neurons identify their designated partners. Our results show that for many neurons the neuronal expression map of C. elegans can be used to accurately predict the subset of adjacent neurons that will be chosen as its postsynaptic partners. Notably, these predictions can be achieved using the expression patterns of only a small number of specific genes that interact in a combinatorial fashion.

Even though electronic computers are the only computer species we are accustomed to, the mathematical notion of a programmable computer has nothing to do with electronics. In fact, Alan Turing's notional computer [L.M. Turing, On computable numbers, with an application to the entcheidungsproblem, Proc. Lond. Math. Soc. 42 (1936) 230-265], which marked in 1936 the birth of modem computer science and still stands at its heart, has greater similarity to natural biomolecular machines such as the ribosome and polymerases than to electronic computers. This similarity led to the investigation of DNA-based computers [C.H. Bennett, The thermodynamics of computation - Review, Int. J. Theoret. Phys. 21 (1982) 905-940; A.M. Adleman, Molecular computation of solutions to combinatorial problems, Science 266 (1994) 1021-1024]. Although parallelism, sequence specific hybridization and storage capacity, inherent to DNA and RNA molecules, can be exploited in molecular computers to solve complex mathematical problems [Q. Ouyang, et a]., DNA solution of the maximal clique problem, Science 278 (1997) 446-449; R.J. Lipton, DNA solution of hard computational problems, Science 268 (1995) 542-545; R.S. Braich, et al., Solution of a 20-variable 3-SAT problem on a DNA computer, Science 296 (2002) 499-502; Liu Q., et al., DNA computing on surfaces, Nature 403 (2000) 175-179; D. Faulhammer, et al., Molecular computation: RNA solutions to chess problems, Proc. Natl. Acad. Sci. USA 97 (2000) 1385-1389; C. Mao, et al., Logical computation using algorithmic self-assembly of DNA triple-crossover molecules, Nature 407 (2000) 493-496; A.J. Ruben, et al., The past, present and future of molecular computing, Nat. Rev. Mol. Cell. Biol. 1 (2000) 69-72], we believe that the more significant potential of molecular computers lies in their ability to interact directly with a biochemical environment such as the bloodstream and living cells. From this perspective, even simple molecular computations may have important consequences when performed in a proper context. We envision that molecular computers that operate in a biological environment can be the basis of \u201csmart drugs\u201d, which are potent drugs that activate only if certain environmental conditions hold. These conditions could include abnormalities in the molecular composition of the biological environment that are indicative of a particular disease. Here we review the research direction that set this vision and attempts to realize it.

The depth of a cell of a multicellular organism is the number of cell divisions it underwent since the zygote, and knowing this basic cell property would help address fundamental problems in several areas of biology. At present, the depths of the vast majority of human and mouse cell types are unknown. Here, we show a method for estimating the depth of a cell by analyzing somatic mutations in its microsatellites, and provide to our knowledge for the first time reliable depth estimates for several cells types in mice. According to our estimates, the average depth of oocytes is 29, consistent with previous estimates. The average depth of B cells ranges from 34 to 79, linearly related to the mouse age, suggesting a rate of one cell division per day. In contrast, various types of adult stem cells underwent on average fewer cell divisions, supporting the notion that adult stem cells are relatively quiescent. Our method for depth estimation opens a window for revealing tissue turnover rates in animals, including humans, which has important implications for our knowledge of the body under physiological and pathological conditions.

Stochastic computing has a broad range of applications, yet electronic computers realize its basic step, stochastic choice between alternative computation paths, in a cumbersome way. Biomolecular computers use a different computational paradigm and hence afford novel designs. We constructed a stochastic molecular automaton in which stochastic choice is realized by means of competition between alternative biochemical pathways, and choice probabilities are programmed by the relative molar concentrations of the software molecules coding for the alternatives. Programmable and autonomous stochastic molecular automata have been shown to perform direct analysis of disease-related molecular indicators in vitro and may have the potential to provide in situ medical diagnosis and cure.

Although electronic computers are the only "computer species" we are accustomed to, the mathematical notion of a programmable computer has nothing to do with wires and logic gates. In fact, Alan Turing's notional computer, which marked in 1936 the birth of modern computer science and still stands at its heart, has greater similarity to natural biomolecular machines such as the ribosome and polymerases than to electronic computers. Recently, a new "computer species" made of biological molecules has emerged. These simple molecular computers inspired by the Turing machine, of which a trillion can fit into a microliter, do not compete with electronic computers in solving complex computational problems; their potential lies elsewhere. Their molecular scale and their ability to interact directly with the biochemical environment in which they operate suggest that in the future they may be the basis of a new kind of "smart drugs": molecular devices equipped with the medical knowledge to perform disease diagnosis and therapy inside the living body. They would detect and diagnose molecular disease symptoms and, when necessary, administer the requisite drug molecules to the cell, tissue or organ in which they operate. In the talk we review this new research direction and report on preliminary steps carried out in our lab towards realizing its vision.

Biopolymers such as nucleic acids and proteins encode biological data and may be viewed as strings of chemical letters. While electronic computers manipulate strings of 0s and 1s encoded in electric signals, biologically encoded data might, in principle, be manipulated by biochemical means. During the last decade, several approaches to compute with biomolecules were developed, and the field has become known as biomolecular or DNA computing. The approaches varied widely with respect to the model of computation they employed, the problems they attempted to solve, and the degree of human intervention. One approach focused on the application of the Turing machine model and, more generally, string-processing automata to biomolecular information processing. Its goal is to construct computers made of biomolecules that are capable of autonomous conversion of an input dataencoding molecule to an output molecule according to a set of rules defined by a molecular program. Here we survey the field of biomolecular computing machines and discuss possible future directions.

We describe a novel application of a stochastic name-passing calculus for the study of biomolecular systems. We specify the structure and dynamics of biochemical networks in a variant. of the stochastic pi -calculus, yielding a model which is mathematically well-defined and biologically faithful. We adapt the operational semantics of the calculus to account for both the time and probability of biochemical reactions, and present a computer implementation of the calculus for biochemical simulations.

Abstract Data Types (ADTs) has been introduced recently to Israeli high-school students as tools for problem solving and knowledge representation in Prolog environment. This paper reviews a research that was conducted in order to assess the influence of students' use of ADTs on the development process of knowledge-based Prolog programs.

A directed logic variable is a two-port communication channel that can transmit at most one message, which may contain embedded ports. The ability to send both input and output ports in messages allows directed logic variables to implement other communication primitives such as streams and remote procedure calls; to realize dynamic process migration; and to support sophisticated mail and window system protocols. Hence directed logic variables can be useful as an implementation layer for concurrent languages and as an extension to sequential procedural languages. We provide an abstract, programming language independent, operational semantics for communication with directed logic variables and develop effective distributed implementations of it. Our implementation algorithms ensure that, in spite of arbitrary port migration, if a message is sent on a channel's output port and the channel's input port eventually stops migrating then the message will eventually reach it. In addition, our algorithms are efficient and robust: They dynamically shorten the logical routing paths caused by port migration, collect unused routing table entries, and are resilient to a certain class of network faults. We prove that the algorithms implement the operational semantics using the refinement mapping proof technique and temporal logic inference rules for weak and strong fairness, demonstrating the effectiveness of combining these two methods.

In a previous paper [1] we developed an algebraic framework for language comparison based on language embeddings, which are mappings that preserve certain aspects of both the syntactic and the semantic structure of the language. We provided separation results by demonstrating the nonexistence of various kinds of embeddings among languages. In this talk we survey the framework and complement the separation results with positive results, i.e., demonstrate embeddings among various well-known concurrent languages. Together the positive and negative results induce a preordering on the family of concurrent programming languages that quite often coincides with previous intuitions on the "expressive power" of these languages.

The language FCP(:,?) is the outcome of attempts to integrate the best of several flat concurrent logic programming languages, including Flat GHC, FCP (↓, |) and Flat Concurrent Prolog, in a single consistent framework. FCP(:) is a subset of FCP(:, ?), which is a variant of FPP(↓, |) and employs concepts of the concurrent constraint framework of cc(↓, |). FCP(:, ?) is a language which is strong enough to accommodate all useful concurrent logic programming techniques, including those which rely on atomic test unification and read-only variables, yet incorporates the weaker languages mentioned as subsets. This allows the programmer to remain within a simple subset of the language such as Flat GHC when the full power of atomic unification or read-only variables is not needed.

This paper describes a uniprocessor implementation of Flat Concurrent Prolog, based on an abstract machine and a compiler for it. The machine instruction set includes the functionality necessary to implement efficiently the parallel semantics of the language. In addition, the design includes a novel approach to the integration of a module system into a language. Both the compiler and the emulator for the abstract machine have been implemented and form the basis of Logix, a practical programming environment for Flat Concurrent Prolog. Its performance suggests that a process-oriented language need not be less efficient then a procedure-oriented language, even on a uniprocessor. In particular, it shows that a process queue and process spawning can be implemented as effectively as an activation stack and procedure calling, and thus debunks the \u201cexpensive-process-spawn myth\u201d.

This paper reports on the design and the implementation of a distributed transactions-system for a Universal File Server. The system maintains consistency in a general purpose file-system by means of concurrency control and crash recovery. Both the distributivity of a transaction and the intra-transaction concurrency, are depicted by a single model which describes the transaction as a partially ordered set of operations. The main concurrency control algorithm described in this paper is a novel distributed locking management algorithm based on the two-phase-locking (2pl) protocol. The system is implemented in Flat Concurrent Prolog (FCP), a concurrent logic programming language. FCP lends itself to the development of new distributed algorithms which utilize the fine-grained concurrency and the powerful communication and synchronization mechanisms supplied by the language. The features of concurrent logic languages, which are useful for implementing file and database systems are demonstrated in this paper.

Flat Concurrent Prolog is a simple concurrent programming language which has been used for a variety of non-trivial applications. A compiler based parallel implementation has been completed which operates on an Intel Hypercube. This paper presents a brief summary of performance data from a recent study of the implementation. Three categories of program were studied: parallel applications, uniprocessor benchmarks and communication stereotypes. The latter programs are abstractions of common parallel programming techniques and serve to quantify the cost of communication in the language.

In this paper we apply the result that when using abstract interpretation for program analysis, we do not necessarily need to compute an abstract least fixed point, or indeed any fixed point of the abstract semantic function. Any meaning which is a safe approximation of the least fixed point can give useful information. In particular, the sequence of meanings obtained by applying the semantic function iteratively to the top element of the domain yields safe approximations, since this sequence approaches the greatest fixed point from above. The framework of the technique is first defined, and its advantages and disadvantages discussed. Two applications of the technique for the parallel logic programming language Flat Concurrent Prolog (FCP) are presented. The mode analysis application is based on a collecting semantics for SLD derivations, and has been incorporated in a compiler for FCP. The suspension analysis application is the first attempt, to our knowledge, to apply abstract interpretation to analyse reactive aspects of a parallel programming language.

We propose a framework for discussing fully abstract compositional semantics, which exposes the interrelations between the choices of observables, compositions, and meanings. Every choice of observables and compositions determines a unique fully abstract equivalence. A semantics is fully abstract if it induces this equivalence. We study the semantics of logic programs within this framework. We find the classical Herbrand-base semantics of logic programs inadequate, since it identifies programs that should be distinguished and vice versa. We therefore propose alternative semantics, and consider the cases of no compositions, composition by program union, and composition of logic modules (programs with designated exported and imported predicates). Although equivalent programs can be in different vocabularies, we prove that our fully abstract semantics are always in a subvocabulary of that of the program. This subvocabulary, called the essential vocabulary, is common to all equivalent programs. The essential vocabulary is also the smallest subvocabulary in which an equivalent program can be written.

This paper presents an approach to specialising logic programs which is based on abstract interpretation. Program specialisation involves two stages, the construction of an abstract computation tree and a program construction stage. For the tree construction stage, abstract OLDT resolution is defined and used to construct a complete and finite tree corresponding to a given logic program and a goal. In the program construction stage, a specialised program is extracted from this tree.We focus on two logic programming languages: sequential Prolog and Flat Concurrent Prolog. Although the procedural reading of concurrent logic programs is very different from that of sequential programs, the techniques presented provide a uniform approach to the specialisation of both languages. We present the results for Prolog rigorously, and extend them less formally to Flat Concurrent Prolog.There are two main advantages of basing program specialisation on abstract interpretation. Firstly, termination can be ensured by using abstract interpretations over finite domains, while performing a complete flow analysis of the program. Secondly, correctness of the specialised program is closely related to well-defined consistency conditions on the concrete and abstract interpretations.

This paper presents two notes which discuss basic theoretical issues concerning the systolic programming methodology and demonstrates simple techniques which can by used to structure communication. The first note shows how the complexity of two simple algorithms is adversely affected by the cost of data movement in a parallel system. Programming techniques which introduce pipelining are used to overcome the problem and improve the complexity. The second note shows an upper bound on the speedup which can be obtained using the methodology on a mesh connected architecture. This bound is stated in terms of the sequential lower bound for the algorithm concerned.

The authors propose an execution model and a special-purpose processor architecture for the execution of Flat Concurrent Prolog (FCP). The execution model defines concurrency inherent to the execution of FCP on a single processor. It is derived by partitioning the FCP Sequential Abstract Machine into concurrently executing units. To support this execution model, the FCP Processor architecture consists of the following concurrent functional processors: Reduction Processor, Tag Processor, Goal Management Processor, Instruction Porcessor and Data-Trail Processor. The Goal Management Processor performs the efficient management of concurrent FCP goals reduced by the Reduction Processor. The Data-Trail Processor implements a novel cache management algorithm which supports shallow backtracking. The FCP Processor architectural model is specified in FCP itself and is part of a working simulator. The attainable performance of the FCP Processor architecture is currently under investigation.

This study is based on the belief that in the near future, computer programming using high level programming language techniques, should become an integral part of all school subjects, as reading, writing and arithmetics are today.A program designed for teaching Prolog (PROgramming in LOGic) as a first computer language for students and teachers at junior high and high school level is introduced. A unique approach of introducing basic concepts of logic programming within its proportional level is described.Applications of Prolog in different school subjects, and its potential to enhance logical and deductive reasoning and problem solving abilities are discussed.

This paper reports on the experience of implementing Shiloach and Vishkin's parallel Maxflow algorithm [7] in Concurrent PROLOG. The major difficulties in this endeavor were understanding the algorithm, which is intricate, and adapting it to the computational model of Concurrent PROLOG. In spite of the difficulties, we were able to produce a Concurrent PROLOG program that implements the algorithm and achieves the expected complexity bounds. The lack of destructive assignment in the logic program's computation model prevents PROLOG from being an efficient implementation language for many sequential algorithms. Our main conclusion is that, in concurrent algorithms, message passing is a powerful substitute for destructive assignment. It is therefore possible to write efficient Concurrent PROLOG implementations of concurrent algorithms.

Concurrent Prolog is a logic programming language designed for concurrent programming and parallel execution. It is a process oriented language, which embodies dataflow synchronization and guarded-command indeterminacy as its basic control mechanisms.The paper outlines the basic concepts and definition of the language, and surveys the major programming techniques that emerged out of three years of its use. The history of the language development, implementation, and applications to date is reviewed. Details of the performance of its compiler and the functionality of Logix, its programming environment and operating system, are provided.

Most Prolog textbooks are based on gradual presentation of Prolog's concepts, as well as some concepts from logic. We think that this order of presentation used in most books is inadequate for readers with little prior experience with logic, mathematics or programming. In this paper we introduce a new approach for teaching Prolog to these \u201cnaive\u201d users. Within our framework, the order of concept introduction is based upon the order used in teaching logic: from propositions to predicates. We believe that this approach will ease the difficulties encountered by newcomers to Prolog, and will provide a good basis for better understanding of logic, programming, data-base theory, and perhaps also other relevant disciplines.The choice of Prolog as a first programming language is also discussed, and we argue that it is a better choice than conventional languages in the same sense that those languages are considered better than machine languages. This claim however should be empirically verified.

The problem of allowing a dynamically changing set of processes fair access to a shared resource is considered, in the context of communication-stream based systems. It is argued that fair binary merge operators alone cannot solve this problem satisfactorily. Two solutions are proposed. One employs binary merge operators with a programmable bias; the other binary and ternary fair merge operators capable of self-balancing, using the concept of 23 trees. A Concurrent Prolog implementation of these operators is described. The implementation of the self-balancing merge operators illustrates the expressive power of incomplete messages, a programming technique that supports messages that contain communication channels as arguments. In the course of implementing the self-balancing merge operator, it was necessary to develop a distributed variant of the 23 tree deletion algorithm.

Concurrent Prolog [28] combines the logic programming computation model with guarded-command indeterminacy and dataflow synchronization. It will form the basis of the Kernel Language [21] of the Parallel Inference Machine [36], planned by Japan's Fifth Generation Computers Project. This paper explores the feasibility of programming such a machine solely in Concurrent Prolog (in the absence of a lower-level programming language), by implementing in it a representative collection of systems programming problems.

As part of Japan's effort to become a leader in the computer industry, the Institute for New Generation Computer Technology has launched a revolutionary ten-year plan for the development of large computer systems which will be applicable to knowledge information processing systems. These Fifth Generation computers will be built around the concepts of logic programming. In order to refute the accusation that Japan exploits knowledge from abroad without contributing any of its own, this project will stimulate original research and will make its results available to the international research community.

It is shown that the basic operations of object-oriented programming languages creating an, object, sending and receiving messages, modifying an objects state, and forming class-superclass hierarchies can be implemented naturally in Concurrent Prolog. In addition, a new object-oriented programming paradigm, called incomplete messages, is presented. This paradigm subsumes stream communication, and greatly simplifies the complexity of programs defining communication networks and protocols for managing shared resources. Several interesting programs are presented, including a multiple-window manager. All programs have been developed and tested using the Concurrent Prolog interpreter described in.

A framework for inductive inference in logic is presented: a Model Inference Problem is defined, and it is shown that problems of machine learning and program synthesis from examples can be formulated naturally as model inference problems. A general, incremental inductive inference algorithm for solving model inference problems is developed. This algorithm is based on Popper's methodology of conjectures and refutations [II] . The algorithm can be shown to identify in the limit [3] any model in a family of complexity classes of models, is most powerful of its kind, and is flexible enough to have been successfully implemented for several concrete domains. The Model Inference System is a Prolog implementation of this algorithm, specialized to infer theories in Horn form. It can infer axiomatizations of concrete models from a small number of facts in a practical amount of time.