Asynchronous Consensus in Synchronous Systems Using send_to_all Primitive

被引：0

作者：

Srinivasan S. ^{[1
]}

Ramesh K. ^{[2
]}

机构：

[1] Shiv Nadar University, Chennai

[2] National Institute of Technology, Warangal

来源：

SN Computer Science | / 4卷 / 6期

关键词：

Asynchronous algorithms; Consensus; Fault tolerance; send_to_all primitive;

D O I：

10.1007/s42979-023-02216-y

中图分类号：

学科分类号：

摘要：

Consensus is a fundamental agreement problem that arises when a set of distributed processes has to decide on a common value among their respective proposals. An asynchronous consensus algorithm is capable of preserving the safety property of consensus when the system is asynchronous and can solve consensus when the system is synchronous. Such algorithms are practical as modern distributed systems often experience some transient periods of asynchrony and it is essential that the system is safe during such periods. In this work, we consider systems that are capable of performing a broadcast operation in a single atomic step. Such systems can bypass the f+ 1 lower bound for achieving consensus in synchronous runs and allow consensus to be achieved in constant time by tolerating up to f failures. We construct an asynchronous consensus algorithm for such systems that tolerate up-to f=⌈n2-1⌉ process failures, where n is the size of the system. In synchronous runs of the system where δ is the upper bound for message delivery, our algorithm achieves consensus in 9 δ time in synchronous runs and 14 δ time in partial synchronous runs. © 2023, The Author(s), under exclusive licence to Springer Nature Singapore Pte Ltd.

引用

共 41 条

[1]

Pease M., Shostak R., Lamport L., Reaching agreement in the presence of faults, J ACM (JACM), 27, 2, pp. 228-234, (1980)

[2]

Fritzke U., Ingels P., Mostefaoui A., Raynal M., Fault-tolerant total order multicast to asynchronous groups, Proceedings Seventeenth IEEE Symposium on Reliable Distributed Systems (Cat. No. 98CB36281), pp. 228-234, (1998)

[3]

Guerraoui R., Schiper A., Total order multicast to multiple groups, Proceedings of 17Th International Conference on Distributed Computing Systems, pp. 578-585, (1997)

[4]

Pedone F., Schiper A., Generic broadcast, International Symposium on Distributed Computing, pp. 94-106, (1999)

[5]

Guerraoui R., Schiper A., The generic consensus service, IEEE Trans Softw Eng, 27, 1, pp. 29-41, (2001)

[6]

Hurfin M., Macedo R., Raynal M., Tronel F., A general framework to solve agreement problems, Proceedings of the 18Th IEEE Symposium on Reliable Distributed Systems, pp. 56-65, (1999)

[7]

Chandra T.D., Hadzilacos V., Toueg S., The weakest failure detector for solving consensus, J ACM (JACM), 43, 4, pp. 685-722, (1996)

[8]

Cachin C., Guerraoui R., Rodrigues L., Introduction to reliable and secure distributed programming, (2011)

[9]

Merritt M., (1985)

[10]

Lynch N.A., Distributed algorithms, (1996)

← 1 2 3 4 5 →