Minimizing the maximum delay for reaching consensus in quorum-basedmutual exclusion schemes

The use of quorums is a well-known approach to achieving mutual exclusion in distributed computing systems. This approach works based on a coterie, a special set of node groups where any pair of the node groups shares at least one common node. Each node group in a coterie is called a quorum. Mutual exclusion is ensured by imposing that a node gets consensus from all nodes in at least one of the quorums before it enters a critical section. In a quorum-based mutual exclusion scheme, the delay for reaching consensus depends critically on the coterie adopted and, thus, it is important to find a coterie with small delay. Fu (1997) introduced two related measures called max-delay and mean-delay. The former measure represents the largest delay among all nodes, while the latter is the arithmetic mean of the delays. She proposed polynomial-time algorithms for finding max-delay and mean-delay optimal coteries when the network topology is a tree or a ring. In this paper, we first propose a polynomial-time algorithm for finding max-delay optimal coteries and, then, modify the algorithm so as to reduce the mean-delay of generated coteries. Unlike the previous algorithms, the proposed algorithms can be applied to systems with arbitrary topology     

New approach to the synthesis of a stabilizing control method for a power system

A new approach to the synthesis of a stabilizing control method for a multimachine power system is presented. The power system dynamics based on the usual assumptions can be formulated as a class of non-linear dynamic systems in which are contained the sinusoidal functions associated with the power torque-angle curve of the AC generator. In this theoretical scheme, an optimal control law, which retains the principal non-linearity of the system, is derived by using optimization techniques well known in linear optimal control theory. The stabilizing control of an N-synchronous machine power system with velocity governor and phase-shifter is synthesized by using the optimal control method. The usefulness of the proposed method is illustrated by the stabilizing control problem for a three-machine power system, taking into account additional control signals for the governing system and phase-shifter control systems, and simulation results are given numerically.     

Optimization of metal-forming process via a hybrid intelligent optimization technique

In recent years, finite element simulation has been increasingly combined with optimization techniques and applied to optimization of various metal-forming processes. The robustness and efficiency of process optimization are critical factors to obtain ideal results, especially for those complicated metal-forming processes. Gradient-based optimization algorithms are subject to mathematical restrictions of discontinuous searching space, while nongradient optimization algorithms often lead to excessive computation time. This paper presents a novel intelligent optimization approach that integrates machine learning and optimization techniques. An intelligent gradient-based optimization scheme and an intelligent response surface methodology are proposed, respectively. By machine learning based on the rough set algorithm, initial total design space can be reduced to self-continuous hypercubes as effective searching spaces. Then optimization algorithms can be implemented more effectively to find optimal design results. An extrusion forging process and a U channel roll forming process are studied as application samples and the effectiveness of the proposed approach is verified.     

Computational Method for a Class of Switched System Optimal Control Problems

We consider an optimal control problem with dynamics that switch between several subsystems of nonlinear differential equations. Each subsystem is assumed to satisfy a linear growth condition. Furthermore, each subsystem switch is accompanied by an instantaneous change in the state. These instantaneous changes-called ldquostate jumpsrdquo-are influenced by a set of control parameters that, together with the subsystem switching times, are decision variables to be selected optimally. We show that an approximate solution for this optimal control problem can be computed by solving a sequence of conventional dynamic optimization problems. Existing optimization techniques can be used to solve each problem in this sequence. A convergence result is also given to justify this approach.     

Maximum variation analysis based analytical target cascading for multidisciplinary robust design optimization under interval uncertainty

Analytical target cascading (ATC) is a generally used hierarchical method for deterministic multidisciplinary design optimization (MDO). However, uncertainty is almost inevitable in the lifecycle of a complex system. In engineering practical design, the interval information of uncertainty can be more easily obtained compared to probability information. In this paper, a maximum variation analysis based ATC (MVA-ATC) approach is developed. In this approach, all subsystems are autonomously optimized under the interval uncertainty. MVA is used to establish an outer-inner framework which is employed to find the optimal scheme of system and subsystems. All subsystems are coordinated at the system level to search the system robust optimal solution. The accuracy and validation of the presented approach are tested using a classical mathematical example, a heart dipole optimization problem, and a battery thermal management system (BTMS) design problem.     

Coterie join algorithm

Given a set of nodes in a distributed system, a coterie is a collection of subsets of the set of nodes such that any two subsets have a nonempty intersection and are not properly contained in one another. A subset of nodes in a coterie is called a quorum. An algorithm, called the join algorithm, which takes nonempty coteries as input, and returns a new, larger coterie called a composite coterie is introduced. It is proved that a composite coterie is nondominated if and only if the input coteries are nondominated. Using the algorithm, dominated or nondominated coteries may be easily constructed for a large number of nodes. An efficient method for determining whether a given set of nodes contains a quorum of a composite coterie is presented. As an example, tree coteries are generalized using the join algorithm, and it is proved that tree coteries are nondominated. It is shown that the join algorithm may be used to generate read and write quorums which may be used by a replica control protocol     

