Broadcast Using Certified Propagation Algorithm in Presence of Byzantine Faults

Abstract

We explore the correctness of the Certified Propagation Algorithm (CPA) [5, 1, 7, 4] 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. We also present some simple extensions of this result.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 20, 2012
Accession Number
ADA568117

Entities

People

  • Lewis Tseng
  • Nitin H. Vaidya
  • Vartika Bhandari

Organizations

  • University of Illinois Urbana–Champaign

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Agreements
  • Algorithms
  • Communication Channels
  • Communication Networks
  • Computer Science
  • Computers
  • Engineering
  • Illinois
  • Information Operations
  • Network Topology
  • Networks
  • Specifications
  • Standards
  • Topology
  • Universities

Fields of Study

  • Computer science

Readers

  • Computer Networking
  • Graph Algorithms and Convex Optimization.
  • Software Engineering.