Brief Announcement: Effects of Topology Knowledge and Relay Depth on Asynchronous Consensus
AuthorsDimitris Sakavalas,Lewis Tseng,Nitin H. Vaidya
- Part of: Volume:32nd International Symposium on Distributed Computing (DISC 2018)
Part of: Series:Leibniz International Proceedings in Informatics (LIPIcs)
Part of: Conference:International Symposium on Distributed Computing (DISC) - License:
Creative Commons Attribution 3.0 Unported license - Publication Date: 2018-10-04
File
LIPIcs.DISC.2018.51.pdf
- Filesize: 336 kB
- 4 pages
Document Identifiers
Author Details
Funding
- Vaidya, Nitin H.: This research is supported in part by National Science Foundation awards 1421918. Any opinions, findings, and conclusions or recommendations expressed here are those of the authors and do not necessarily reflect the views of the funding agencies or the U.S. government.
Cite AsGet BibTex
Dimitris Sakavalas, Lewis Tseng, and Nitin H. Vaidya. Brief Announcement: Effects of Topology Knowledge and Relay Depth on Asynchronous Consensus. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 51:1-51:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)https://doi.org/10.4230/LIPIcs.DISC.2018.51
Abstract
Consider an asynchronous incomplete directed network. We study the feasibility and efficiency of approximate crash-tolerant consensus under different restrictions on topology knowledge and relay depth, i.e., the maximum number of hops any message can be relayed.
Subject Classification
ACM Subject Classification
- Computer systems organization → Fault-tolerant network topologies
Keywords
- Asynchrony
- crash fault
- consensus
- topology knowledge
- relay
Metrics
- Access Statistics
- Total Accesses (updated on a weekly basis)0PDF Downloads0Metadata Views
Related Versions
References
- Eduardo A. P. Alchieri, Alysson Neves Bessani, Joni da Silva Fraga, and Fabíola Greve. Byzantine consensus with unknown participants. In OPODIS 2008, volume 5401 of LNCS, pages 22-40. Springer, 2008. URL:http://dx.doi.org/10.1007/978-3-540-92221-6_4.
- Danny Dolev. The Byzantine generals strike again. Journal of Algorithms, 3(1), 1982.
- Danny Dolev, Nancy A. Lynch, Shlomit S. Pinter, Eugene W. Stark, and William E. Weihl. Reaching approximate agreement in the presence of faults. J. ACM, 33(3):499-516, 1986. URL:http://dx.doi.org/10.1145/5925.5931.
- M. Pease, R. Shostak, and L. Lamport. Reaching agreement in the presence of faults. J. ACM, 27(2):228-234, 1980. URL:http://dx.doi.org/10.1145/322186.322188.
- Dimitris Sakavalas, Lewis Tseng, and Nitin H. Vaidya. Effects of topology knowledge and relay depth on asynchronous consensus. CoRR, abs/1803.04513, 2018. URL:http://arxiv.org/abs/1803.04513.
- Lili Su and Nitin Vaidya. Reaching approximate Byzantine consensus with multi-hop communication. In SSS 2015, volume 9212 of LNCS, pages 21-35. Springer, 2015. URL:http://dx.doi.org/10.1007/978-3-319-21741-3_2.
- Lewis Tseng and Nitin H. Vaidya. Fault-tolerant consensus in directed graphs. In PODC '15, pages 451-460. ACM, 2015. URL:http://dx.doi.org/10.1145/2767386.2767399.