Reachability and optimal control for linear hybrid automata: a quantifier elimination approach

This paper considers an optimal control problem for linear hybrid automata (LHA). First, we present a controller synthesis algorithm based on reachability analysis. The algorithm computes the maximal initial set from which the controller drives the system to a given target set. It is shown that, using quantifier elimination (QE), an under-approximation of the maximal reachable set can be derived. Next, a weighted time-optimal control problem is solved by transforming it into a constrained optimization problem whose constraints are a set of inequalities with quantifiers. Quantifier elimination (QE) techniques are employed in order to derive the quantifier free inequalities that are shown to be linear. Thus, the optimal cost is obtained using linear programming. For any state belonging to the maximal initial set the optimal switching times and the optimal continuous control inputs are computed. These are used in order to derive a hybrid controller which is optimal with respect to the cost function. Our results are applied to an air traffic management example which is of practical interest.     

Multi-objective decision support system in numerical reliability optimization of modern electronic packaging

Nowadays, numerical prototyping methods in electronic packaging are widely used. This is mainly due to cost and time reduction and improved functionality and reliability of final products. Recently, there has been a lot of interest and work conducted on advanced numerical optimization, which can be directly applied to prototyping. So far, the optimization is focused on one criteria while neglecting problem of multi-objectivity, which is not the best approach from practical point of view. Nevertheless, such an approach is jusitified from the point of view of complex analysis, interdisciplinary issues and reduced accuracy of numerical models. In reality, there are usually many criteria which, in order to solve the problem, have to be taken into consideration. There are many multi-objective methods, of which the Pareto set approach is mostly cited in the literature. The “problem” of multi-objective optimization is that not a single optimal solution has resulted but the set of equivalent optimal solutions. This set of equivalent optimal solutions is referenced as “the Pareto set”. From the mathematical point of view, every value from this set can be treated as optimal for certain assumed constraints. However, there could be some additional conditions which cannot be applied to optimization process and some of the results from the Pareto set are more likely (i.e., the fabrication process will be more repeatable) then the others. So, the question is: which value from the Pareto set should be taken to further processing? There are two possibilities: asking an expert for the advice or use the decision making system. Decision making methods based on multi-objective optimization could be referenced as “Multiple criteria decision making” (MCDM) or “Multiple criterial decision aid” (MCDA) systems. There are several groups of these methods: (a) mathematical multi-objective programming, (b) artificial intelligence methods, (c) simple arithmetic methods, and (d) advanced mathematical methods. The current paper will focus on designing and application of the decision support system for multi-objective numerical reliability optimization of electronic packaging. The work will be based on the self developed numerical tool based on Python Scrippting language and will present its application to selected microelectronic packages based on its numerical model elaborated in ABAQUS.     

A hybrid genetic algorithm for constrained multi-objective optimization under uncertainty and target matching problems

This work presents a new approach for interval-based uncertainty analysis. The proposed approach integrates a local search strategy as the worst-case-scenario technique of anti-optimization with a constrained multi-objective genetic algorithm. Anti-optimization is a term for an approach to safety factors in engineering structures which is described as pessimistic and searching for least favorable responses, in combination with optimization techniques but in contrast to probabilistic approaches. The algorithm is applied and evaluated to be efficient and effective in producing good results via target matching problems: a simulated topology and shape optimization problem where a ‘target’ geometry set is predefined as the Pareto optimal solution and a constrained multiobjective optimization problem formulated such that the design solutions will evolve and converge towards the target geometry set.     

Measurement-based optimization of batch and repetitive processes using an integrated two-layer architecture

This paper is concerned with optimal control of batch and repetitive processes in the presence of uncertainty. An integrated two-layer optimization strategy is proposed, whereby within-run corrections are performed using a neighboring-extremal update strategy and run-to-run corrections are based on a constraint-adaptation scheme. The latter is appealing since a feasible operating strategy is guaranteed upon convergence, and its combination with neighboring-extremal updates improves the reactivity and convergence speed. Moreover, these two layers are consistent in that they share the same objective function. The proposed optimization scheme is declined into two versions, namely an indirect version based on the Pontryagin maximum principle and a direct version that applies a control parameterization and nonlinear programming techniques. Although less rigorous, the latter approach can deal with singular extremals and path constraints as well as handle active-set changes more conveniently. Two case studies are considered. The indirect approach is demonstrated for a level-control problem in an experimental two-tank system, whereas the direct approach is illustrated in numerical simulation on a fed-batch reactor for acetoacetylation of pyrrole. The results confirm that faster adaptation is possible with the proposed integrated two-layer scheme compared to either constraint adaptation or neighboring-extremal update alone.     

