Prioritized-MVBA: A New Approach to Design an Optimal Asynchronous Byzantine Agreement Protocol Article Swipe
Nasit S Sony
,
Xianzhong Ding
,
Mukesh Singhal
·
YOU?
·
· 2024
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2406.03739
YOU?
·
· 2024
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2406.03739
The multi-valued byzantine agreement protocol (MVBA) in the authenticated setting has been widely used as a core to design atomic broadcast and fault-tolerant state machine replication protocols in asynchronous networks. Originating from the seminal work of Cachin et al. \cite{CACHIN01}, subsequent research endeavors have sought to optimize protocol efficiency in terms of communication complexity. Notable advancements following Cachin's contributions include: i) VABA \cite{BYZ17}, requiring multiple protocol instances to achieve agreement on a party's request, and ii) Dumbo-MVBA \cite{LU20}, employing a cryptographic asynchronous dispersal and recovery methods to manage communication complexity alongside additional computational and communication rounds overheads. Our objective is to devise an MVBA protocol that achieves agreement in each instance without extra computation and communication rounds while maintaining the optimal metrics. Central to our design approach is the introduction of the committee in the classic MVBA protocol, wherein a randomly selected subset of ($f+1$, where $n=3f+1$) parties get selected and simultaneously broadcast their requests (transactions) to gather verifiable proofs. Successive distributions of these proofs afford us the necessary properties to employ the asynchronous binary Byzantine agreement (ABBA) protocol for reaching an agreement on a selected party's requests. By integrating the committee and ABBA protocols, we devise the optimal MVBA protocol, termed pMVBA (Prioritized-MVBA). This protocol exhibits resilience to tolerate up to $\lfloor \frac{n}{3}\rfloor$ Byzantine failures, with an expected runtime of $O(1)$, optimal message complexity of $O(n^2)$, and optimal communication complexity $O((l+λ)n^2)$ .
Related Topics
Concepts
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- http://arxiv.org/abs/2406.03739
- https://arxiv.org/pdf/2406.03739
- OA Status
- green
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4399454147
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4399454147Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.48550/arxiv.2406.03739Digital Object Identifier
- Title
-
Prioritized-MVBA: A New Approach to Design an Optimal Asynchronous Byzantine Agreement ProtocolWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2024Year of publication
- Publication date
-
2024-06-06Full publication date if available
- Authors
-
Nasit S Sony, Xianzhong Ding, Mukesh SinghalList of authors in order
- Landing page
-
https://arxiv.org/abs/2406.03739Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/2406.03739Direct link to full text PDF
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://arxiv.org/pdf/2406.03739Direct OA link when available
- Concepts
-
Asynchronous communication, Byzantine architecture, Protocol (science), Computer science, Computer network, History, Ancient history, Medicine, Pathology, Alternative medicineTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
0Total citation count in OpenAlex
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W4399454147 |
|---|---|
| doi | https://doi.org/10.48550/arxiv.2406.03739 |
| ids.doi | https://doi.org/10.48550/arxiv.2406.03739 |
| ids.openalex | https://openalex.org/W4399454147 |
| fwci | |
| type | preprint |
| title | Prioritized-MVBA: A New Approach to Design an Optimal Asynchronous Byzantine Agreement Protocol |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T10772 |
| topics[0].field.id | https://openalex.org/fields/17 |
| topics[0].field.display_name | Computer Science |
| topics[0].score | 0.907800018787384 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/1705 |
| topics[0].subfield.display_name | Computer Networks and Communications |
| topics[0].display_name | Distributed systems and fault tolerance |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C151319957 |
| concepts[0].level | 2 |
| concepts[0].score | 0.7671301364898682 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q752739 |
| concepts[0].display_name | Asynchronous communication |
| concepts[1].id | https://openalex.org/C104562893 |
| concepts[1].level | 2 |
| concepts[1].score | 0.7557392716407776 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q47591 |
| concepts[1].display_name | Byzantine architecture |
| concepts[2].id | https://openalex.org/C2780385302 |
| concepts[2].level | 3 |
| concepts[2].score | 0.7326816916465759 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q367158 |
| concepts[2].display_name | Protocol (science) |
| concepts[3].id | https://openalex.org/C41008148 |
| concepts[3].level | 0 |
| concepts[3].score | 0.5994324684143066 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[3].display_name | Computer science |
| concepts[4].id | https://openalex.org/C31258907 |
| concepts[4].level | 1 |
| concepts[4].score | 0.21298304200172424 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q1301371 |
| concepts[4].display_name | Computer network |
| concepts[5].id | https://openalex.org/C95457728 |
| concepts[5].level | 0 |
| concepts[5].score | 0.07666563987731934 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q309 |
| concepts[5].display_name | History |
| concepts[6].id | https://openalex.org/C195244886 |
| concepts[6].level | 1 |
| concepts[6].score | 0.07403862476348877 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q41493 |
| concepts[6].display_name | Ancient history |
| concepts[7].id | https://openalex.org/C71924100 |
| concepts[7].level | 0 |
| concepts[7].score | 0.05882343649864197 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q11190 |
| concepts[7].display_name | Medicine |
| concepts[8].id | https://openalex.org/C142724271 |
| concepts[8].level | 1 |
| concepts[8].score | 0.0 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q7208 |
| concepts[8].display_name | Pathology |
| concepts[9].id | https://openalex.org/C204787440 |
| concepts[9].level | 2 |
| concepts[9].score | 0.0 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q188504 |
| concepts[9].display_name | Alternative medicine |
| keywords[0].id | https://openalex.org/keywords/asynchronous-communication |
| keywords[0].score | 0.7671301364898682 |
| keywords[0].display_name | Asynchronous communication |
| keywords[1].id | https://openalex.org/keywords/byzantine-architecture |
| keywords[1].score | 0.7557392716407776 |
| keywords[1].display_name | Byzantine architecture |
| keywords[2].id | https://openalex.org/keywords/protocol |
| keywords[2].score | 0.7326816916465759 |
| keywords[2].display_name | Protocol (science) |
| keywords[3].id | https://openalex.org/keywords/computer-science |
| keywords[3].score | 0.5994324684143066 |
| keywords[3].display_name | Computer science |
| keywords[4].id | https://openalex.org/keywords/computer-network |
| keywords[4].score | 0.21298304200172424 |
| keywords[4].display_name | Computer network |
| keywords[5].id | https://openalex.org/keywords/history |
| keywords[5].score | 0.07666563987731934 |
| keywords[5].display_name | History |
| keywords[6].id | https://openalex.org/keywords/ancient-history |
| keywords[6].score | 0.07403862476348877 |
| keywords[6].display_name | Ancient history |
| keywords[7].id | https://openalex.org/keywords/medicine |
| keywords[7].score | 0.05882343649864197 |
| keywords[7].display_name | Medicine |
| language | en |
| locations[0].id | pmh:oai:arXiv.org:2406.03739 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4306400194 |
| locations[0].source.issn | |
| locations[0].source.type | repository |
| locations[0].source.is_oa | True |
| locations[0].source.issn_l | |
| locations[0].source.is_core | False |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | arXiv (Cornell University) |
| locations[0].source.host_organization | https://openalex.org/I205783295 |
| locations[0].source.host_organization_name | Cornell University |
| locations[0].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[0].license | |
| locations[0].pdf_url | https://arxiv.org/pdf/2406.03739 |
| locations[0].version | submittedVersion |
| locations[0].raw_type | text |
| locations[0].license_id | |
| locations[0].is_accepted | False |
| locations[0].is_published | False |
| locations[0].raw_source_name | |
| locations[0].landing_page_url | http://arxiv.org/abs/2406.03739 |
| locations[1].id | doi:10.48550/arxiv.2406.03739 |
| locations[1].is_oa | True |
| locations[1].source.id | https://openalex.org/S4306400194 |
| locations[1].source.issn | |
| locations[1].source.type | repository |
| locations[1].source.is_oa | True |
| locations[1].source.issn_l | |
| locations[1].source.is_core | False |
| locations[1].source.is_in_doaj | False |
| locations[1].source.display_name | arXiv (Cornell University) |
| locations[1].source.host_organization | https://openalex.org/I205783295 |
| locations[1].source.host_organization_name | Cornell University |
| locations[1].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[1].license | |
| locations[1].pdf_url | |
| locations[1].version | |
| locations[1].raw_type | article |
| locations[1].license_id | |
| locations[1].is_accepted | False |
| locations[1].is_published | |
| locations[1].raw_source_name | |
| locations[1].landing_page_url | https://doi.org/10.48550/arxiv.2406.03739 |
| indexed_in | arxiv, datacite |
| authorships[0].author.id | https://openalex.org/A5099057003 |
| authorships[0].author.orcid | |
| authorships[0].author.display_name | Nasit S Sony |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Sony, Nasit S |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5108940900 |
| authorships[1].author.orcid | |
| authorships[1].author.display_name | Xianzhong Ding |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Ding, Xianzhong |
| authorships[1].is_corresponding | False |
| authorships[2].author.id | https://openalex.org/A5058282709 |
| authorships[2].author.orcid | https://orcid.org/0000-0002-0497-1942 |
| authorships[2].author.display_name | Mukesh Singhal |
| authorships[2].author_position | last |
| authorships[2].raw_author_name | Singhal, Mukesh |
| authorships[2].is_corresponding | False |
| has_content.pdf | False |
| has_content.grobid_xml | False |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://arxiv.org/pdf/2406.03739 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2024-06-08T00:00:00 |
| display_name | Prioritized-MVBA: A New Approach to Design an Optimal Asynchronous Byzantine Agreement Protocol |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T06:51:31.235846 |
| primary_topic.id | https://openalex.org/T10772 |
| primary_topic.field.id | https://openalex.org/fields/17 |
| primary_topic.field.display_name | Computer Science |
| primary_topic.score | 0.907800018787384 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/1705 |
| primary_topic.subfield.display_name | Computer Networks and Communications |
| primary_topic.display_name | Distributed systems and fault tolerance |
| related_works | https://openalex.org/W4391375266, https://openalex.org/W2748952813, https://openalex.org/W635625959, https://openalex.org/W1548189724, https://openalex.org/W4242769984, https://openalex.org/W2034320198, https://openalex.org/W4252331942, https://openalex.org/W4386477301, https://openalex.org/W4220997590, https://openalex.org/W2763042189 |
| cited_by_count | 0 |
| locations_count | 2 |
| best_oa_location.id | pmh:oai:arXiv.org:2406.03739 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4306400194 |
| best_oa_location.source.issn | |
| best_oa_location.source.type | repository |
| best_oa_location.source.is_oa | True |
| best_oa_location.source.issn_l | |
| best_oa_location.source.is_core | False |
| best_oa_location.source.is_in_doaj | False |
| best_oa_location.source.display_name | arXiv (Cornell University) |
| best_oa_location.source.host_organization | https://openalex.org/I205783295 |
| best_oa_location.source.host_organization_name | Cornell University |
| best_oa_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| best_oa_location.license | |
| best_oa_location.pdf_url | https://arxiv.org/pdf/2406.03739 |
| best_oa_location.version | submittedVersion |
| best_oa_location.raw_type | text |
| best_oa_location.license_id | |
| best_oa_location.is_accepted | False |
| best_oa_location.is_published | False |
| best_oa_location.raw_source_name | |
| best_oa_location.landing_page_url | http://arxiv.org/abs/2406.03739 |
| primary_location.id | pmh:oai:arXiv.org:2406.03739 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4306400194 |
| primary_location.source.issn | |
| primary_location.source.type | repository |
| primary_location.source.is_oa | True |
| primary_location.source.issn_l | |
| primary_location.source.is_core | False |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | arXiv (Cornell University) |
| primary_location.source.host_organization | https://openalex.org/I205783295 |
| primary_location.source.host_organization_name | Cornell University |
| primary_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| primary_location.license | |
| primary_location.pdf_url | https://arxiv.org/pdf/2406.03739 |
| primary_location.version | submittedVersion |
| primary_location.raw_type | text |
| primary_location.license_id | |
| primary_location.is_accepted | False |
| primary_location.is_published | False |
| primary_location.raw_source_name | |
| primary_location.landing_page_url | http://arxiv.org/abs/2406.03739 |
| publication_date | 2024-06-06 |
| publication_year | 2024 |
| referenced_works_count | 0 |
| abstract_inverted_index.. | 232 |
| abstract_inverted_index.a | 15, 71, 79, 139, 184 |
| abstract_inverted_index.By | 188 |
| abstract_inverted_index.an | 102, 181, 217 |
| abstract_inverted_index.as | 14 |
| abstract_inverted_index.et | 37 |
| abstract_inverted_index.i) | 60 |
| abstract_inverted_index.in | 6, 27, 49, 108, 133 |
| abstract_inverted_index.is | 99, 127 |
| abstract_inverted_index.of | 35, 51, 130, 143, 162, 220, 225 |
| abstract_inverted_index.on | 70, 183 |
| abstract_inverted_index.to | 17, 45, 67, 86, 100, 123, 156, 170, 208, 211 |
| abstract_inverted_index.up | 210 |
| abstract_inverted_index.us | 166 |
| abstract_inverted_index.we | 195 |
| abstract_inverted_index.Our | 97 |
| abstract_inverted_index.The | 0 |
| abstract_inverted_index.al. | 38 |
| abstract_inverted_index.and | 21, 74, 83, 93, 114, 150, 192, 227 |
| abstract_inverted_index.for | 179 |
| abstract_inverted_index.get | 148 |
| abstract_inverted_index.has | 10 |
| abstract_inverted_index.ii) | 75 |
| abstract_inverted_index.our | 124 |
| abstract_inverted_index.the | 7, 32, 119, 128, 131, 134, 167, 172, 190, 197 |
| abstract_inverted_index.ABBA | 193 |
| abstract_inverted_index.MVBA | 103, 136, 199 |
| abstract_inverted_index.This | 204 |
| abstract_inverted_index.VABA | 61 |
| abstract_inverted_index.been | 11 |
| abstract_inverted_index.core | 16 |
| abstract_inverted_index.each | 109 |
| abstract_inverted_index.from | 31 |
| abstract_inverted_index.have | 43 |
| abstract_inverted_index.that | 105 |
| abstract_inverted_index.used | 13 |
| abstract_inverted_index.with | 216 |
| abstract_inverted_index.work | 34 |
| abstract_inverted_index.extra | 112 |
| abstract_inverted_index.pMVBA | 202 |
| abstract_inverted_index.state | 23 |
| abstract_inverted_index.terms | 50 |
| abstract_inverted_index.their | 153 |
| abstract_inverted_index.these | 163 |
| abstract_inverted_index.where | 145 |
| abstract_inverted_index.while | 117 |
| abstract_inverted_index.(ABBA) | 177 |
| abstract_inverted_index.(MVBA) | 5 |
| abstract_inverted_index.Cachin | 36 |
| abstract_inverted_index.afford | 165 |
| abstract_inverted_index.atomic | 19 |
| abstract_inverted_index.binary | 174 |
| abstract_inverted_index.design | 18, 125 |
| abstract_inverted_index.devise | 101, 196 |
| abstract_inverted_index.employ | 171 |
| abstract_inverted_index.gather | 157 |
| abstract_inverted_index.manage | 87 |
| abstract_inverted_index.proofs | 164 |
| abstract_inverted_index.rounds | 95, 116 |
| abstract_inverted_index.sought | 44 |
| abstract_inverted_index.subset | 142 |
| abstract_inverted_index.termed | 201 |
| abstract_inverted_index.widely | 12 |
| abstract_inverted_index.$O(1)$, | 221 |
| abstract_inverted_index.($f+1$, | 144 |
| abstract_inverted_index.Central | 122 |
| abstract_inverted_index.Notable | 54 |
| abstract_inverted_index.achieve | 68 |
| abstract_inverted_index.classic | 135 |
| abstract_inverted_index.machine | 24 |
| abstract_inverted_index.message | 223 |
| abstract_inverted_index.methods | 85 |
| abstract_inverted_index.optimal | 120, 198, 222, 228 |
| abstract_inverted_index.parties | 147 |
| abstract_inverted_index.party's | 72, 186 |
| abstract_inverted_index.proofs. | 159 |
| abstract_inverted_index.runtime | 219 |
| abstract_inverted_index.seminal | 33 |
| abstract_inverted_index.setting | 9 |
| abstract_inverted_index.wherein | 138 |
| abstract_inverted_index.without | 111 |
| abstract_inverted_index.$\lfloor | 212 |
| abstract_inverted_index.Cachin's | 57 |
| abstract_inverted_index.achieves | 106 |
| abstract_inverted_index.approach | 126 |
| abstract_inverted_index.exhibits | 206 |
| abstract_inverted_index.expected | 218 |
| abstract_inverted_index.include: | 59 |
| abstract_inverted_index.instance | 110 |
| abstract_inverted_index.metrics. | 121 |
| abstract_inverted_index.multiple | 64 |
| abstract_inverted_index.optimize | 46 |
| abstract_inverted_index.protocol | 4, 47, 65, 104, 178, 205 |
| abstract_inverted_index.randomly | 140 |
| abstract_inverted_index.reaching | 180 |
| abstract_inverted_index.recovery | 84 |
| abstract_inverted_index.request, | 73 |
| abstract_inverted_index.requests | 154 |
| abstract_inverted_index.research | 41 |
| abstract_inverted_index.selected | 141, 149, 185 |
| abstract_inverted_index.tolerate | 209 |
| abstract_inverted_index.$O(n^2)$, | 226 |
| abstract_inverted_index.$n=3f+1$) | 146 |
| abstract_inverted_index.Byzantine | 175, 214 |
| abstract_inverted_index.agreement | 3, 69, 107, 176, 182 |
| abstract_inverted_index.alongside | 90 |
| abstract_inverted_index.broadcast | 20, 152 |
| abstract_inverted_index.byzantine | 2 |
| abstract_inverted_index.committee | 132, 191 |
| abstract_inverted_index.dispersal | 82 |
| abstract_inverted_index.employing | 78 |
| abstract_inverted_index.endeavors | 42 |
| abstract_inverted_index.failures, | 215 |
| abstract_inverted_index.following | 56 |
| abstract_inverted_index.instances | 66 |
| abstract_inverted_index.necessary | 168 |
| abstract_inverted_index.networks. | 29 |
| abstract_inverted_index.objective | 98 |
| abstract_inverted_index.protocol, | 137, 200 |
| abstract_inverted_index.protocols | 26 |
| abstract_inverted_index.requests. | 187 |
| abstract_inverted_index.requiring | 63 |
| abstract_inverted_index.Dumbo-MVBA | 76 |
| abstract_inverted_index.Successive | 160 |
| abstract_inverted_index.additional | 91 |
| abstract_inverted_index.complexity | 89, 224, 230 |
| abstract_inverted_index.efficiency | 48 |
| abstract_inverted_index.overheads. | 96 |
| abstract_inverted_index.properties | 169 |
| abstract_inverted_index.protocols, | 194 |
| abstract_inverted_index.resilience | 207 |
| abstract_inverted_index.subsequent | 40 |
| abstract_inverted_index.verifiable | 158 |
| abstract_inverted_index.Originating | 30 |
| abstract_inverted_index.complexity. | 53 |
| abstract_inverted_index.computation | 113 |
| abstract_inverted_index.integrating | 189 |
| abstract_inverted_index.maintaining | 118 |
| abstract_inverted_index.replication | 25 |
| abstract_inverted_index.\cite{LU20}, | 77 |
| abstract_inverted_index.advancements | 55 |
| abstract_inverted_index.asynchronous | 28, 81, 173 |
| abstract_inverted_index.introduction | 129 |
| abstract_inverted_index.multi-valued | 1 |
| abstract_inverted_index.\cite{BYZ17}, | 62 |
| abstract_inverted_index.authenticated | 8 |
| abstract_inverted_index.communication | 52, 88, 94, 115, 229 |
| abstract_inverted_index.computational | 92 |
| abstract_inverted_index.contributions | 58 |
| abstract_inverted_index.cryptographic | 80 |
| abstract_inverted_index.distributions | 161 |
| abstract_inverted_index.$O((l+λ)n^2)$ | 231 |
| abstract_inverted_index.(transactions) | 155 |
| abstract_inverted_index.fault-tolerant | 22 |
| abstract_inverted_index.simultaneously | 151 |
| abstract_inverted_index.\cite{CACHIN01}, | 39 |
| abstract_inverted_index.(Prioritized-MVBA). | 203 |
| abstract_inverted_index.\frac{n}{3}\rfloor$ | 213 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 3 |
| citation_normalized_percentile |