2011/10/17 by Haotian Zhang, Zhang, Haotian, Shreyas Sundaram +1 · 4 citations
Computer Science · Engineering · #Advanced Memory and Neural Computing #Distributed #Distributed Control Multi-Agent Systems #FOS: Computer and information sciences #FOS: Electrical engineering #FOS: Mathematics #FOS: Physical sciences #Multiagent Systems (cs.MA) #Opportunistic and Delay-Tolerant Networks #Optimization and Control (math.OC) #Parallel #Physics and Society (physics.soc-ph) #Social and Information Networks (cs.SI) #Systems and Control (eess.SY) #and Cluster Computing (cs.DC) #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.1110.3843
openalex publication_date 2011/10/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the problem of diffusing information in networks that contain malicious nodes. We assume that each normal node in the network has no knowledge of the network topology other than an upper bound on the number of malicious nodes in its neighborhood. We introduce a topological property known as r-robustness of a graph, and show that this property provides improved bounds on tolerating malicious behavior, in comparison to traditional concepts such as connectivity and minimum degree. We use this topological property to analyze the canonical problems of distributed consensus and broadcasting, and provide sufficient conditions for these operations to succeed. Finally, we provide a construction for r-robust graphs and show that the common preferential-attachment model for scale-free networks produces a robust graph.