Based on genetic algorithm (GA) in this paper we present a simple method to extract distributed circuit parameters of a multiple coupled nonuniform microstrip transmission lines from it's measured or computed S-parameters. The lines may be lossless or lossy, with frequency dependent parameters. First a sufficient amount of information about the system is measured or computed over an specified frequency range. Then this information is used as an input for a GA to determine the inductance and capacitance matrices of the system. The theory used for fitness evaluation is based on the steplines approximation of the nonuniform transmission lines and quasi-TEM assumptions. Using steplines approximation the system of coupled nonuniform transmission lines is subdivided into arbitrary large number of coupled uniform lines (steplines) with different characteristics. Then using modal decomposition method the system of coupled partial differential equations for each step is decomposed to a number of uncoupled ordinary wave equations which are then solved in frequency-domain.

We investigate possibility of fault-tolerant and self-stabilizing protocols (ftss protocols) using an unreliable failure detector. Our main contribution is (1) to newly introduce k-accuracy of an unreliable failure detector, (2) to show that k-accuracy of a failure detector is necessary for any ftss k-group consensus protocol, and (3) to present three ftss k-group consensus protocols using a k-accurate and weakly complete failure detector under the read/write daemon on complete networks and on (n-k+1)-connected networks, and under the central daemon on complete networks.

The main contribution of this work is to propose energy-efficient randomized initialization protocols for ad-hoc radio networks (ARN, for short). First, we show that if the number n of stations is known beforehand, the single-channel ARN can be initialized by a protocol that terminates, with high probability, in O(n) time slots with no station being awake for more than O(log n) time slots. We then go on to address the case where the number n of stations in the ARN is not known beforehand. We begin by discussing, an elegant protocol that provides a tight approximation of n. Interestingly, this protocol terminates, with high probability, in O((log n)2) time slots and no station has to be awake for more than O(log n) time slots. We use this protocol to design an energy-efficient initialization protocol that terminates, with high probability, in O(n) time slots with no station being awake for more than O(log n) time slots. Finally, we design an energy-efficient initialization protocol for the k-channel ARN that terminates, with high probability, in O(n/k+log n) time slots, with no station being awake for more than O(log n) time slots.

This paper presents an accelerated image halftoning technique using an improved genetic algorithm with tiny populations. The algorithm is based on a new cooperative model for genetic operators in GA. Two kinds of operators are used in parallel to produce offspring: (i) SRM (Self-Reproduction with Mutation) to introduce diversity by means of Adaptive Dynamic-Block (ADB) mutation inducing the appearance of beneficial mutations. (ii) CM (Crossover and Mutation) to promote the increase of beneficial mutations in the population. SRM applies qualitative mutation only to the bits inside a mutation block and controls the required exploration-exploitation balance through its adaptive mechanism. An extinctive selection mechanism subjects SRM's and CM's offspring to compete for survival. The simulation results show that our scheme impressively reduces computer memory and processing time required to obtain high quality halftone images. For example, compared to the conventional image halftoning technique with GA, the proposed algorithm using only a 2% population size required about 15% evaluations to generate high quality images. The results make our scheme appealing for practical implementations of the image halftoning technique using GA.

An approach for analysis of the small signal response of the carriers in semiconductors is presented. The integro-differential equation, describing the phenomenon in the time domain is transformed into a Fredholm integral equation of the second kind. The response of the carrier system to a small signal of a general time dependence can be calculated by the knowledge of the response to an impulse signal, defined by a delta function in time. For an impulse signal, the obtained integral equation resembles the basic structure of the integral form of the time dependent (evolution) Boltzmann equation. Due to this similarity a physical model of the impulse response process is developed. The model explains the response to an impulse signal in terms of a relaxation process of two carrier ensembles, governed by a Boltzmann equation. A Monte-Carlo method is developed which consists of algorithms for modeling the initial distribution of the two ensembles. The numerical Monte-Carlo theory for evaluation of integrals is applied. The subsequent relaxation process can be simulated by the standard algorithms for solving the Boltzmann equation. The presented simulation results for Si and GaAs electrons serve as a test of the Monte-Carlo method and demonstrate that the physical model can be used for explanation of the small signal response process.

