一种协调勘探和开采的遗传算法：收敛性及性能分析

提出了一种新的遗传算法结构。在该结构中,每一代的新种群由保留种 群、繁殖种群的随机种群三部分组成,而它们的相对数量则由不同的参数进行控制,这体现了该算法在运行过程中对搜索空间勘探和开采操作的协调和权衡。通过把该算法建模为齐次的有限Markov链,该文证明了该算法具有全局收敛性。对试验数据的分析表明,该算法能够有效协调算法对问题解空间的勘探和开采操作,因而在处理复杂问题时表现出较高的性能。     

A self-stabilizing algorithm for constructing weakly connected minimal dominating sets

This paper presents a new distributed self-stabilizing algorithm for the weakly connected minimal dominating set problem. It assumes a self-stabilizing algorithm to compute a breadth-first tree. Using an unfair distributed scheduler the algorithm stabilizes in at most O(nmA) moves, where A is the number of moves to construct a breadth-first tree. All previously known algorithms required an exponential number of moves.     

Analysis of a large number of Markov chains competing for transitions

We consider the behaviour of a stochastic system composed of several identically distributed, but non independent, discrete-time absorbing Markov chains competing at each instant for a transition. The competition consists in determining at each instant, using a given probability distribution, the only Markov chain allowed to make a transition. We analyse the first time at which one of the Markov chains reaches its absorbing state. When the number of Markov chains goes to infinity, we analyse the asymptotic behaviour of the system for an arbitrary probability mass function governing the competition. We give conditions that ensure the existence of the asymptotic distribution and we show how these results apply to cluster-based distributed storage when the competition is handled using a geometric distribution.     

Linear self-stabilizing algorithms for the independent and dominating set problems using an unfair distributed scheduler

This paper presents distributed self-stabilizing algorithms for the maximal independent and the minimal dominating set problems. Using an unfair distributed scheduler the algorithms stabilizes in at most max{3n−5,2n} resp. 9n moves. All previously known algorithms required O(n²) moves.     

On the propagation of updates in distributed replicated systems

We analyse the performance and dependability of protocols which implement ‘sequence consistency’ in distributed replicated systems. Sites send messages to each other from time to time, passing information about the update requests that have been received. The recipient of a message is chosen according to some probability distribution which may depend on the sender. The random variables of main interest are (a) the interval between receiving an update request and being able to execute it on the original site, subject to the consistency requirement, and (b) the time it takes to bring all sites to a consistent state after the arrival of an update.     

Frameworks for designing and implementing dependable systems using Coordinated Atomic Actions: A comparative study

This paper¹ presents ways of implementing dependable distributed applications designed using the Coordinated Atomic Action (CAA) paradigm. CAAs provide a coherent set of concepts adapted to fault tolerant distributed system design that includes structured transactions, distribution, cooperation, competition, and forward and backward error recovery mechanisms triggered by exceptions. DRIP (Dependable Remote Interacting Processes) is an efficient Java implementation framework which provides support for implementing Dependable Multiparty Interactions (DMI). As DMIs have a softer exception handling semantics compared with the CAA semantics, a CAA design can be implemented using the DRIP framework. A new framework called CAA-DRIP allows programmers to exclusively implement the semantics of CAAs using the same terminology and concepts at the design and implementation levels. The new framework not only simplifies the implementation phase, but also reduces the final system size as it requires less number of instances for creating a CAA at runtime. The paper analyses both implementation frameworks in great detail, drawing a systematic comparison of the two. The CAAs behaviour is described in terms of Statecharts to better understand the differences between the two frameworks. Based on the results of the comparison, we use one of the frameworks to implement a case study belonging to the e-health domain.     

A weakest failure detector-based asynchronous consensus protocol for f<n

has been shown to be the weakest realistic failure detector class needed to solve the consensus problem in an asynchronous distributed system prone to f<n process crashes in which communication is by message-passing. However, the only protocol that is known to meet this bound is based on three layers of protocol construction, and is therefore not efficient. This paper presents a surprisingly simple and very efficient direct message-passing implementation of a -based consensus protocol, and proves its correctness.     

Uniform metrical task systems with a limited number of states

We give a randomized algorithm (the “Wedge Algorithm”) of competitiveness for any metrical task system on a uniform space of k points, for any k?2, where , the kth harmonic number. This algorithm has better competitiveness than the Irani-Seiden algorithm if k is smaller than 10⁸. The algorithm is better by a factor of 2 if k<47.     

