Deciding bisimulation and trace equivalences for systems with many identical processes

In the study of process semantics, trace equivalence and bisimulation equivalence constitute the two extremes of the so-called linear time—branching time spectrum. In this paper, we study the complexity and decidability issues of deciding trace and bisimulation equivalences for the model of systems with many identical processes with respect to various interprocess communication structures. In our model, each system consists of an arbitrary number of identical finite-state processes using Milner's calculus of communicating systems (CCS) as the style of interprocess communication. As it turns out, deciding trace and bisimulation equivalences are undecidable for star-like and linear systems, whereas the two problems are complete for PSPACE and PTIME, respectively, for fully connected systems.     

Active Disk Paxos with infinitely many processes

Abstract We present an improvement to the Disk Paxos protocol by Gafni and Lamport which utilizes extended functionality and flexibility provided by Active Disks and supports unmediated concurrent data access by an unlimited number of processes. The solution facilitates coordination by an infinite number of clients using finite shared memory. It is based on a collection of read-modify-write objects with faults, that emulate a new, reliable shared memory abstraction called a ranked register. The required read-modify-write objects are readily available in Active Disks and in Object Storage Device controllers, making our solution suitable for state-of-the-art Storage Area Network (SAN) environments. A preliminary version of this work appears in Proceedings of the 21st ACM Symposium on Principles of Distributed Computing (PODC02), August 2002.     

Almost periodic processes with conflict control with many participants

For a stationary process with conflict control with equal opportunities of the participants, sufficient conditions of the capture of an evader by a group consisting of a given number pursuers are obtained.     

Stability of sampled-data composite systems with many nonlinearities

A sampled-data composite system given by a set of vector difference equationsx_{i}(tau + 1) - x_{i}(tau) = sum min{j = 1} max{n} A_{ij} f_{j}[x_{j}(tau)], i = 1 ..., nis dealt with. The system given byx_{i}(tau + 1) - x_{i}(tau) = A_{ij} f_{i}[x_{i}(tau)]is referred to as theith isolated subsystem. It is shown that the composite system is asymptotically stable in the large if the fisatisfy certain conditions and the leading principal minors of the determinant|b_{ij}|, i,j = 1, ..., n,are all positive. Here, the diagonal element biiis a positive number such that|x_{i}(tau + 1)| - |x_{i}(tau) | leq - b_{ij}| f_{i}[x_{i}(tau)]|holds with regard to the motion of theith isolated subsystem, and the nondiagonal elementb_{ij} , i neq j, is the minus of|A_{ij}|, which is defined as the maximum of|A_{ij}x_{j}|, for|x_{j}| = 1. Some extensions of this result are also given. Composite relay controlled systems are studied as examples.     

Partial consensus of identical feedforward dynamic systems with input saturations

This paper studies the partial consensus problem for identical feedforward dynamic systems with input saturations. We construct two consensus protocols using the partial‐state information and full‐state information, respectively. Applying a change of coordinates, feedforward system is transformed into the block diagonal form. Then, by utilizing the bounded real lemma and small gain theorem, we solve the partial consensus problem, and the existence of each protocol is derived. Copyright © 2015 John Wiley & Sons, Ltd.     

Reliability evaluation in complex systems with many failure modes

A general method is presented for evaluating the reliability of complex systems, subsystems of which may have many failure modes. The method is easily com-puterizable, computationally efficient and has low memory requirements. Compared to the existing methods for a single failure mode case, this method has the additional advantages of avoiding repeated generation of compared numbers and requiring no selection of prime implieants or their subsets. Examples of the method have been included.     

Synchronization in networks of identical linear systems

The paper investigates the synchronization of a network of identical linear state-space models under a possibly time-varying and directed interconnection structure. The main result is the construction of a dynamic output feedback coupling that achieves synchronization if the decoupled systems have no exponentially unstable mode and if the communication graph is uniformly connected. The result can be interpreted as a generalization of classical consensus algorithms. Stronger conditions are shown to be sufficient–but to some extent, also necessary–to ensure synchronization with the diffusive static output coupling often considered in the literature.     

Oscillation family in weakly coupled identical systems

Consideration was given to an autonomous model with weakly coupled identical subsystems. Existence of a family of periodic solutions which is similar to the family in a subsystem was established. A scenario of bifurcations of the characteristic exponents was given, and the stabilization problem was solved. An example was given.     

User-perceived reliability of unrepairable shared protection systems with functionally identical units

In this article, we investigate the reliability of M-for-N (M:N) shared protection systems. We focus on the reliability that is perceived by an end user of one of N units. We assume that any failed unit is instantly replaced by one of the M units (if available). We describe the effectiveness of such a protection system in a quantitative manner under the condition that the failed units are not repairable. Mathematical analysis gives the closed-form solution of the reliability and mean time to failure (MTTF). We also analyse several numerical examples of the reliability and MTTF. This result can be applied, for example, to the analysis and design of an integrated circuit consisting of redundant backup components. In such a device, repairing a failed component is unrealistic. The analysis provides useful information for the design for general shared protection systems in which the failed units are not repaired.     

