Broadcast using certified propagation algorithm in presence of Byzantine faults

Lewis Tseng; Nitin Vaidya; Vartika Bhandari

doi:10.1016/j.ipl.2014.11.010

Broadcast using certified propagation algorithm in presence of Byzantine faults

Lewis Tseng, Nitin Vaidya, Vartika Bhandari

Research output: Contribution to journal › Article › peer-review

Abstract

We explore the correctness of the Certified Propagation Algorithm (CPA) [6,1,8,5] in solving broadcast with locally bounded Byzantine faults. CPA allows the nodes to use only local information regarding the network topology. We provide a tight necessary and sufficient condition on the network topology for the correctness of CPA.

Original language	English (US)
Pages (from-to)	512-514
Number of pages	3
Journal	Information Processing Letters
Volume	115
Issue number	4
DOIs	https://doi.org/10.1016/j.ipl.2014.11.010
State	Published - Apr 2015
Externally published	Yes

Keywords

Byzantine broadcast
CPA
Distributed computing
Tight condition

ASJC Scopus subject areas

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Online availability

10.1016/j.ipl.2014.11.010

Library availability

Discover UIUC Full Text

Cite this

@article{05224731c7614d81b2c211d0fbbde653,

title = "Broadcast using certified propagation algorithm in presence of Byzantine faults",

abstract = "We explore the correctness of the Certified Propagation Algorithm (CPA) [6,1,8,5] in solving broadcast with locally bounded Byzantine faults. CPA allows the nodes to use only local information regarding the network topology. We provide a tight necessary and sufficient condition on the network topology for the correctness of CPA.",

keywords = "Byzantine broadcast, CPA, Distributed computing, Tight condition",

author = "Lewis Tseng and Nitin Vaidya and Vartika Bhandari",

note = "Funding Information: This research is supported in part by Army Research Office grant W-911-NF-0710287 . 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. Publisher Copyright: {\textcopyright} 2014 Elsevier B.V. All rights reserved.",

year = "2015",

month = apr,

doi = "10.1016/j.ipl.2014.11.010",

language = "English (US)",

volume = "115",

pages = "512--514",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "4",

}

TY - JOUR

T1 - Broadcast using certified propagation algorithm in presence of Byzantine faults

AU - Tseng, Lewis

AU - Vaidya, Nitin

AU - Bhandari, Vartika

N1 - Funding Information: This research is supported in part by Army Research Office grant W-911-NF-0710287 . 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. Publisher Copyright: © 2014 Elsevier B.V. All rights reserved.

PY - 2015/4

Y1 - 2015/4

N2 - We explore the correctness of the Certified Propagation Algorithm (CPA) [6,1,8,5] in solving broadcast with locally bounded Byzantine faults. CPA allows the nodes to use only local information regarding the network topology. We provide a tight necessary and sufficient condition on the network topology for the correctness of CPA.

AB - We explore the correctness of the Certified Propagation Algorithm (CPA) [6,1,8,5] in solving broadcast with locally bounded Byzantine faults. CPA allows the nodes to use only local information regarding the network topology. We provide a tight necessary and sufficient condition on the network topology for the correctness of CPA.

KW - Byzantine broadcast

KW - CPA

KW - Distributed computing

KW - Tight condition

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

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

U2 - 10.1016/j.ipl.2014.11.010

DO - 10.1016/j.ipl.2014.11.010

M3 - Article

AN - SCOPUS:84921056752

SN - 0020-0190

VL - 115

SP - 512

EP - 514

JO - Information Processing Letters

JF - Information Processing Letters

IS - 4

ER -

Broadcast using certified propagation algorithm in presence of Byzantine faults

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this