Optimizing Gossiping for Asynchronous Fault-Prone IoT Networks With Memory and Battery Constraints

Abstract

A gossip protocol is a procedure by which a device disseminates its rumor to all devices on a network. The traditional definition of the gossip problem states that, in a system with $n$ interconnected devices where each of them only knows initially its own rumor, after a known finite time of message exchange, all devices learn the $n$ rumors. This definition considers synchronous systems where devices cannot fail. Gossip-based protocols can be very useful in Internet of Things (IoT) networks as a means of disseminating information. Thus, we have reformulated the problem to expand the spectrum of networks in which the gossip technique can be applied, including asynchrony and device failures, very common features in current IoT newtwoks. Gossiping consumes valuable memory and battery resources in devices. This can be particularly problematic for small IoT devices that operate with reduced memory in remote or inaccessible locations, where battery replacement or recharging is difficult. To address these issues, two efficient gossip protocols are presented, so that the efficiency and longevity of IoT devices is not compromised. The first protocol (battery-efficient protocol) allows to reduce battery consumption while still having a good time performance, but needs quadratic memory, like traditional versions. The second protocol (memory-optimal protocol) only needs linear memory to store and manage the rumors, and is capable of significantly reducing the number of messages sent, while obtaining similar (or, in many cases, better) performance than the first protocol. Both protocols are formally proved to be correct, and upper and lower limits of their number of messages sent are determined. These theoretical limits, however, differ so much among them that they do not permit to guess the number of messages that a real case may require. Hence, the practical performance of both protocols is assessed with experiments.

Keywords

• Gossip protocols
• crash failures
• IoT networks
• partial-knowledge of membership
• unknown maximum number of failures
• reliable links