A distributed resource allocation algorithm for many processes

Resource allocation is the problem that a process may enter a critical section CS of its code only when its resource requirements are not in conflict with those of other processes in their critical sections. For each execution of CS, these requirements are given anew. In the resource requirements, levels can be distinguished, such as e.g. read access or write access. We allow unboundedly many processes that communicate by reliable asynchronous messages and have finite memory. A simple starvation-free solution is presented. Processes only wait for one another when they have conflicting resource requirements. The correctness of the solution is argued with invariants and temporal logic. It has been verified with the proof assistant PVS.     

On standard control problems for systems with infinitely many unstable poles

In this paper, H^∞ control for a class of linear time invariant systems with infinitely many unstable poles is studied. An example of such a plant is a high gain system with delayed feedback. We formulate the problem via a generalized plant which consists of a rational transfer matrix and the inverse of a scalar (possibly irrational) inner function. It is shown that the problem can be decomposed into a finite-dimensional H^∞ control problem and an additional rank condition.     

Random search techniques for optimization of nonlinear systems with many parameters

This paper concerns the application of adaptive random search techniques to large parameter optimization and identification problems. A brief review of the algorithm is presented, followed by a discussion of 3 examples: (1) identification of 25 unknown parameters in a nonlinear 5-degree of freedom mechanical system (2) identification of 17 parameters in a nonlinear model of soil mechanics and (3) determination of optimum values of 24 parameters to obtain a match of two response spectra. The results indicate the robustness and applicability of adaptive random search to a wide variety of nonlinear optimization problems.     

Priority worksheet brings order to information systems projects

"Eeeny, meeny, miny, moe, and the first priority is ..." maybe the CEO's pet project or nursing's necessity. Putting aside "gut feel" for an objective method promises to streamline the process of prioritizing I/S projects, according to Saint Alexis Hospital Medical Center leadership.     

Gathering identical autonomous systems on a circle using stigmergy

In this paper we provide a protocol solving the problem of gathering of identical autonomous systems (aka ants) on a circle. In our biologically inspired model the autonomous systems are unable to communicate directly, instead they employ the mechanism of pheromone marking. The gathering on a circle is not always solvable, however our protocol will terminate in finite time if ants are in a general initial position. Since the gathering problem on a line is unsolvable for obvious reasons for any non-degenerate initial position, this implies that if the ants are in generic initial position they will be able to decide in finite time whether they are on a line or on a circle. We give asymptotic bounds for the time our protocol needs to terminate, and show that for fixed number of ants, the termination time of any protocol can be arbitrarily long. Finally, our protocol may be adopted to the case of asynchronous drop-downs and starting times of the autonomous systems.     

The computation of stability regions for systems with many singular points†

A method is presented for the generation of Liapunov functions for the analysis of non-linear systems with many singular points. Criteria are given for non-oscillatory behaviour, Stability regions for all stable equilibria can be found, using a single Liapunov function of the proposed type.     

Designing a stable cycle in weakly coupled identical systems

Consideration was given to a dynamic model containing weakly coupled identical subsystems. The subsystem was assumed to admit a family of periodic solutions where the period is a monotonic function of one parameter. Requirements on the coupling under which the model has an asymptotic orbital stable cycle were established. The problem of stabilization of the model oscillations by a small smooth autonomous coupling control was solved using the results obtained. The system of two coupled conservative systems with one degree of freedom was considered individually.     

On the mixed sensitivity minimization for systems with infinitely many unstable modes

In this note we consider a class of linear time invariant systems with infinitely many unstable modes. By using the parameterization of all stabilizing controllers and a data transformation, we show that controllers for such systems can be computed using the techniques developed earlier for infinite dimensional plants with finitely many unstable modes.     

优先级有限时的单处理器静态优先级调度

静态优先级调度在实际应用中经常受到系统支持的优先级个数的影响,当任务个数多于系统优先级个数时,需要将几个任务优先级映射成一个系统优先级.这可能引起优先级映射问题,使映射前可调度的系统(任务集合)在映射后变得不可调度.解决这一问题需要减少时间复杂度的映射算法和判定映射后任务可调度性的充分必要条件主要存在3种映射算法:(1)按照任务优先级递减顺序进行映射的DPA(decreasing priority assignment)算法;(2)按照优先级递增顺序进行映射的IPA(Increasing priority assignment)算法;(3)阈值段间映射法(thresh01d segment mapping,简称TSM).描述了3种算法的实现和判定条件,论述并证明了算法特性,分析并通过仿真实验比较了算法的性能,最后总结了3种算法各自的适用场合.比较结果和结论对实时嵌入式系统的设计和实现具有一定的参考价值.     

The many faces of consensus in distributed systems

Known results regarding consensus among processors are surveyed and related to practice. The ideas embodied in the various proofs are explained. The goal is to give practitioners some sense of the system hardware and software guarantees that are required to achieve a given level of reliability and performance. The survey focuses on two categories of failures: fail-stop failures, which occur when processors fail by stopping; and Byzantine failures, which occur when processors fail by acting maliciously