Low complexity Byzantine-resilient consensus

The application of the tolerance paradigm to security - intrusion tolerance - has been raising a reasonable amount of attention in the dependability and security communities. In this paper we present a novel approach to intrusion tolerance. The idea is to use privileged components - generically designated by wormholes - to support the execution of intrusion-tolerant protocols, often called Byzantine-resilient in the literature.The paper introduces the design of wormhole-aware intrusion-tolerant protocols using a classical distributed systems problem: consensus. The system where the consensus protocol runs is mostly asynchronous and can fail in an arbitrary way, except for the wormhole, which is secure and synchronous. Using the wormhole to execute a few critical steps, the protocol manages to have a low time complexity: in the best case, it runs in two rounds, even if some processes are malicious. The protocol also shows how often theoretical partial synchrony assumptions can be substantiated in practical distributed systems. The paper shows the significance of the TTCB as an engineering paradigm, since the protocol manages to be simple when compared with other protocols in the literature.Published online: 29 October 2004This work was partially supported by the EC, through project IST-1999-11583 (MAFTIA), and by the FCT, through the Large-Scale Informatic Systems Laboratory (LASIGE) and projects POSI/1999/CHS/33996 (DEFEATS) and POSI/CHS/39815/2001 (COPE).     

The inherent price of indulgence

An indulgent algorithm is a distributed algorithm that tolerates asynchronous periods of the network when process crash detection is unreliable. This paper presents a tight bound on the time complexity of indulgent consensus algorithms. We consider a round-based eventually synchronous model, and we show that any t-resilient consensus algorithm in this model, requires at least t+2 rounds for a global decision even in runs that are synchronous. We contrast our lower bound with the well-known t+1 round tight bound on consensus in the synchronous model. We then prove the bound to be tight by exhibiting a new t-resilient consensus algorithm in the eventually synchronous model that reaches a global decision at round t+2 in every synchronous run. Our new algorithm is in this sense significantly faster than the most efficient indulgent algorithm we know of, which requires 2t+2 rounds in synchronous runs. Our lower bound applies to round-based consensus algorithms with unreliable failure detectors such as ⋄ P and ⋄ S, and our matching algorithm can be adapted to such failure detectors. This work is partially supported by the Swiss National Science Foundation (project number 510-207).     

Lower bounds for asynchronous consensus

Impossibility results and best-case lower bounds are proved for the number of message delays and the number of processes required to reach agreement in an asynchronous consensus algorithm that tolerates non-Byzantine failures. General algorithms exist that achieve these lower bounds in the normal case, when the response time of non-faulty processes and the transmission delay of messages they send to one another are bounded. Our theorems allow algorithms to do better in certain exceptional cases, and such algorithms are presented. Two of these exceptional algorithms may be of practical interest.     

Fast Paxos

As used in practice, traditional consensus algorithms require three message delays before any process can learn the chosen value. Fast Paxos is an extension of the classic Paxos algorithm that allows the value to be learned in two message delays. How and why the algorithm works are explained informally, and a TLA⁺ specification of the algorithm appears as an appendix.     

遗传算法的平均收敛速度及其估计

给出了独立于表示的变异算子和交叉算子的数学描述, 建立了遗传算法种群的精确马尔可夫链模型, 导出了种群中最佳个体的马尔可夫链及其随机矩阵, 将遗传算法的平均收敛速度定义为最佳个体转移至吸收态的平均吸收时间的数学期望, 提出了应用最佳个体的随机矩阵估计遗传算法平均收敛速度的理论方法和计算步骤.     

The weakest failure detector to solve nonuniform consensus

We determine the weakest failure detector to solve nonuniform consensus in any environment, i.e., regardless of the number of faulty processes. Together with previous results, this closes all aspects of the following question: What is the weakest failure detector to solve (uniform or nonuniform) consensus in any environment?     

遗传算法的几乎必然强收敛性--鞅方法

遗传算法已有的收敛性的分析大都是在概率收敛意义下考虑的且基于算法的遍历性分析，这种敛性分析不确保算法在有限步内收敛到问题的全局最优解且所获得结果不仅对带“杰出者记录策略”的算法有效。该文首次尝试运用鞅论研究遗传算法的几乎必然强收敛性，证明一大类不带“杰出者记录策略”的遗传算法能以概率1确保在有限步内达到全局最优解，所获结果为遗传算法的实际应用奠定了理论基础，且所使用的鞅论分析方法为遗传算法研究提供了全新的分析工具。     

