基于重复数的最短循环请求集生成算法

在分布式循环请求集长度最短时,针对请求集生成算法的时间复杂度和空间复杂度过高问题,提出了一种基于重复数的最短循环请求集生成算法。算法在基于循环松弛差集的思想上,以当前请求集差集允许的最大重复数作为判断条件,依次向请求集中添加元素。实验结果表明,系统节点数为70到90时,该算法在保证请求集长度最短,且空间复杂度为O(2N)的前提下,使得时间复杂度是穷搜方法的3.6E-03到6.8E-07,降低了最短循环请求集生成算法的时间复杂度。     

一种高效能的分布式请求集生成算法

分布式互斥请求集的长度、对称性和生成的难易程度以及生成算法占用的空间及耗费的时间直接影响着基于该请求集的分布式互斥算法的消息复杂度、对称性和算法的应用规模。本文在折半循环编码算法的基础上,提出了一种增加算法初始化节点数量和引入松弛差集的对称分布式互斥请求集生成算法,使算法的时间复杂度和消息复杂度大幅度降低。     

基于差集的高效能分布式请求集生成算法

在折半循环编码算法的基础上,提出了一种增加算法初始化节点数量和松弛正向差集的对称分布式互斥请求集生成算法,使算法的时间复杂度大幅度降低,而所生成的请求集长度仍然保持（2N）^1/2～2N^1/2之间。     

频繁项集挖掘算法

在松弛循环差集的基础上,依据局部贪心策略对可纳入节点以局部求优的方式来生成请求集的算法,使算法的时间复杂度降低一个数量级,同时所生成的请求集长度仍然保持在2N2N,从而更有利于在通信中推广使用。     

改进的分布式互斥请求集生成算法

在分布式系统中,各节点必须互斥地访问临界区.节点的请求集的长度决定了系统的效率、性能.虽然最优请求集的节点数最少(大约n),但已有的解决方案该类问题算法类似于穷举法,随着节点的增加,该方法变得不可计算.提出了一种快速的请求集生成算法,该算法以循环差集请求集生成算法的理论和贪心算法的基本思想为基础,在每次迭代的过程中,选出一个当前条件下最优的节点加入请求集.与其他的方法相比较,该方法能对任意给定的整数快速、有效地生成对称的请求集.本算法时间复杂度为O(n2),生成的请求集长度为n～2n.     

基因组Translocation排序问题的改进多项式算法

该文给出基因组Transhocation排序问题的一个改进多项式算法，原算法所有存储空间O（n)，时间复杂度为O(n^3)，文中改进算法仍采用O(n)存储空间，时间复杂度为O(n^2logn),具体地，将计算Translocation距离的时间复杂度由O(n^3)改进为O(n^2),将计算Translocation序列的时间复杂度由O(n^3)改进为O(n^2logn).     

有向基因组移位排序问题的O(n2)快速算法

有向基因组移位排序问题在计算生物学研究中占有重要位置．以前最好的算法时间复杂度为O(n^2logn)．该文给出一个有向基因组移位排序的新多项式算法，将移位排序的时间复杂度改进为O(n^2)．算法改进的关键在于找到一种寻找有效合理移位的新方法，通过在最小子排列中删除无关顶点确定一个合理移位是否有效，从而将寻找一个有效移位的时间复杂度改进为O(n)，总时间复杂度由此降为O(n^2)．     

一种新的分布式互斥请求集生成算法

分布式互斥请求集的长度、对称性和生成的难易程度以及生成算法占用的空间及耗费的时间直接影响着基于该请求集的分布式互斥算法的消息复杂度、对称性和算法的应用规模。本文在基于循环编码的分布式互斥请求集生成算法的基础上,提出了一种增加算法初始化节点数量的对称分布式互斥请求集生成算法。其生成的请求集长度小于2N0.5,其时间复杂度也比基于循环编码的分布式互斥请求集生成算法小。因此,该算法较已有的分布式互斥请求集生成算法在性能上具有较大提高。     

基于实时逻辑的时间约束检测方法

本文针对具有严格时间要求的系统,阐述并分析了三种利用实时逻辑实现时间约束检测的方法。第一种方法通过检测系统规范和安全性断言的一致性来验证约束的满足性,非常适合于系统规范的设计与可满足性检测,算法的时间复杂度是O(n^2) O(n^2) O(2^k)。第二种方法利用实时逻辑与约束图的方法实现运行时的时间约束检测,但检测时的系统约束条件不够第三种方法简约,算法时间复杂度为O(n^2),改进之后为O(n^2)。第三种方法通过对约束图的处理,减少运行时系统检测的约束条件,从而减少运行时的时间约束条件的搜索时间,算法的时间复杂度为O(n),在实时性和检测效率明显优于前两种方法。但需要运行前优化约束规则,将会增加额外的时间和空间复杂度。     

基于局部递归的动态多点初始化请求集生成算法

如何在保证请求集长度不显著增加的情况下使时间复杂度尽量减小,是对称分布式互斥请求集生成算法研究者必须解决的问题。通过动态增加初始化节点的方法,采用局部递归的方式设计了一种新的对称分布式互斥请求集生成算法。该算法能够保证请求集长度与其长度下限比较不会显著增加,而时间复杂度比WK算法及全局递归算法有显著下降。因此,通过对请求集本身特性的研究,能够部分解决请求集长度与请求集生成算法时间复杂度之间的矛盾。     

Refined quorum systems

