Mobile Byzantine agreement on arbitrary network

Toru Sasaki; Yukiko Yamauchi; Shuji Kijima; Masafumi Yamashita

doi:10.1007/978-3-319-03850-6_17

Mobile Byzantine agreement on arbitrary network

Toru Sasaki, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita

Mathematical Informatics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

18 Citations (Scopus)

Abstract

The mobile Byzantine agreement problem on general network is investigated for the first time. We first show that the problem is unsolvable on any network with the order n and the vertex connectivity d, if n ≤ 6t or d ≤ 4t, where t is an upper bound on the number of faulty processes. Assuming full synchronization and the existence of a permanently non-faulty process, we next propose two t-resilient mobile Byzantine agreement algorithms for some families of not fully connected networks. They are optimal on some networks, in the sense that they correctly work if n > 6t and d > 4t.

Original language	English
Title of host publication	Principles of Distributed Systems - 17th International Conference, OPODIS 2013, Proceedings
Pages	236-250
Number of pages	15
DOIs	https://doi.org/10.1007/978-3-319-03850-6_17
Publication status	Published - 2013
Event	17th International Conference on Principles of Distributed Systems, OPODIS 2013 - Rouen, France Duration: Dec 16 2013 → Dec 18 2013

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8304 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	17th International Conference on Principles of Distributed Systems, OPODIS 2013
Country/Territory	France
City	Rouen
Period	12/16/13 → 12/18/13

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-319-03850-6_17

Cite this

Sasaki, T., Yamauchi, Y., Kijima, S., & Yamashita, M. (2013). Mobile Byzantine agreement on arbitrary network. In Principles of Distributed Systems - 17th International Conference, OPODIS 2013, Proceedings (pp. 236-250). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8304 LNCS). https://doi.org/10.1007/978-3-319-03850-6_17

Mobile Byzantine agreement on arbitrary network. / Sasaki, Toru; Yamauchi, Yukiko; Kijima, Shuji et al.
Principles of Distributed Systems - 17th International Conference, OPODIS 2013, Proceedings. 2013. p. 236-250 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8304 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Sasaki, T, Yamauchi, Y, Kijima, S & Yamashita, M 2013, Mobile Byzantine agreement on arbitrary network. in Principles of Distributed Systems - 17th International Conference, OPODIS 2013, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8304 LNCS, pp. 236-250, 17th International Conference on Principles of Distributed Systems, OPODIS 2013, Rouen, France, 12/16/13. https://doi.org/10.1007/978-3-319-03850-6_17

Sasaki T, Yamauchi Y, Kijima S, Yamashita M. Mobile Byzantine agreement on arbitrary network. In Principles of Distributed Systems - 17th International Conference, OPODIS 2013, Proceedings. 2013. p. 236-250. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-03850-6_17

@inproceedings{beefa367d7834e79921151ad54148260,

title = "Mobile Byzantine agreement on arbitrary network",

abstract = "The mobile Byzantine agreement problem on general network is investigated for the first time. We first show that the problem is unsolvable on any network with the order n and the vertex connectivity d, if n ≤ 6t or d ≤ 4t, where t is an upper bound on the number of faulty processes. Assuming full synchronization and the existence of a permanently non-faulty process, we next propose two t-resilient mobile Byzantine agreement algorithms for some families of not fully connected networks. They are optimal on some networks, in the sense that they correctly work if n > 6t and d > 4t.",

author = "Toru Sasaki and Yukiko Yamauchi and Shuji Kijima and Masafumi Yamashita",

note = "Funding Information: This work is supported in part by JSPS KAKENHI (No. 22300004, No. 24650008, No. 23700019, and No. 24106005).; 17th International Conference on Principles of Distributed Systems, OPODIS 2013 ; Conference date: 16-12-2013 Through 18-12-2013",

year = "2013",

doi = "10.1007/978-3-319-03850-6_17",

language = "English",

isbn = "9783319038490",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "236--250",

booktitle = "Principles of Distributed Systems - 17th International Conference, OPODIS 2013, Proceedings",

}

TY - GEN

T1 - Mobile Byzantine agreement on arbitrary network

AU - Sasaki, Toru

AU - Yamauchi, Yukiko

AU - Kijima, Shuji

AU - Yamashita, Masafumi

N1 - Funding Information: This work is supported in part by JSPS KAKENHI (No. 22300004, No. 24650008, No. 23700019, and No. 24106005).

PY - 2013

Y1 - 2013

N2 - The mobile Byzantine agreement problem on general network is investigated for the first time. We first show that the problem is unsolvable on any network with the order n and the vertex connectivity d, if n ≤ 6t or d ≤ 4t, where t is an upper bound on the number of faulty processes. Assuming full synchronization and the existence of a permanently non-faulty process, we next propose two t-resilient mobile Byzantine agreement algorithms for some families of not fully connected networks. They are optimal on some networks, in the sense that they correctly work if n > 6t and d > 4t.

AB - The mobile Byzantine agreement problem on general network is investigated for the first time. We first show that the problem is unsolvable on any network with the order n and the vertex connectivity d, if n ≤ 6t or d ≤ 4t, where t is an upper bound on the number of faulty processes. Assuming full synchronization and the existence of a permanently non-faulty process, we next propose two t-resilient mobile Byzantine agreement algorithms for some families of not fully connected networks. They are optimal on some networks, in the sense that they correctly work if n > 6t and d > 4t.

UR - http://www.scopus.com/inward/record.url?scp=84893137242&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84893137242&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-03850-6_17

DO - 10.1007/978-3-319-03850-6_17

M3 - Conference contribution

AN - SCOPUS:84893137242

SN - 9783319038490

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 236

EP - 250

BT - Principles of Distributed Systems - 17th International Conference, OPODIS 2013, Proceedings

T2 - 17th International Conference on Principles of Distributed Systems, OPODIS 2013

Y2 - 16 December 2013 through 18 December 2013

ER -

Mobile Byzantine agreement on arbitrary network

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this