For many military and civilian large-scale, real-world systems of interest, data are first acquired asynchronously, i. e. at irregular intervals of time, at geographically-dispersed sites, processed utilizing decision-making algorithms, and the processed data then disseminated to other appropriate sites. The term real-world refers to systems under computer control that relate to everyday life and are beneficial to the society in the large. The traditional approach to such problems consists of designing a central entity which collects all data, executes a decision making algorithm sequentially to yield the decisions, and propagates the decisions to the respective sites. Centralized decision making algorithms are slow and highly vulnerable to natural and artificial catastrophes. Recent literature includes successful asynchronous, distributed, decision making algorithm designs wherein the local decision making at every site replaces the centralized decision making to achieve faster response, higher reliability, and greater accuracy of the decisions. Two key issues include the lack of an approach to synthesize asynchronous, distributed, decision making algorithms, for any given problem, and the absence of a comparative analysis of the quality of their decisions. This paper proposes MFAD, a Mathematical Framework for Asynchronous, Distributed Systems, that permits the description of centralized decision-making algorithms and facilities the synthesis of distributed decision-making algorithms. MFAD is based on the Kohn-Nerode distributed hybrid control paradigm. It has been a belief that since the centralized control gathers every necessary data from all entities in the system and utilizes them to compute the decisions, the decisions may be "globally" optimal. In truth, however, as the frequency of the sensor data increases and the environment gets larger, dynamic, and more complex, the decisions are called into question. In the distributed decision-making system, the centralized decision-making is replaced by those of the constituent entities that aim at minimizing a Lagrangian, i. e. a local, non-negative cost criterion, subject to the constraints imposed by the global goal. Thus, computations are carried out locally, utilizing locally obtained dataand appropriate information that is propagated from other sites. It is hypothesized that with each entity engaged in optimizing its individual behavior, asynchronously, concurrently, and independent of other entities, the distributed system will approach "global" optimal behavior. While it does not claim that such algorithms may be synthesized for all centralized real-world systems, this paper implements both the centralized and distributed paradigms for a representative military battlefield command, control, and communication (C3) problem. It also simulates them on a testbed of a network of workstations for a comparative performance evaluation of the centralized and decentralized paradigms in the MFAD framework. While the performance results indicate that the decentralized approach consistently outperforms the centralized scheme, this paper aims at developing a quantitative evaluation of the quality of decisions under the decentralized paradigm. To achieve this goal, it introduces a fundamental concept, embodied through a hypothetical entity termed "Perfect Global Optimization Device (PGOD)," that generates perfect or ideal decisions. PGOD possesses perfect knowledge, i. e. the exact state information of every entity of the entire system, at all times, unaffected by delay. PGOD utilizes the same decision-making algorithm as the centralized paradigm and generates perfect globally-optimal decisions which, though unattainable, provide a fundamental and absolute basis for comparing the quality of decisions. Simulation results reveal that the quality of decisions in the decentralized paradigm are superior to those of the centralized approach and that they approach PGOD's decisions.

A number of parallel algorithms have been developed to solve large-scale real world problems. Although there has been much work on the design of parallel algorithms, there has been little on the design of languages for expressing these algorithms. This paper describes the BPL, a new parallel language designed for butterfly networks. The purpose of this language is to help designers in hiding the complexity of the algorithm and leaving details of mapping between data and processors for lower level. BPL provides a simpler virtual machine for the designer , in order to avoid thinking about control of processors and data. From another point of view, BPL helps designer to logically check the algorithm and correct any possible error in it. The paper gives some examples implemented by this language. In addition, we have also implemented a software tool which simulates the running of the algorithm on the network. The results lead us to believe that this language would be useful in representing all kinds of algorithms on this network including normal algorithms and others.

All the existing scheduling algorithms order the instructions of the program in such a way that it can be executed in minimal time only for one fixed number of processors. In this paper we propose a new scheduling method, called Parallelism-Independent Scheduling Method, which enables the execution of the scheduled program on parallel computers with any degree of parallelism in near-optimal time. We propose three Parallelism-Independent algorithms, which have the following phases: obtaining a parallel schedule by using a list scheduling heuristics, optimization of the parallel schedule by rearranging the tasks in each level, so that they can be executed efficiently with different degrees of parallelism, serialization of the parallel schedule, and insertion of markers for the parallel execution limits. The three algorithms differ in their optimization phase. To prove the efficiency of our algorithms, we have made simulations with random directed acyclic graphs with different size and degree of parallelism. We compared the results in terms of schedule length to those obtained using the Critical Path Algorithm separately for each degree of parallelism.