基于伪谱法的双摆吊车时间最优消摆轨迹规划策略

在工业生产过程中,桥式吊车系统经常会体现出双摆系统的特性,导致更多欠驱动状态量的出现,增大控制难度.基于此,论文提出了一种针对双摆桥式吊车系统的时间最优轨迹规划方法,可以得到全局时间最优且具有消摆能力的轨迹.具体而言,为方便地构造以时间为代价函数的优化问题,首先对系统运动学模型进行相应的变换;在此基础上,考虑包括两级摆角及台车速度和加速度上限值在内的多种约束,构造出相应的优化问题;然后,利用高斯伪谱法(Gauss-pseudospectral method, GPM)将该带约束的优化问题转化为更易于求解的非线性规划问题,且在转化过程中,可以非常方便地考虑轨迹约束.求解该非线性规划问题,即可得到时间最优的台车轨迹.不同于已有的大多数方法,该方法可获得全局时间最优的结果.最后,通过仿真与实验结果验证了这种时间最优轨迹规划方法具有满意的控制性能.     

Integrated system optimization and parameter estimation using a general form of steady-state model

Based on a general form of steady-state model, the integrated system optimization and parameter estimation problem is formulated and two algorithms arc derived for determining the optimal operating point of a process. A set of model qualifications, which are very mild, is defined to ensure that the real process optimum can be obtained by solving an equivalent model based optimization problem. Optimality and convergence conditions of the algorithms are analysed. The practical utility of the approach is demonstrated by a simulation of a continuous chemical reactor. It is observed that the correct optimum is quickly achieved in spite of using an incorrect model.     

Optimal design of infinite repetitive structures

An approach for designing optimal repetitive structures under arbitrary static loading is presented. It is shown that the analysis of such infinite structures can be reduced to the analysis of the repeating module under transformed loading and boundary conditions. Consequently, both the design parameters and the analysis variables constitute a relatively small set which facilitates the optimization process. The approach hinges on the representative cell method. It is based on formulating the analysis equations and the continuity conditions for a sequence of typical modules. Then, by means of the discrete Fourier transform this problem translates into a boundary value problem of a representative cell in transformed variables, which can be solved by any appropriate analytical or numerical method. The real structural response any-where in the structure is then obtained by the inverse transform. The sensitivities can also be calculated on the basis of the sensitivities of the representative cell. The method is illustrated by the design for minimum compliance with a volume constraint of an infinite plane truss. It is shown that by employing this analysis method within an optimal design scheme one can incorporate a reduced analysis problem in an intrinsically small design space.     

Transversal merge operation: a nondominated coterie construction method for distributed mutual exclusion

A coterie is a set of subsets (called quorums) of the processes in a distributed system such that any two quorums intersect with each other and is mainly used to solve the mutual exclusion problem in a quorum-based algorithm. The choice of a coterie sensitively affects the performance of the algorithm and it is known that nondominated (ND) coteries achieve good performance in terms of criteria such as availability and load. On the other hand, grid coteries have some other attractive features: 1) a quorum size is small, which implies a low message complexity, and 2) a quorum is constructible on the fly, which benefits a low space complexity. However, they are not ND coteries unfortunately. To construct ND coteries having the favorite features of grid coteries, we introduce the transversal merge operation that transforms a dominated coterie into an ND coterie and apply it to grid coteries. We call the constructed ND coteries ND grid coteries. These ND grid coteries have availability higher than the original ones, inheriting the above desirable features from them. To demonstrate this fact, we then investigate their quorum size, load, and availability, and propose a dynamic quorum construction algorithm for an ND grid coterie.     

A stochastic model for heterogeneous computing and its applicationin data relocation scheme development

In a dedicated, mixed-machine, heterogeneous computing (HC) system, an application program may be decomposed into subtasks, then each subtask assigned to the machine where it is best suited for execution. Data relocation is defined as selecting the sources for needed data items. It is assumed that multiple independent subtasks of an application program can be executed concurrently on different machines whenever possible. A theoretical stochastic model for HC Is proposed, in which the computation times of subtasks and communication times for intermachine data transfers can be random variables. The optimization problem for finding the optimal matching, scheduling, and data relocation schemes to minimize the total execution time of an application program is defined based on this stochastic HC model. The global optimization criterion and search space for the above optimization problem are described. It is validated that a greedy algorithm-based approach can establish a local optimization criterion for developing data relocation heuristics. The validation is provided by a theoretical proof based on a set of common assumptions about the underlying HC system and application program. The local optimization criterion established by the greedy approach, coupled with the search space defined for choosing valid data relocation schemes, can help developers of future practical data relocation heuristics     

Real-time adaptive multi-robot exploration with application to underwater map construction