A framework for decentralised feedback connectivity control with application to sensor networks

In this article, we propose a decentralised algorithm for connectivity maintenance in a distributed sensor network. Our algorithm uses the dynamics of a consensus algorithm to estimate the connectivity of a network topology in a decentralised manner. These estimates are then used to inform a decentralised control algorithm that regulates the network connectivity to some desired level. Under certain realistic assumptions we show that the closed-loop dynamics can be described as a consensus algorithm with an input, and eventually reduces to a scalar system. Bounds are given to ensure the stability of the algorithm and examples are given to illustrate the efficacy of the proposed algorithm.     

有限级信息素蚁群算法

提出一种新的蚁群算法,将信息素分成有限个级别,通过级别的更新实现对信息素的更新,并且信息素的更新量独立于目标函数值. 文中采用有限马氏链的理论证明算法可以线性地收敛到全局最优解. 针对TSP问题,通过与MMAS和ACS等蚁群算法的数值实验结果进行比较,表明所提出的算法是有效的、鲁棒的.     

An Approximation Algorithm for the Fault Tolerant Metric Facility Location Problem

We consider a fault tolerant version of the metric facility location problem in which every city, j, is required to be connected to r _j facilities. We give the first non-trivial approximation algorithm for this problem, having an approximation guarantee of 3 · H _k , where k is the maximum requirement and H _k is the kth harmonic number. Our algorithm is along the lines of [2] for the generalized Steiner network problem. It runs in phases, and each phase, using a generalization of the primal–dual algorithm of [5] for the metric facility location problem, reduces the maximum residual requirement by one.     

Fast consensus in networks of bounded degree

Summary TheDistributed Consensus problem involvesn processors each of which holds an initial binary vlaue. At mostt of the processors may be faulty and ignore any protocol (even behaving maliciously), yet it is required that the non-faulty processors eventually agree on a value that was initially held by one of them. In this paper we focus on consensus in networks whose degree is bounded, following the work of Dwork, Peleg, Pippenger and Upfal [8]. In such a context, complete consensus among all the correct processors is not possible and some exceptions must be allowed. We first show how to achieve consensus in the butterfly network usingO(t+lognloglogn) one-bit parallel transmission steps, while tolerating the asymptotically optimal number of faulty processors (O(n/logn)) and having the asymptotically minimal number of exceptions (O(tlogt)). This result considerably improves on the running time of existing butterfly consensus protocols [2, 8]. In particular, it replaces the running time ofO(nlognloglogn) of [2] with an asymptotically optimal one. As in [8], we can then decrease the number of exceptions toO(t) by using additional links, while maintaining the same running time. The protocol is derived from a consensus protocol for completely connected networks that is interesting in its own right: it achieves Distributed Consensus with optimal number of processors, asymptotically optimal total bit transfer and nearly optimal number of rounds. Piotr Berman was born in 1955 in Warsaw, Poland, where here progressed from day-care to the degree of Master of Mathematics obtained from the University of Warsaw in 1978. He later studied at the Polish Academy of Sciences and MIT. He received a Ph.D. in Mathematics from MIT in 1985. From 1982 he has been teaching at Penn State, where currently he has a permanent position. His research interests are in two areas: fault-tolerant distributed computing and approximation algorithms. His non-professional hobbies include ancient history and mountain hiking. Juan Alberto Garay is originally from Rosario, Argentina, where he received his degree of Electrical Engineering from the Universidad Nacional de Rosario in 1976, at the age of 21. He then received his Master's degree in Electronic Engineering from the Eindhoven International Institute of the Eindhoven University of Technology (Eindhoven, Holland) in 1981, and his Ph.D. in Computer Science at Penn State University (University Park, PA) in 1989. Between his first and second degrees he worked as a digital design engineer for SOMISA (San Nicola's, Argentina), and between his second and Ph.D. degrees as a systems engineer for IBM Argentina. During the 1989/1990 academic year he was a visiting Assistant Professor at Bucknell University (Lewisburg, PA), and since 1990 he is with IBM's T.J. Watson Research Center (Yorktown Heights, NY). In 1992 he spent 6 months at The Weizmann Institute of Science (Rehovot, Israel) as a postdoctoral fellow. His professional interests include algorithms and lower bounds, distributed computation and fault tolerance. Dr. Garay enjoys tennis, music and philosophy.Preliminary version appeared in Proc 4th International Workshop on Distributed Algorithms, LNCS 486 (Springer-Verlag), pp 321–333, 1990