It is considered good distributed computing practice to devise object implementations that tolerate contention, periods of asynchrony and a large number of failures, but perform fast if few failures occur, the system is synchronous and there is no contention. This paper initiates the first study of quorum systems that help design such implementations by encompassing, at the same time, optimal resilience, as well as optimal best-case complexity. We introduce the notion of a refined quorum system (RQS) of some set S as a set of three classes of subsets (quorums) of S: first class quorums are also second class quorums, themselves being also third class quorums. First class quorums have large intersections with all other quorums, second class quorums typically have smaller intersections with those of the third class, the latter simply correspond to traditional quorums. Intuitively, under uncontended and synchronous conditions, a distributed object implementation would expedite an operation if a quorum of the first class is accessed, then degrade gracefully depending on whether a quorum of the second or the third class is accessed. Our notion of refined quorum system is devised assuming a general adversary structure, and this basically allows algorithms relying on refined quorum systems to relax the assumption of independent process failures, often questioned in practice. We illustrate the power of refined quorums by introducing two new optimal Byzantine-resilient distributed object implementations: an atomic storage and a consensus algorithm. Both match previously established resilience and best-case complexity lower bounds, closing open gaps, as well as new complexity bounds we establish here. Each of our algorithms is representative of a different class of architectures, highlighting the generality of the refined quorum abstraction.     

A Token-Based Distributed Group Mutual Exclusion Algorithm with Quorums

The group mutual exclusion problem is a generalization of mutual exclusion problem such that a set of processes in the same group can enter critical section simultaneously. In this paper, we propose a distributed algorithm for the group mutual exclusion problem in asynchronous message passing distributed systems. Our algorithm is based on tokens, and a process that obtains a token can enter critical section. For reducing message complexity, it uses coterie as a communication structure when a process sends a request messages. Informally, coterie is a set of quorums, each of which is a subset of the process set, and any two quorums share at least one process. The message complexity of our algorithm is $O(|Q|)$ in the worst case, where $|Q|$ is a quorum size that the algorithm adopts. Performance of the proposed algorithm is presented by analysis and discrete event simulation. Especially, the proposed algorithm achieves high concurrency, which is a performance measure for the number of processes that can be in critical section simultaneously.     

Synchronous Byzantine quorum systems

Summary. Quorum systems have been used to implement many coordination problems in distributed systems such as mutual exclusion, data replication, distributed consensus, and commit protocols. Malkhi and Reiter recently proposed quorum systems that can tolerate Byzantine failures; they called these systems Byzantine quorum systems and gave some examples of such quorum systems. In this paper, we propose a new definition of Byzantine quorums that is appropriate for synchronous systems. We show how these quorums can be used for data replication and propose a general construction of synchronous Byzantine quorums using standard quorum systems. We prove tight lower bounds on the load of synchronous Byzantine quorums for various patterns of failures and we present synchronous Byzantine quorums that have optimal loads that match the lower bounds for two failure patterns. Received: June 1998 / Accepted: August 1999     

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     

Average Case Analysis of Gosper’s Algorithm for a Class of Urn Model Inputs

In this paper we perform an asymptotic average case analysis of some of the most important steps of Gosper’s algorithm for indefinite summation of hypergeometric terms. The space of input functions of the algorithm is described in terms of urn models, and the analysis is performed by using specialized probabilistic transform techniques. We analyze two different types of urn model classes: one in which the input functions are assumed to be rational, and another for which a certain function of two inputs is assumed to be rational. The first set of results shows that the asymptotic complexity of the algorithm is the same within each of the two classes. The second set of results indicates that the complexity of the algorithm scales differently for the two classes of models: one can observe the logarithmic versus square root type of difference that is also present in other combinatorial models.     

WDOP‐based Summation Inequality and its Application to Exponential Stability of Linear Delay Difference Systems

This paper is concerned with the exponential stability analysis of linear delay difference systems. Firstly, a set of weighted discrete orthogonal polynomials (WDOPs) is established by using the Gram‐Schmidt orthogonalization process, and then two WDOPs‐based summation inequalities, including some existing summation inequalities as special cases, are developed. Secondly, these WDOPs‐based summation inequalities are applied to investigate the exponential stability criteria and explicit exponential estimates of solutions of linear delay difference systems. Finally, two numerical examples indicate that the proposed WDOPs‐based approach can derive the exponential stability condition with larger decay rate than the existing ones.     

基于Quorum系统容错技术综述

Quorum系统是一种新型冗余拓扑的集合系统。在“冗余”设计的基础上，quorum通过交叉的结点把有效数据复制到其他quorum的结点中，增加了Quorum系统数据冗余性。当某些结点发生故障或者错误时，通过选举协议，从含有故障结点quorum的有效结点中选举出有效数据；或者采用互斥协议，从不含故障或者错误结点的有效quorum的结点中获得有效数据，系统仍能可靠运行。分析了各种Quorum肌系统的容错方式、性能比较，探讨了Quorum系统发展中需要改进的关键问题，并展望了未来的研究方向。     

A self-stabilizing quorum-based protocol for maxima computing

The goal of decentralized consensus protocols is to exchange information among nodes so that each node acquires the information held by every other node in the system. This paper presents a quorum-based, self-stabilizing maxima finding protocol which is based on a decentralized consensus protocol. The protocol exchanges information with less delay than existing ring-based, self-stablizing protocols. Furthermore, quorums can be composed, and the resulting composite quorums can be used to efficiently obtain a solution for any internetwork. Received: October 1999 / Accepted: June 2001