Brief Announcement: Reaching Approximate Consensus When Everyone May Crash

Tseng, Lewis; Zhang, Qinzi; Zhang, Yifan

doi:10.4230/LIPIcs.DISC.2020.53

File

LIPIcs.DISC.2020.53.pdf

Filesize: 368 kB
3 pages

Document Identifiers

DOI: 10.4230/LIPIcs.DISC.2020.53
URN: urn:nbn:de:0030-drops-131319

Author Details

Lewis Tseng

Boston College, Chestnut Hill, MA, USA

Qinzi Zhang

Boston College, Chestnut Hill, MA, USA

Yifan Zhang

Boston College, Chestnut Hill, MA, USA

Cite AsGet BibTex

Lewis Tseng, Qinzi Zhang, and Yifan Zhang. Brief Announcement: Reaching Approximate Consensus When Everyone May Crash. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 53:1-53:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.DISC.2020.53

Abstract

Fault-tolerant consensus is of great importance in distributed systems. This paper studies the asynchronous approximate consensus problem in the crash-recovery model with fair-loss links. In our model, up to f nodes may crash forever, while the rest may crash intermittently. Each node is equipped with a limited-size persistent storage that does not lose data when crashed. We present an algorithm that only stores three values in persistent storage - state, phase index, and a counter.

Subject Classification

ACM Subject Classification

Theory of computation → Distributed algorithms

Keywords

Approximate Consensus
Fair-loss Channel
Crash-recovery

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

References

I. Abraham, Y. Amit, and D. Dolev. Optimal resilience asynchronous approximate agreement. In International Conference On Principles Of Distributed Systems, volume 3544, pages 229-239, December 2004. URL: https://doi.org/10.1007/11516798_17.
M. Aguilera, W. Chen, and S. Toueg. Failure detection and consensus in the crash-recovery model. Distributed Computing, 13:99-125, April 2000. URL: https://doi.org/10.1007/s004460050070.
D. Dolev, N. A. Lynch, S. S. Pinter, E. W. Stark, and W. E. Weihl. Reaching approximate agreement in the presence of faults. J. ACM, 33:499-516, May 1986.
M. Hurfi, A. Mostéfaoui, and M. Raynal. Consensus in asynchronous systems where processes can crash and recover. In Proceedings of the The 17th IEEE Symposium on Reliable Distributed Systems, SRDS ’98, page 280, USA, 1998. IEEE Computer Society.
R. Oliveira, R. Guerraoui, and A. Schiper. Consensus in the crash-recover model. In Technical Report. École Polytechnique Fédérale de Lausanne, 1997.
D. Sakavalas and L. Tseng. Network Topology and Fault-Tolerant Consensus, volume 9. Morgan & Claypool, May 2019. URL: https://doi.org/10.2200/S00918ED1V01Y201904DCT016.
L. Tseng, Q. Zhang, and Y. Zhang. Reach approximate consensus when everyone may crash. In Technical Report. Boston College, 2020.