.一种分布式计算中的容错选举算法.pdf

TP 计算机研究与发展 ISSN1000—1239ICN11-1777I of Re．archand JournalComputer Development 一种分布式计算中的容错选举算法 赵致琢 黄小炜 吴文鑫 (厦门大学计算机科学系 厦门 361005) (zzzhao@XIntl．edu．cn) ANewFault-TolerantElection inDistributed Algorithm Computation Zhao WuWenxin Xiaowei，and Zhizhuo，Huang (Department Science，Xiamen 361005) ofComputer University，Xiamen ithas tobe Abstractelection are usedindistributed been harder algorithmswidely computing，andproved thantheconsensus this relationbetweentheelection andtheconsensus paper，the problem problem．In is a flewfault·tolerantelection is is problemanalysed，and algorithmgiven．Thisalgorithmstable， it cantoleratethe failureonthe andlinks．The communication-efficient，andtemporal processors not solvetheelection it also a new tosolvethe algorithmsproposedonly problem，andprovides way consensus problem． wordselection Key algorithm；fault—tolerant；distributedalgorithm；distributedcomputation 摘要选举算法被广泛应用于分布式计算中，而且它已经被证明比合意问题更难．在分析了选举问题 和合意问题的关系之后，提出了一种新的客错选举算法．该算法是稳定的、通信有效的，并且该算法可 以容忍进程和链路的暂时性错误．所提出的算法不仅解决了选举问题，并且也提供了解决合意问题的 一条新的途径． 关键词选举算法；容错；分布式算法；分布式计算 中图法分类号TP316．4 在分布式计算中，如何保证参与计算的进程之 位，出现了用故障检测器来解决选举问题的思路． 间的某种一致性是一个很重要的课题，而在分布式容 而文献[10]中提出的Q故障检测器由于其特殊定 错计算领域提出的合意问题【11(consensusproblem)正义可以被用做leader选择器，Q保证最终所有的正 是对解决这一课题在理论方法探索研究中提出的一 确进程都信任相同的进程并且该进程也是正确的． 个重要的概念．所谓合意问题就是如何在系统中使 在文献[11—1