Asynchronous Boolean totalistic cellular automata have recently attracted attention as promising models for implementation by reaction-diffusion systems. It is unknown, however, to what extent they are able to conduct computation. In this paper, we introduce the so-called non-camouflage property, which means that a cell's update is insensitive to neighboring states that equal its own state. This property subsumes the Boolean totalistic property, which signifies the existence of states in a cell's neighborhood, but is not concerned with how many cells are in those states. We argue that the non-camouflage property is extremely useful for the implementation of reaction-diffusion systems, and we construct an asynchronous cellular automaton with this property that is Turing-complete by directly simulating Turing machines. We also construct another asynchronous cellular automaton, but this model incorporates the so-called freezing property [1], which restricts the direction of transitions of each cell to one-way. We show that this model is Turing-complete, since it can simulate the temporal evolution of elementary cellular automata. These results indicate the feasibility of computation by reaction-diffusion systems.

Summary In this paper, we extend work on model‐based testing for Apache ZooKeeper, to handle watchers (triggers) and improve scalability. In a distributed asynchronous shared storage like ZooKeeper, watchers deliver notifications on state changes. They are difficult to test because watcher notifications involve an initial action that sets the watcher, followed by another action that changes the previously seen state. We show how to generate test cases for concurrent client sessions executing against ZooKeeper with the tool Modbat. The tests are verified against an oracle that takes into account all possible timings of network communication. The oracle has to verify that there exists a chain of events that triggers both the initial callback and the subsequent watcher notification. We show in detail how the oracle computes whether watch triggers are correct and how the model was adapted and improved to handle these features. Together with a new search improvement that increases both speed and accuracy, we are able to verify large test setups and confirm several defects with our model.

IoT devices operate in environments where networks may be unstable. They rely on transport protocols to deliver data with given quality-of-service settings. To test an implementation of the popular MQTT protocol thoroughly, we extend the model-based test framework “Modbat” to simulate unstable networks by taking into account delays and transmission failures. Our proxy-based technology requires no changes to the IoT software, while the model allows the user to define stateless or stateful types or fault patterns. We evaluate our methods on a client-server library for MQTT, a transport protocol designed for IoT.

This paper deals with the programmability of a swarm of bio-micro-robots in order to display self-assembling behaviors into specific shapes. We consider robots that are DNA-functionalized micro-beads capable of sensing and expressing signals as well as self-assembling. We describe an in vitro experimentation with a million of micro-beads conditionally aggregating into clusters. Using a realistic simulation, we then address the question of how to automatically design the reaction networks that define the micro-robots' behavior, to self-assemble into a specific shape at a specific location. We use bioNEAT, an instantiation of the famous NEAT algorithm capable of handling chemical reaction networks, and CMA-ES to optimize the behavior of each micro-bead. As in swarm robotics, each micro-bead shares the same behavioral rules and the general outcome depends on interactions between neighbors and with the environment. Results obtained on four different target functions show that solutions optimized with evolutionary algorithms display efficient self-assembling behaviors, improving over pure hand-designed networks provided by an expert after a week-long trials and errors search. In addition, we show that evolved solutions are able to self-repair after damage, which is a critical property for smart materials.

Apache ZooKeeper is a distributed data storage that is highly concurrent and asynchronous due to network communication, testing such a system is very challenging. Our solution using the tool "Modbat" generates test cases for concurrent client sessions, and processes results from synchronous and asynchronous callbacks. We use an embedded model checker to compute the test oracle for non-deterministic outcomes, the oracle model evolves dynamically with each new test step. Our work has detected multiple previously unknown defects in ZooKeeper. Finally, a thorough coverage evaluation of the core classes show how code and branch coverage strongly relate to feature coverage in the model, and hence modeling effort.

Various artificial molecular devices, including some made of DNA or RNA , have been developed to date. The next step in this area of research is to develop an integrated system from such molecular devices. A molecular robot consists of sensors, computers, and actuators , all made of molecular devices, and reacts autonomously to its environment by observing the environment, making decisions with its computers, and performing actions upon the environment. Molecular computers should thus be the intelligent controllers of such molecular robots. Such controllers can naturally be regarded as hybrid systems because the environment, the robot, and the controller are all state transition systems having discrete and continuous states and transitions. For modeling and designing hybrid systems, formal frameworks, such as hybrid automata , are commonly used. In this perspective paper, we examine how molecular controllers can be modeled as hybrid automata and how they can be realized in a molecular robot. We first summarize the requirements for such molecular controllers and examine existing frameworks of DNA computing with respect to these requirements. We then show the possibility of combining existing frameworks of DNA computing to implement a sample hybrid controller for a molecular robot.

Distributed systems are complex, being usually composed of several subsystems running in parallel. Concurrent execution and inter-process communication in these systems are prone to errors that are difficult to detect by traditional testing, which does not cover every possible program execution. Unlike testing, model checking can detect such faults in a concurrent system by exploring every possible state of the system. However, most model-checking techniques require that a system be described in a modeling language. Although this simplifies verification, faults may be introduced in the implementation. Recently, some model checkers verify program code at runtime but tend to be limited to stand-alone programs. This paper proposes cache-based model checking, which relaxes this limitation to some extent by verifying one process at a time and running other processes in another execution environment. This approach has been implemented as an extension of Java PathFinder, a Java model checker. It is a scalable and promising technique to handle distributed systems. To support a larger class of distributed systems, a checkpointing tool is also integrated into the verification system. Experimental results on various distributed systems show the capability and scalability of cache-based model checking.

