Computer Science

Reliable broadcast with trusted nodes: Energy reduction, resilience, and speed

Document Type

Article

Abstract

Broadcast is an important primitive in large-scale distributed systems. One application is to enable reliable and efficient communication in large-scale networks such as sensor networks and Internet-of-Things. There is a rich study on achieving reliable broadcast under various kind of failures. In this paper, we use the notion of “trust” to improve the performance of reliable broadcast. We focus on Certified Propagation Algorithm (CPA), one of the simple algorithms that does not rely on a cryptographic infrastructure and has a proven guarantee on resilience (number of node failures tolerated). Specifically, the paper has two main contributions: (i) A new algorithm Trust-CPA – which integrates CPA with trusted nodes – has been proposed and shown to increase the resilience from the original CPA, and (ii) Natural optimization problems related to Trust-CPA have been proposed and studied as well. First, we study the location to place trusted nodes to reduce power consumption while maintaining the same level of resilience. Second, we study two optimizations problems on finding out which set of nodes to “trustify” to increase resilience and reduce speed. For the speed-related optimization problem, we present a greedy heuristic algorithm, and its efficacy has been examined using simulation. We show that our algorithm performs relatively well in geometric random graphs, an appropriate model for large-scale wireless sensor networks.

Publication Title

Computer Networks

Publication Date

2020

Volume

182

ISSN

1389-1286

DOI

10.1016/j.comnet.2020.107486

Keywords

Certified Propagation Algorithm, hardness result, reliable broadcast, tight condition, trust

APA Citation

Tseng, L., Wu, Y., Pan, H., Aloqaily, M., & Boukerche, A. (2020). Reliable broadcast with trusted nodes: Energy reduction, resilience, and speed. Computer Networks, 182, 107486.

Link to Full Text

Share

COinS