This paper deals with the problem of autonomous exploration of unknown areas using teams of Autonomous X Vehicles (AXVs)—with X standing for Aerial, Underwater or Sea-surface—where the AXVs have to autonomously navigate themselves so as to construct an accurate map of the unknown area. Such a problem can be transformed into a dynamic optimization problem which, however, is NP-complete and thus infeasible to be solved. A usual attempt is to relax this problem by employing greedy (optimal one-step-ahead) solutions which may end-up quite problematic. In this paper, we first show that optimal one-step-ahead exploration schemes that are based on a transformed optimization criterion can lead to highly efficient solutions to the multi-AXV exploration. Such a transformed optimization criterion is constructed using both theoretical analysis and experimental investigations and attempts to minimize the “disturbing” effect of deadlocks and nonlinearities to the overall exploration scheme. As, however, optimal one-step-ahead solutions to the transformed optimization criterion cannot be practically obtained using conventional optimization schemes, the second step in our approach is to combine the use of the transformed optimization criterion with the cognitive adaptive optimization (CAO): CAO is a practicably feasible computational methodology which adaptively provides an accurate approximation of the optimal one-step-ahead solutions. The combination of the transformed optimization criterion with CAO results in a multi-AXV exploration scheme which is both practically implementable and provides with quite efficient solutions as it is shown both by theoretical analysis and, most importantly, by extensive simulation experiments and real-life underwater sea-floor mapping experiments in the Leixes port, Portugal.     

Toward infinite-horizon optimality in nonlinear model predictivecontrol

A new model predictive control scheme with guaranteed stability is presented for constrained discrete-time nonlinear systems. The open-loop optimization problem does not involve explicit terminal constraints, and employs a nonstandard terminal cost function. The closed-loop system is shown to be infinite-horizon optimal, provided that the terminal cost exactly captures the infinite-horizon optimal value in a neighborhood of the origin. Stability and optimality are proven for a set of initial states, which is invariant and approaches the set of all controllable states, as the prediction horizon increases     

Delay-optimal quorum consensus for distributed systems

Given a set of nodes S, a coterie is a set of pairwise intersecting subsets of S. Each element in a coterie is called a quorum. Mutual exclusion in a distributed system can be achieved if each request is required to gel consensus from a quorum of nodes. This technique of quorum consensus is also used for replicated distributed database systems, and bicoteries and wr-coteries have been defined to capture the requirements of read and write operations in user transactions. The author is interested in finding coteries, bicoteries, and wr-coteries with optimal communication delay. The protocols take into account the network topology. They design delay-optimal quorum consensus protocols for network topologies of trees, rings, and clustered networks     

A framework for the application of metaheuristics to?tasks-to-processors assignation problems

The optimization of the execution time of a parallel algorithm can be achieved through the use of an analytical cost model function representing the running time. Typically the cost function includes a set of parameters that model the behavior of the system and the algorithm. In order to reach an optimal execution, some of these parameters must be fitted according to the input problem and to the target architecture. An optimization problem can be stated where the modeled execution time for the algorithm is used to estimate the parameters. Due to the large number of variable parameters in the model, analytical minimization techniques are discarded. Exhaustive search techniques can be used to solve the optimization problem, but when the number of parameters or the size of the computational system increases, the method is impracticable due to time restrictions. The use of approximation methods to guide the search is also an alternative. However, the dependence on the algorithm modeled and the bad quality of the solutions as a result of the presence of many local optima values in the objective functions are also drawbacks to these techniques. The problem becomes particularly difficult in complex systems hosting a large number of heterogeneous processors solving non-trivial scientific applications. The use of metaheuristics allows for the development of valid approaches to solve general problems with a large number of parameters. A well-known advantage of metaheuristic methods is the ability to obtain high-quality solutions at low running times while maintaining generality. We propose combining the parameterized analytical cost model function and metaheuristic minimization methods, which contributes to a novel real alternative to minimize the parallel execution time in complex systems. The success of the proposed approach is shown with two different algorithmic schemes on parallel heterogeneous systems. Furthermore, the development of a general framework allows us to easily develop and experiment with different metaheuristics to adjust them to particular problems.     

Revisiting Multiple Pattern Matching Algorithms for Multi-Core Architecture

Due to the huge size of patterns to be searched,multiple pattern searching remains a challenge to several newly-arising applications like network intrusion detection.In this paper,we present an attempt to design efficient multiple pattern searching algorithms on multi-core architectures.We observe an important feature which indicates that the multiple pattern matching time mainly depends on the number and minimal length of patterns.The multi-core algorithm proposed in this paper leverages this feature to decompose pattern set so that the parallel execution time is minimized.We formulate the problem as an optimal decomposition and scheduling of a pattern set,then propose a heuristic algorithm,which takes advantage of dynamic programming and greedy algorithmic techniques,to solve the optimization problem.Experimental results suggest that our decomposition approach can increase the searching speed by more than 200% on a 4-core AMD Barcelona system.