Reliable broadcast with trusted nodes: Energy reduction, resilience, and speed
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.