Asynchronous, distributed, decision-making (ADDM) systems constitute a special class of distributed problems and are characterized as large, complex systems wherein the principal elements are the geographically-dispersed entities that communicate among themselves, asynchronously, through message passing and are permitted autonomy in local decision-making. A fundamental property of ADDM systems is stability that refers to their behavior under representative perturbations to their operating environments, given that such systems are intended to be real, complex, and to some extent, mission critical systems, and are subject to unexpected changes in their operating conditions. ADDM systems are closely related to autonomous decentralized systems (ADS) in the principal elements, the difference being that the characteristics and boundaries of ADDM systems are defined rigorously. This paper introduces the concept of stability in ADDM systems and proposes an intuitive yet practical and usable definition that is inspired by those used in Control Systems and Physics. A comprehensive stability analysis on an accurate simulation model will provide the necessary assurance, with a high level of confidence, that the system will perform adequately. An ADDM system is defined as a stable system if it returns to a steady-state in finite time, following perturbation, provided that it is initiated in a steady-state. Equilibrium or steady-state is defined through placing bounds on the measured error in the system. Where the final steady-state is equivalent to the initial one, a system is referred to as strongly stable. If the final steady-state is potentially worse then the initial one, a system is deemed marginally stable. When a system fails to return to steady-state following the perturbation, it is unstable. The perturbations are classified as either changes in the input pattern or changes in one or more environmental characteristics of the system such as hardware failures. Thus, the key elements in the study of stability include steady-state, perturbations, and stability. Since the development of rigorous analytical models for most ADDM systems is difficult, if not impossible, the definitions of the key elements, proposed in this paper, constitute a general framework to investigate stability. For a given ADDM system, the definitions are based on the performance indices that must be judiciously identified by the system architect and are likely to be unique. While a comprehensive study of all possible perturbations is too complex and time consuming, this paper focuses on a key subset of perturbations that are important and are likely to occur with greater frequency. To facilitate the understanding of stability in representative real-world systems, this paper reports the analysis of two basic manifestations of ADDM systems that have been reported in the literature --(i) a decentralized military command and control problem, MFAD, and (ii) a novel distributed algorithm with soft reservation for efficient scheduling and congestion mitigation in railway networks, RYNSORD. Stability analysis of MFAD and RYNSORD yields key stable and unstable conditions.

The minimum distance of a linear code C is a useful metric property for estimating the error correction upper bound of C and the maximum likelihood decoding of a linear code C is also of practical importance and of theoretical interest. These problems are known to be NP-hard to approximate within any constant relative error to the optimum. As a problem related to the above, we consider the maximization problem MAX-WEIGHT: Given a generator matrix of a linear code C, find a codeword c C with its weight as close to the maximum weight of C as possible. It is shown that MAX-WEIGHT PTAS unless P=NP, however, no nontrivial approximation upper and lower bounds are known. In this paper, we investigate the complexity of MAX-WEIGHT to make the approximation upper and lower bounds more precise, and show that (1) MAX-WEIGHT is APX-complete; (2) MAX-WEIGHT is approximable within relative error 1/2 to the optimum; (3) MAX-WEIGHT is not approximable within relative error 1/10 to the optimum unless P=NP.

This paper studies the "usefulness" of initial conditions for distributed algorithms on anonymous networks. In the literature, several initial conditions such as making one vertex a leader, giving the number of vertex to each vertices, and so on, have been considered. In this paper, we study a relation between the initial condition by considering transformation algorithm from one initial condition to another. For such transformation algorithms, we consider in this paper, both deterministic and randomized distributed algorithms. For each deterministic and randomized transformation type, we show that the relation induces an infinite lattice structure among equivalence classes of initial conditions.

