ASYNCHRONOUS FAULT-TOLERANT TOTAL ORDERING ALGORITHMS

作     者：MOSER, LE MELLIARSMITH, PM AGRAWALA, V 

作者机构：SIEMENS CORP RESPRINCETONNJ 08540 

出 版 物：《SIAM JOURNAL ON COMPUTING》 (工业与应用数学会计算杂志)

年 卷 期：1993年第22卷第4期

页      面：727-750页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：DISTRIBUTED COMPUTING FAULT TOLERANCE ASYNCHRONISM PROBABILISTIC ALGORITHM PARTIAL ORDER TOTAL ORDER 

摘      要：Two novel efficient algorithms for placing a total order on messages in an asynchronous fault-tolerant distributed system are presented. The algorithms are resilient to fewer than n/3 and n/2 faulty processes in an n-process system. Partial correctness and probabilistic termination are demonstrated;it is also shown that there does not exist a total ordering algorithm that is guaranteed to terminate. A comparison of the complexity of the algorithms is given.