International Journal of Foundations of Computer Science

In this paper, we consider procedures for logic and arithmetic operations with DNA molecules. We first show a DNA representation of n binary numbers of m bits, and propose a procedure to assign the same values for the representation. The representation enables addressing feature, and the procedure is applicable to n binary numbers of m bits in O(1) steps in parallel. Next, we propose a procedure for logic operations. The procedure enables any boolean operation whose input and output are defined by a truth table, and executes different kinds of boolean operations simultaneously for any pair of n binary numbers of m bits in O(1) lab steps using O(mn) DNA strands. Finally, we propose a procedure for additions of pairs of two binary numbers. The procedure executes O(n) additions of two m-bit binary numbers in O(1) steps using O(mn) DNA strands.

This paper studies the simulation problem of meshes with separable buses by meshes with multiple partitioned buses . The and the are the mesh connected computers enhanced by the addition of broadcasting buses along every row and column. The broadcasting buses of the , called separable buses, can be dynamically sectioned into smaller bus segments by program control, while those of the , called partitioned buses, are statically partitioned in advance. In the model, each row/column has only one separable bus, while in the model, each row/column has L partitioned buses (L≥2). We consider the simulation and the scaling-simulation of the by the , and show that the of size n×n can be simulated in O(n^1/(2L)) steps by the of size n×n, and that the of size n×n can be simulated in steps by the of size m×m(m<n). The latter result implies that the of size n×n can be simulated time-optimally by the of size m×m when n≥m^1+∊ holds where .

In-network collaborative computation is essential for implementation of a large number of sensor applications. We approach the problem of computation in sensor networks from a parallel and distributed system's perspective. We define COSMOS, the Cluster-based, heterOgeneouSMOdel for Sensor networks. The model abstracts the key features of the class of cluster-based sensor applications. It assumes a hierarchical network architecture comprising of a large number of low cost sensors with limited computation capability, and fewer number of powerful clusterheads, uniformly distributed in a two dimensional terrain. The sensors are organized into single hop clusters, each managed by a distinct clusterhead. The clusterheads are organized in a mesh-like topology. All sensors in a cluster are time synchronized, whereas the clusterheads communicate asynchronously. The sensors are assumed to have multiple power states and a wakeup mechanism to facilitate power management. To illustrate algorithm design using our model, we discuss implementation of algorithms for sorting and summing in sensor networks.

In this paper we present the first distributed algorithm on general graphs for the Minimum Degree Spanning Tree problem. The problem is NP-hard in sequential. Our algorithm give a Spanning Tree of a degree at most 1 from the optimal.

The resulting distributed algorithm is asynchronous, it works for named asynchronous arbitrary networks and achieves O(|V|) time complexity and O(|V||E|) message complexity.

We study hierarchical configuration of distributed systems for achieving optimized system performance. A distributed system consists of a collection of local processes which are distributed over a network of processors, and work in a cooperative manner to fulfill various tasks. A hierarchical approach is to group and organize the distributed processes into a logical hierarchy of multiple levels, so as to coordinate the local computation/control activities to improve the overall system performance. It has been proposed as an effective way to solve various problems in distributed computing, such as distributed monitoring, resource scheduling, and network routing. The optimization problem considered in this paper is concerned with finding an optimal hierarchical partition of the processors, so that the total traffic flow over the network is minimized. The problem in its general form has been known to be NP-hard. Therefore, we just focus on distributed computing jobs which require collecting and processing information from all processors. By limiting levels of the hierarchy to two, we will establish the analytically optimal hierarchical configurations for two popular interconnection networks: mesh and hypercube. Based on analytical results, partitioning algorithms are proposed to achieve minimal communication cost (network traffic flow). We will also present and discuss heuristic algorithms for multiple-level hierarchical partitions.

Numerical software for sequential or parallel machines with memory hierarchies can benefit from locality optimizations which are usually achieved by program restructuring or program transformations. In this paper we introduce and discuss program-based locality measures which can be used to guide the restructuring and transformation process at program level. As example we consider a popular solution method to solve ordinary differential equations provided in many scientific libraries.

Content networks are overlay networks, enabling access to distributed contents on centralized servers or individual computers. Since flooding-based routing scheme features poor scalability, we present a modification, which reduces the total network traffic while retaining the original efficiency. In choosy routing, as we call it, each node, while passing an answer, remembers which neighbor it came from. Subsequently repeated queries about the same content are forwarded only to that neighbor. This way, the network learns effective routes. The simulations on several topology types have shown the expected behavior, with up to three-fold reduction in the overall query traffic.