Distributed computation has attracted considerable attention and large-scale distributed systems have been designed and developed. A distributed system inherently has possibility of fault tolerance because of its redundancy. Thus, a great deal of investigation has been made to design fault-tolerant distributed algorithms. This paper introduces two promising paradigms, self-stabilization and wait-freedom, for designing fault-tolerant distributed algorithms and discusses some subjects important from the point of view of algorithm engineering.

The main problem considered is submodular set cover, the problem of minimizing a linear function under a nondecreasing submodular constraint, which generalizes both well-known set cover and minimum matroid base problems. The problem is NP-hard, and two natural greedy heuristics are introduced along with analysis of their performance. As applications of these heuristics we consider various special cases of submodular set cover, including partial cover variants of set cover and vertex cover, and node-deletion problems for hereditary and matroidal properties. An approximation bound derived for each of them is either matching or generalizing the best existing bounds.

The subject of the paper is to give an overview and latest results on the Legal Firing Sequence Problem of Petri nets (LFS for short). LFS is very fundamental in the sense that it appears as a subproblem or a simpler form of various basic problems in Petri net theory, such as the well-known marking reachability problem, the minimum initial resource allocation problem, the liveness (of level 4) problem, the scheduling problem and so on. However, solving LFS generally is not easy: it is NP -hard even for Petri nets having very simple structures. This intractability of LFS may have been preventing us from producing efficient algorithms for those problems. So research on LFS from computational complexity point of view seems to be rewarding.

Maximum Satisfiability Problem (MAX SAT) is one of the most natural optimization problems. Since it is known to be NP-hard, approximation algorithms have been considered. The aim of this survey is to show recent developments of approximation algorithms for MAX SAT.

We first describe fundamental results about submodular functions and submodular flows, which lay a basis for devising efficient algorithms for submodular flows. We then give a comprehensive survey on algorithms for submodular flows and show some possible future research directions.

The legal firing sequence problem (LFS) asks if it is possible to fire each transition some prescribed number of times in a given Petri net. It is a fundamental problem in Petri net theory as it appears as a subproblem, or as a simplified version of marking reachability, minimum initial resource allocation, liveness, and some scheduling problems. It is also known to be NP-hard, however, even under various restrictions on nets (and on firing counts), and no efficient algorithm has been previously reported for any class of nets having general edge weights. We show in this paper that LFS can be solved in polynomial time (in O(n log n) time) for a subclass of state machines, called cacti, with arbitrary edge weights allowed (if each transition is asked to be fired exactly once).

A convex hull is one of the most fundamental and interesting geometric constructs in computational geometry. Considerable research effort has focused on developing algorithms, both in serial and in parallel, for computing convex hulls. In particular, there are few problems whose parallel algorithms are so thoroughly studied as convex hull problems. In this paper, we review the convex hull parallel algorithms and their paradigm. We provide a summary of results and introduce several interesting topics including typical techniques, output-size sensitive methods, randomized approaches, and robust algorithms for convex hull problems, with which we may see the highlights of the whole research for parallel algorithms. Most of our discussion uses the PRAM (Parallel Random Access Machine) computational model, but still we give a glance at the results of the other parallel computational models such as mesh, mesh-of-trees, hypercube, recofigurable array, and models of coarse grained multicomputers like BSP and LogP.

This paper analyzes what structural features of graph problems allow efficient parallel algorithms. We survey some parallel algorithms for typical problems on three kinds of graphs, outerplanar graphs, trapezoid graphs and in-tournament graphs. Our results on the shortest path problem, the longest path problem and the maximum flow problem on outerplanar graphs, the minimum-weight connected dominating set problem and the coloring problem on trapezoid graphs and Hamiltonian path and Hamiltonian cycle problem on in-tournament graphs are adopted as working examples.

A coterie is a set of quorums such that any two quorums intersect each other, and is used in a quorum based algorithm for solving the mutual exclusion problem. The availability of a coterie is the probability that the algorithm (adopting the coterie) tolerates process and/or link failures. Constructing an optimal coterie in terms of the availability is therefore important from the view of fault tolerance, but unfortunately, even calculating the availability is known to be #P-hard. Recently Harada and Yamashita proposed several heuristic methods for improving the availability of a coterie. This letter first evaluates their performance and then proposes a practical method for constructing a semi-optimal coterie by using one of the heuristic methods as a main component.