Mobile Byzantine agreement on arbitrary network

Toru Sasaki, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita

Research output: Chapter in Book/Report/Conference proceedingConference contribution

18 Citations (Scopus)


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 languageEnglish
Title of host publicationPrinciples of Distributed Systems - 17th International Conference, OPODIS 2013, Proceedings
Number of pages15
Publication statusPublished - 2013
Event17th International Conference on Principles of Distributed Systems, OPODIS 2013 - Rouen, France
Duration: Dec 16 2013Dec 18 2013

Publication series

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


Other17th International Conference on Principles of Distributed Systems, OPODIS 2013

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Mobile Byzantine agreement on arbitrary network'. Together they form a unique fingerprint.

Cite this