Many modern software systems are implemented as client/server architectures, where a server handles multiple clients concurrently. Testing does not cover the outcomes of all possible thread and communication schedules reliably. Software model checking, on the other hand, covers all possible outcomes but is often limited to subsets of commonly used protocols and libraries. Earlier work in cache-based software model checking handles implementations using socket-based TCP/IP networking, with one thread per client connection using blocking input/output. Recently, servers using non-blocking, selector-based input/output have become prevalent. This paper describes our work extending the Java PathFinder extension net-iocache to such software, and the application of our tool to modern server software.

Verification of distributed software systems by model checking is not a straightforward task due to inter-process communication. Many software model checkers only explore the state space of a single multi-threaded process. Recent work proposes a technique that applies a cache to capture communication between the main process and its peers, and allows the model checker to complete state-space exploration. Although previous work handles non-deterministic output in the main process, any peer program is required to produce deterministic output. This paper introduces a process checkpointing tool. The combination of caching and process checkpointing makes it possible to handle non-determinism on both sides of communication. Peer states are saved as checkpoints and restored when the model checker backtracks and produces a request not available in the cache. We also introduce the concept of strategies to control the creation of checkpoints and the overhead caused by the checkpointing tool.

Many applications are concurrent and communicate over a network. The non-determinism in the thread and communication schedules makes it desirable to model check such systems. However, a simple state space exploration scheme is not applicable, as backtracking results in repeated communication operations. A cache-based approach solves this problem by hiding redundant communication operations from the environment. In this work, we propose a change from a linear-time to a branching-time cache, allowing us to relax restrictions in previous work regarding communication traces that differ between schedules. We successfully applied the new algorithm to real-life programs where a previous solution is not applicable.

We constructed a DNA machine, the state branches of which depend on input DNA oligomers. The machine is a single DNA oligomer consisting of two hairpin structures connected by a single-stranded section. The input DNA oligomers can invade a hairpin's stem via branch migration, opening the hairpin. The branching state is represented by which of the hairpins is opened. This paper describes the design of the DNA machine, an analysis of secondary structure transitions, and experimental results.

An equilibrium model was reported for predicting the hybridization error of a tag-antitag (TAT) system in response to a dilute input [J. Rose, et al., in DNA Computing, (Springer, 2001), 138]. One notable aspect of the model was its disagreement with the error behavior expected via a consideration of the melting temperatures (T'/sub m/s) of planned and error TAT duplexes, in isolation (the stringency picture). In this work, an equilibrium approach is applied to model TAT system error in response to a general, single-tag input. This model is implemented, using two-state and statistical zipper models of duplex formation, via Mathematica/spl trade/ and NucleicPark, respectively. Under appropriate nondilute conditions (high unplanned sequence-similarity; equimolar/excess input), an error minimum is predicted between the T'/sub m/s of planned and unplanned TAT duplexes, as expected via stringency considerations, providing a reconciliation between the two models of hybridization fidelity. On the other hand, predictions for a dilute input agree closely with the model in Rose, et al., supporting the view that a T/sub m/-based model is not fully adequate. A TAT set is then reported, evolved to support experimental validation, which exhibits excess input, signal-to-noise ratios that uniformly span the dynamic range of current fluorescence measurement equipment.

Whiplash PCR, a reaction in which hairpin DNA structures are extended by polymerase, is a useful method for DNA computing. For example, state transitions can be implemented by this method. However, the feasibility of using whiplash PCR in a specific DNA algorithm should be carefully considered. We have implemented a general-purpose simulator to aid those who design protocols and algorithms for DNA computing, that includes whiplash PCR. The simulator, including its data structures and a simulation algorithm, is described, and then the results of simulating state transitions with whiplash PCR are discussed.

Abstract. We introduce an Emacs interface for writing HOL proof scripts in SML based on the Computing-as-Editing paradigm. Tactics in a proof script are considered as constraints, and the process of interactive theorem proving becomes that of solving constraints. In addition, constraint solving is subsumed by the process of editing a proof script. Tactics are executed while the script is being edited. The user does not have to pay attention to the status of the HOL prover. In our interface, the user can also enjoy proof-by-pointing. The result of proof-by-pointing is inserted as a tactic into a proof script. We expect that our interface will be widely used as an extension of the familiar HOL mode on Emacs.

The dynamic-sized tabulation method can be used to eliminate redundant calls for certain classes of recursive programs. An innovative aspect of the method is the use of lambda abstractions that may subsequently be converted to bounded vectors, in order to share redundant calls via vector lookup.To facilitate this conversion to vector form, we propose a new inference method to conservatively determine the bounds for arithmetic parameters of recursive functions. Suitable techniques for inferring the safe bounds of these parameters are introduced, together with supporting transformations. The resulting method can obtain efficient vector-based programs without the need for run-time bounds checking.