Search

In this work we present a new framework for the analysis and design of randomized gossip algorithms for solving the average consensus problem. We show how classical randomized iterative methods for solving linear systems can be interpreted as gossip algorithms when applied to special systems encoding the underlying network and explain in detail their decentralized nature. Our general framework recovers a comprehensive array of well-known gossip algorithms as special cases, including the pairwise randomized gossip algorithm and path averaging gossip, and allows for the development of provably faster variants. The flexibility of the new approach enables the design of a number of new specific gossip methods. For instance, we propose and analyze novel block and the first provably accelerated randomized gossip protocols, and dual randomized gossip algorithms. From a numerical analysis viewpoint, our work is the first that explores in depth the decentralized nature of randomized iterative methods for linear systems and proposes them as methods for solving the average consensus problem. We evaluate the performance of the proposed gossip protocols by performing extensive experimental testing on typical wireless network topologies., Comment: 44 pages, 12 figures

Designing distributed, fast and reliable wireless consensus protocols is instrumental in enabling mission-critical decentralized systems, such as robotic networks in the industrial Internet of Things (IIoT), drone swarms in rescue missions, and so forth. However, chasing both low-latency and reliability of consensus protocols is a challenging task. The problem is aggravated under wireless connectivity that may be slower and less reliable, compared to wired connections. To tackle this issue, we investigate fundamental relationships between consensus latency and reliability through the lens of wireless connectivity, and co-design communication and consensus protocols for low-latency and reliable decentralized systems. Specifically, we propose a novel communication-efficient distributed consensus protocol, termed Random Representative Consensus (R2C), and show its effectiveness under gossip and broadcast communication protocols. To this end, we derive a closed-form end-to-end (E2E) latency expression of the R2C that guarantees a target reliability, and compare it with a baseline consensus protocol, referred to as Referendum Consensus (RC). The result shows that the R2C is faster compared to the RC and more reliable compared when co-designed with the broadcast protocol compared to that with the gossip protocol., 30 pages, 8 figures, to appear in IEEE Internet of Things Journal

Part 6: Large-Scale Decentralised Systems; International audience; Gossip protocols form the basis of many smart collective adaptive systems. They are a class of fully decentralised, simple but robust protocols for the distribution of information throughout large scale networks with hundreds or thousands of nodes. Mean field analysis methods have made it possible to approximate and analyse performance aspects of such large scale protocols in an efficient way that is independent of the number of nodes in the network. Taking the gossip shuffle protocol as a benchmark, we evaluate a recently developed refined mean field approach. We illustrate the gain in accuracy this can provide for the analysis of medium size models analysing two key performance measures: replication and coverage. We also show that refined mean field analysis requires special attention to correctly capture the coordination aspects of the gossip shuffle protocol.

Gossip-based consensus protocols have been recently proposed to confront the challenges faced by state machine replication in large geographically distributed systems. It is unclear, however, to which extent consensus and gossip communication fit together. On the one hand, gossip communication has been shown to scale to large settings and efficiently handle participant failures and message losses. On the other hand, gossip may slow down consensus. Moreover, gossip's inherent redundancy may be unnecessary since consensus naturally accounts for participant failures and message losses. This paper investigates the suitability of gossip as a communication building block for consensus. We answer three questions: How much overhead does classic gossip introduce in consensus? Can we design consensus-friendly gossip protocols? Would more efficient gossip protocols still maintain the same reliability properties of classic gossip?

A source node forwards fresh status updates as a point process to a network of observer nodes. Within the network of observers, these updates are forwarded as point processes from node to node. Each node wishes its knowledge of the source to be as timely as possible. In this network, timeliness at each node is measured by an age of information metric: how old is the timestamp of the freshest received update. This work extends a method for evaluating the average age at each node in the network when nodes forward updates using a memoryless gossip protocol. This method is then demonstrated by age analysis for a simple network.

This study develops a gossip-based distributed hierarchical algorithm to solve the constrained convex optimisation problem over a multi-cluster network. Different from the existing works with incremental communication approach, a gossip protocol is applied to achieve inter-cluster information exchange. At each iteration, only two neighbour clusters are randomly woken up to exchange their new updates while others keep their latest information, which relaxes the restrictions on the inter-cluster communication topology. Technically, to investigate the intra-cluster consensus, a new analysing approach is exploited and some different techniques including the non-expansiveness of projection operator and the supermartingale convergence results are employed, based on which it is proved that estimates of all agents in the multi-cluster network jointly converge to the optimal solution with probability one. A numerical example on constrained lasso regression is provided to validate the theoretical results.

During the most up-to-date decade, we've seen an upheaval in network among PCs, and a future change in perspective from concentrated to exceptionally disseminated frameworks. Tattle and tree-based conglomeration calculations are two famous answers for circulated averaging in remote systems. The final uses just neighborhood message trades and requires no steering structures while the final requires accumulating a spreading over tree. We give conditions under which this course of action of action is ensured to mix to an agreement arrangement, where all hubs have an identical restricting qualities, on any firmly associated coordinated diagram. Tattle conventions will in most cases be utilized in settings where in actuality the scale and the dynamism of the fundamental correspondence organize make the choice of customary correspondence conventions very strange. In this educational article, we initially present a gathering of tattle conventions for data dissemination, and we offer an expository model to examine their execution in relation to speed and nature of the dispersion. We at that time present three samples of tattle based conventions that tackle likely the absolute most different issues, in particular participation the board, accumulation and overlay topology development.

A source node updates its status as a point process and also forwards its updates to a network of observer nodes. Within the network of observers, these updates are forwarded as point processes from node to node. Each node wishes its knowledge of the source to be as timely as possible. In this network, timeliness is measured by a discrete form of age of information: each status change at the source is referred to as a version and the age at a node is how many versions out of date is its most recent update from the source. This work introduces a method for evaluating the average version age at each node in the network when nodes forward updates using a memoryless gossip protocol. This method is then demonstrated by version age analysis for a collection of simple networks. For gossip on a complete graph with symmetric updating rates, it is shown that each node has average age that grows as the logarithm of the network size., Submitted to ISIT 2021

P2P networks along with the other distributed systems need to satisfy the strict requirement of efficiency in terms of the information propagation process. Fast message transmission affects the whole network functionality which includes data processing, attacks robustness, topology changes, etc. In this paper we consider the most wide-spread gossip-based network protocols, explore and compare several approaches to improve the information dissemination model. We describe the Neo blockchain network protocol which extends gossip algorithms for message propagation over the P2P network. Based on the imitation modelling results, we build a network protocol model of the Neo blockchain and evaluate the Neo network protocol efficiency in terms of reactive message processing in several scenarios, propose protocol enhancements and evaluate resulting performance gain.

International audience; Gossip describes the spread of information throughout a network of agents. It investigates how agents, each starting with a unique secret, can efficiently make peer-to-peer calls so that ultimately everyone knows all secrets. In Dynamic Gossip, agents share phone numbers in addition to secrets, which allows the network to grow at run-time. Most gossip protocols assume that all agents are reliable, but this is not given for many practical applications. We drop this assumption and study Dynamic Gossip with unreliable agents. The aim is then for agents to learn all secrets of the reliable agents and to identify the unreliable agents. We show that with unreliable agents classic results on Dynamic Gossip no longer hold. Specifically, the Learn New Secrets protocol is no longer characterised by the same class of graphs, so-called sun graphs. In addition, we show that unreliable agents that do not initiate communication are harder to identify than agents that do. This has paradoxical consequences for measures against unreliability, for example to combat the spread of fake news in social networks.

Improving performance of blockchain systems is one of the principal research interests in the field. While many efforts are being made to produce faster and more efficient consensus protocols, they are all constrained by a common factor: the time it takes for a block to propagate through the network. Most blockchain networks use different variations of gossip-like communication protocols to be able to send large messages whilst minimizing latency and bandwidth use. Unfortunately, it still supposes a major bottleneck for state-of-the-art high-performance blockchain systems.In this paper we analyze the most relevant work being done to improve message propagation in blockchain networks. More specifically, we introduce the problem of neighbour selection for gossip protocols, and we propose an alternative method to pick neighbours based on weights derived from self-collected metrics. Our technical performance study shows that the proposed method can suppose an improvement of up to 5 seconds. Additionally, in combination with the use of erasure coding techniques, we are capable of achieving a 75% reduction of the overall block propagation time.

In Wireless Sensor Networks (WSN), typically composed of nodes with resource constraints, leveraging efficient processes is crucial to enhance the network lifetime and, consequently, the sustainability in ultra-dense and heterogeneous environments, such as smart cities. Particularly, balancing the energy required to transport data efficiently across such dynamic environments poses significant challenges to routing protocol design and operation, being the trade-off of reducing data redundancy while achieving an acceptable delivery rate a fundamental research topic. In this way, this work proposes a new energy-aware epidemic protocol that uses the current state of the network energy to create a dynamic distribution topology by self-adjusting each node forwarding behavior as eager or lazy according to the local residual battery. Simulated evaluations demonstrate its efficiency in energy consumption, delivery rate, and reduced computational burden when compared with classical gossip protocols as well as with a directional protocol., FCT -Fundação para a Ciência e a Tecnologia(UIDB/50014/2020)

Gossip protocols aim at arriving, by means of point-to-point or group communications, at a situation in which all the agents know each other secrets. Recently a number of authors studied distributed epistemic gossip protocols. These protocols use as guards formulas from a simple epistemic logic, which makes their analysis and verification substantially easier. We study here common knowledge in the context of such a logic. First, we analyze when it can be reduced to iterated knowledge. Then we show that the semantics and truth for formulas without nested common knowledge operator are decidable. This implies that implementability, partial correctness and termination of distributed epistemic gossip protocols that use non-nested common knowledge operator is decidable, as well. Given that common knowledge is equivalent to an infinite conjunction of nested knowledge, these results are non-trivial generalizations of the corresponding decidability results for the original epistemic logic, established in (Apt & Wojtczak, 2016). K. R. Apt & D. Wojtczak (2016): On Decidability of a Logic of Gossips. In Proc. of JELIA 2016, pp. 18-33, doi:10.1007/ 978-3-319-48758-8_2., In Proceedings TARK 2017, arXiv:1707.08250

Distributed computation of average consensus is an important function in numerous wireless sensor networks and ad-hoc networks applications. In light of the severe resource constraints characterizing these embedded networked systems, it is of paramount importance the design of effective algorithms with low computational, communication, and energy requirements. Randomized gossip are a category of network algorithms that entail communication and information exchange among nodes selected with probabilistic mechanisms. They are considered attractive solutions for solving consensus problems because of their decentralized nature, conceptual simplicity, and capability of adapting to structural network modifications. However, the number of iterations needed by randomized gossip to converge towards consensus is an issue to be addressed to reduce latency and to limit the impact of the algorithm on the lifetime of battery operated devices. Solutions to the problem have been proposed that make use of localization and greedy geographic routing to build overlay graphs on top of a randomized gossip protocol, thus enabling information averaging among non-neighbor nodes and accelerating convergence. The main drawback of this type of approach is that each node is required to know its position, which is not always affordable in terms of costs or not even possible because of the lack of GPS signal. In this article we propose a novel approach to the consensus averaging problem based on a random walk mechanism to identify nodes involved in a computation round, and on a path averaging technique to update more than two nodes into the same round. The resulting algorithm doesn’t rely on any positioning mechanism. Experimental results provide evidence of the improved performance of the proposed method with respect to standard randomized gossip, with considerable gain in terms of convergence speed.

In this paper, we present an effective and efficient Byzantine-resilient dual membership management technique in cloud environments, in which nodes are prone to churn and the network topology is not fully connected. Our method is based on unstructured message communication model, namely a gossip protocol that is able to handle the dynamic behavior of nodes properly in the system. We argue that due to the presence of malicious Byzantine nodes, existing membership management mechanisms are not suitable for preserving uniformity of random sampling. Therefore, we propose a new membership management mechanism using gossip with social membership information. The proposed membership management scheme maintains not only neighbor nodes in a social graph, but also Byzantine nodes in a local data structure. The results show that our dual membership management effectively deals with Byzantine nodes, requiring only n$$\ge $$ź 2f + 1, where n is the number of nodes and f is the number of Byzantine nodes in the system. The message complexity is reduced from O(n$$^{2}$$2) to O(n) with our proposed algorithm compared to broadcast-based algorithms.

A gossip protocol is a procedure for spreading secrets among a group of agents, using a connection graph. In each call between a pair of connected agents, the two agents share all the secrets they have learnt. In dynamic gossip problems, dynamic connection graphs are enabled by permitting agents to spread as well the telephone numbers of other agents they know. This paper characterizes different distributed epistemic protocols in terms of the (largest) class of graphs where each protocol is successful, i.e. where the protocol necessarily ends up with all agents knowing all secrets.

Permissioned blockchains are supported by identified but individually untrustworthy nodes, collectively maintaining a replicated ledger whose content is trusted. The Hyperledger Fabric permissioned blockchain system targets high-throughput transaction processing. Fabric uses a set of nodes tasked with the ordering of transactions using consensus. Additional peers endorse and validate transactions, and maintain a copy of the ledger. The ability to quickly disseminate new transaction blocks from ordering nodes to all peers is critical for both performance and consistency. Broadcast is handled by a gossip protocol, using randomized exchanges of blocks between peers. We show that the current implementation of gossip in Fabric leads to heavy tail distributions of block propagation latencies, impacting performance, consistency, and fairness. We contribute a novel design for gossip in Fabric that simultaneously optimizes propagation time, tail latency and bandwidth consumption. Using a 100-node cluster, we show that our enhanced gossip allows the dissemination of blocks to all peers more than 10 times faster than with the original implementation, while decreasing the overall network bandwidth consumption by more than 40%. With a high throughput and concurrent application, this results in 17% to 36% fewer invalidated transactions for different block sizes., Comment: To appear in IEEE ICDCS 2020, copyright is with IEEE

Gossip problem is an information dissemination problem in which networked agents (nodes) must share their secrets by the minimum number of calls. In recent years, to solve the problem, various epistemic gossip protocols have been proposed, where the agents decide who to call based on the higher-order knowledge about the possession of secrets. Although most previous studies on the epistemic gossip protocol have restricted their scope to the environments including only reliable agents, from the practical viewpoint, it is worthwhile investigating robust protocols against agent failure. In this paper, we assume the existence of unreliable agents and analyze the robustness of some existing protocols using epistemic logic. In our model, when an agent fails, it loses the secrets and telephone numbers gained by previous calls and returns to its initial state. In addition, during each call, agents share not only their possessing secrets but also the history of the transmission path of each secret. For these settings, we show that the protocols ANY and PIG are successful (i.e., the protocols always lead to the state where every agent knows all secrets). We also show that the protocol CO is not immediately successful under the assumption that agents can fail, but it becomes successful if the protocol execution satisfies some conditions. Furthermore, we clarify sufficient conditions for agents to detect the failure of other agent, which are useful for designing robust protocols.

Novel machine learning techniques apply decentralized model training in order to mitigate data volume and privacy issues. Current approaches assume (a) node performance homogeneity, and (b) simultaneous training. These assumptions also imply that the predictive performance of the distributed models evolves uniformly. A different approach is required since a distributed decentralized network is heterogeneous and nonstationary: nodes can join or leave the network at any point in time (churn). We propose a novel protocol for exchanging the model knowledge between peers using a gossip algorithm combined with the stochastic gradient descent (SGD). Our method has the advantage of being fully asynchronous, decentralized, trustless, and independent of the network size and the churn ratio. We validated the proposed algorithm by running network simulations in various scenarios.

Decentralized solutions are emerging as promising candidates to overcome the privacy risks associated with centralized data services. Such solutions suffer however from their own range of privacy vulnerabilities, arising from untrusted and malicious peers. In this paper, we consider the emblematic problem of privacy-preserving decentralized averaging, and propose a novel gossip protocol that exchanges noise for several rounds before starting to exchange actual data. This makes it hard for an honest but curious attacker to know whether a user is transmitting noise or actual data. Our protocol and analysis do not assume a lock-step execution, and demonstrate improved resilience to colluding attackers. We prove the correctness of this protocol as well as several privacy results. Finally, we provide simulation results about the efficiency of our averaging protocol.

Gossip protocols are programs used in a setting in which each agent holds a secret and the aim is to reach a situation in which all agents know all secrets. Such protocols rely on a point-to-point or group communication. Distributed epistemic gossip protocols use epistemic formulas in the component programs for the agents. The advantage of the use of epistemic logic is that the resulting protocols are very concise and amenable for a simple verification. Recently, we introduced a natural modal logic that allows one to express distributed epistemic gossip protocols and to reason about their correctness. We proved that the resulting protocols are implementable and that all aspects of their correctness, including termination, are decidable. To establish these results we showed that both the definition of semantics and of truth of the underlying logic are decidable. We also showed that the analogous results hold for an extension of this logic with the 'common knowledge' operator. However, several, often deceptively simple, questions about this logic and the corresponding gossip protocols remain open. The purpose of this paper is to list and elucidate these questions and provide for them an appropriate background information in the form of partial of related results., In Proceedings TARK 2019, arXiv:1907.08335

Network connectivity policies dictate network communication between virtual instances in a cloud networking environment. Any change to these policies needs to be deterministic (a version of policy needs to be uniformly applied across the network), time-bound (needs to be completed or rolled back in case of failures within a defined SLA) and fail-safe against erroneous policies (application of a faulty policy should not block all communication across the network). Network partitions, inter-geographic network latencies, hardware failures and operator errors pose major challenges to continuous policy update propagation in a deterministic, time-bound and fail-safe manner. In this paper, we describe a new system for controlled propagation of service configurations across large networks called NEFERION. Neferion provides deterministic guarantees in face of network partitions, host server and/or controller downtime by employing gossip membership protocol across the network nodes for local ascertainment of cluster state.

In this work we present novel provably accelerated gossip algorithms for solving the average consensus problem. The proposed protocols are inspired from the recently developed accelerated variants of the randomized Kaczmarz method - a popular method for solving linear systems. In each gossip iteration all nodes of the network update their values but only a pair of them exchange their private information. Numerical experiments on popular wireless sensor networks showing the benefits of our protocols are also presented.

International audience; The last decade has witnessed of a rising surge interest in Gossip protocols in distributed systems. In particular, as soon as there is a need to disseminate events, they become a key functional building block due to their scalability, robustness and fault tolerance under high churn. However, Gossip protocols are known to be bandwidth intensive. A huge amount of algorithms has been studied to limit the number of exchanged messages using different combination of push/pull approaches. We are revisiting the state of the art by applying Random Linear Network Coding to further increase performances. In particular, the originality of our approach is to combine sparse vector encoding to send our network coding coefficients and Lamport timestamps to split messages in generations in order to provide an efficient gossiping. Our results demonstrate that we are able to drastically reduce the bandwidth overhead and the delay compared to the state ofthe art.

In peer-to-peer networks, each node directly connects to other nodes without access points. This type of network system is useful for information sharing by using mobile devices (e.g., smartphones). Although it is easy to construct an ad-hoc network, there are several problems, for instance, the management of the network under node churn. On message delivery over the network, it might be difficult to assume the static routing if the structure of the network can be changed frequently by node churn and link failures. In this paper, we evaluate the message reachability by gossip protocols on random geometric graphs under link instability. Specifically, we focus on the distribution of link failures on the network. The result shows that the link instability caused by nodes’ churn has a significant impact on the message reachability compared to a uniform link instability.

Cloud computing offers computational, storage, and applications capabilities as subscription oriented services. It offers a platform explore computational assets and use them based on "pay per use arrangement". Thus it opens ways to access boundless assets with negligible equipment and programming at the customers' end. This paper focuses on the advancement of a cloud administration's provisioning structure by building up a dynamic load-balancer for the cloud. It proposes a framework and protocol for the resource environment in the cloud. Distributed Hash Table (DHT) protocol has been utilized for a service query to perform a job agreed by the user. For load balancing, gossip protocol has been used for inter/intra-cluster gossip. For inter-cluster gossip, the load is balanced among the leaders of every cluster. The proposed protocol uses the inter-cloud resource management, where a leader is selected from the cloud that interacts to other cloud and decides on virtual machine (VM) migration. The decision about job allocation is not acknowledged by a single machine, which generates the scalable architecture of the proposed protocol. The protocol considers the current load situation and decides at the time of request submission. This protocol is adaptable, reliable and scalable and supports green computing by utilizing server solidification.

Clustering is one of the important data mining issues, especially for large and distributed data analysis. Distributed computing environments such as Peer-to-Peer (P2P) networks involve separated/scattered data sources, distributed among the peers. According to unpredictable growth and dynamic nature of P2P networks, data of peers are constantly changing. Due to the high volume of computing and communications and privacy concerns, processing of these types of data should be applied in a distributed way and without central management. Today, most applications of P2P systems focus on unstructured P2P systems. In unstructured P2P networks, spreading gossip is a simple and efficient method of communication, which can adapt to dynamic conditions in these networks. Recently, some algorithms with different pros and cons have been proposed for data clustering in P2P networks. In this paper, by combining a novel method for extracting the representative data, a gossip-based protocol and a new centralized clustering method, a Gossip Based Distributed Clustering algorithm for P2P networks called GBDC-P2P is proposed. The GBDC-P2P algorithm is suitable for data clustering in unstructured P2P networks and it adapts to the dynamic conditions of these networks. In the GBDC-P2P algorithm, peers perform data clustering operation with a distributed approach only through communications with their neighbours. The GBDC-P2P does not need to rely on a central server and it performs asynchronously. Evaluation results demonstrate the superior performance of the GBDC-P2P algorithm. Also, a comparative analysis with other well-established methods illustrates the efficiency of the proposed method.

In a sensor network in which each sensor controls a real-valued state, the goal of a distributed averaging problem is to compute the global average in a decentralized way, which is the average of all sensors' initial state values across the entire network. A T-periodic gossiping protocol can solve such a problem, which stipulates that each agent must gossip with each of its neighbors exactly once every T time unit. The convergence rate of a T-periodic gossiping protocol is determined by the magnitude of the second largest eigenvalue of the stochastic matrix associated with the gossip sequence occurring over one period. An interesting result is that when the allowable gossip graph is a tree, the convergence rate is independent of gossip orders within one period. This paper will prove this result by developing several properties of doubly stochastic matrices. The properties derived also can be used in analyzing convergence rate problems of other periodic gossip protocols.

This paper considers the scheduling of distributable real time tasks in dynamic networks which are prone to failures and do not have a fixed network infrastructure. We propose a distributable scheduling algorithm using gossip called GBTS-F for reliable and dynamic discovery of appropriate nodes which can execute the tasks. GBTS-F uses the slack time of the tasks for optimizing the gossiping duration and thus satisfies the each task timing constraints with probabilistic guarantee. Even though gossip protocols are usually fault tolerant but to handle byzantine faults and to control the high message complexity incurred during gossiping we propose to use an expander graph. Performance analysis and simulation results show that GBTS-F performs better than other state of art algorithms in terms of message complexity and task success probability.

Sharing information among nodes is a key function in Wireless sensor networks (WSNs) applications. Gossip protocols can be employed to facilitate data exchange and ensure data delivery to a sink node. In this paper, we propose two protocols to enhance the traditional gossip protocol by providing lightweight distance-based methods for selecting the next optimal node to retransmit a message. The first proposed protocol, NNGossip, uses the nearest neighbor distance measure, while the second, CBGossip, uses the city block distance measures. The major advantage of using these two techniques is that the computation is simple and fast and hence preserves the energy. We evaluated the performance of the proposed protocols against the traditional gossip protocol, Gossiping, and the Fair Efficient Location-based Gossiping protocol, FELGossiping. The experimental results show that using the proposed protocols maximize the network lifetime and insures efficient bandwidth while maintaining the delay at a low level.

The network function virtualization (NFV) paradigm decouples service functions (SFs) from the physical equipment where they are executed, thus increasing the efficiency of resource utilization, and makes networks and services more scalable and flexible. However, in order to efficiently manage and chain SFs to build network service slices in 5G networks, it is necessary to localize (virtualized) SFs together with their current status, which includes their load, attached virtual links status, configuration parameters, etc. To this aim, we propose a monitoring architecture able to track the network location and the current status of distributed and virtualized SFs, by using agents responsible to monitor the status of co-located SFs, both physical and virtual ones. The monitoring agents exchange their information by means of a gossip protocol to increase the reliability of the process and to build a distributed service monitoring architecture. In this way, it is possible to keep service decisions as local as possible, limiting the interactions with a centralized orchestrator, and thus increasing network scalability. We show that the network overhead of the distributed monitoring process is negligible.

Gossip protocols play an important role in disseminating information and solving global tasks over networks in a distributed fashion. In this paper, we propose gossip algorithms that preserve the sum of network states (and therefore the average), while fully protecting node privacy even against eavesdroppers possessing the entire information flow and network knowledge. At each time step, a node is selected to interact with one of its neighbors via deterministic or random gossiping. The selected node generates a random number to replace its current state, and sends to the neighbor the difference between the current state and the random number. On receiving the data from the selected node, the neighbor sets its new state as the sum of its current state and the difference. The algorithms can be used as a simple encryption step in distributed optimization and computation algorithms. In this Part I, we study the output statistics of the proposed algorithms with deterministic edge sequence selection, in addition to the convergence limits and encryption time of their randomized version.

Future extreme-scale high-performance computing systems will be required\ud to work under frequent component failures. The MPI Forum’s User\ud Level Failure Mitigation proposal has introduced an operation,\ud MPI Comm shrink, to synchronize the alive processes on the list of failed\ud processes, so that applications can continue to execute even in the presence\ud of failures by adopting algorithm-based fault tolerance techniques. This\ud MPI Comm shrink operation requires a failure detection and consensus\ud algorithm. This paper presents three novel failure detection and consensus\ud algorithms using Gossiping. Stochastic pinging is used to quickly detect\ud failures during the execution of the algorithm, failures are then disseminated\ud to all the fault-free processes in the system and consensus on the\ud failures is detected using the three consensus techniques. The proposed\ud algorithms were implemented and tested using the Extreme-scale Simulator.\ud The results show that the stochastic pinging detects all the failures in\ud the system. In all the algorithms, the number of Gossip cycles to achieve\ud global consensus scales logarithmically with system size. The second algorithm\ud also shows better scalability in terms of memory and network\ud bandwidth usage and a perfect synchronization in achieving global consensus.\ud The third approach is a three-phase distributed failure detection\ud and consensus algorithm and provides consistency guarantees even in very\ud large and extreme-scale systems while at the same time being memory and\ud bandwidth efficient.

Many decentralized algorithms allow both proactive and reactive implementations. Examples include gossip protocols for broadcasting and decentralized computing, as well as chaotic matrix iteration algorithms. In proactive systems, nodes communicate at a fixed rate in regular intervals, while in reactive systems they communicate in response to certain events such as the arrival of fresh data. Although reactive algorithms tend to stabilize/converge/self-heal much faster, they have serious drawbacks: they may cause bursts in bandwidth consumption, and they may also cause starvation when the number of messages circulating in the system becomes too low. Proactive algorithms do not have these problems, but nodes waste a lot of time sitting on fresh information. Here, we propose a novel family of adaptive protocols that apply rate limiting inspired by the token bucket algorithm to prevent bursts, but they also include proactive communication to prevent starvation. With the help of our traffic shaping service, some applications approach the speed of the reactive implementation, while maintaining strong guarantees regarding the total communication cost and burstiness. Due to the proactive component we can help maintain a certain level of activity despite losing messages due to faults or the application semantics. We perform simulation experiments in different scenarios including a real smartphone availability trace. Our results suggest up to a fourfold speedup in a broadcast application, and an order of magnitude speedup in the case of gossip learning, when compared to the purely proactive implementation.

Gossip based communication is an efficient tool to manage unstructured decentralized Peer-to-Peer (P2P) overlay connectivity. Such unstructured overlay connectivity is prone to security risks. Few malicious nodes are able to isolate all peer of the entire overlay as in Hub attack. Several existing security protocols such as SPSS, TooLate, and S-Gossip have dealt with this Hub attack. A probabilistic gossip-based secure protocol is introduced to handle this attack efficiently. It senses faulty neighbours before gossip with high probability. It uses a single control table to seize the malicious nodes. The comparison shows that the effects of the proposed security protocol are better than others.

International audience; This paper deals with Principal Components Analysis (PCA) of data spread over a network where central coordination and synchronous communication between networking nodes are forbidden. We propose an asynchronous and decentralized PCA algorithm dedicated to large scale problems, where " large " simultaneously applies to dimensionality, number of observations and network size. It is based on the integration of a dimension reduction step into a Gossip consensus protocol. Unlike other approaches, a straightforward dual formulation makes it suitable when observed dimensions are distributed. We theoretically show its equivalence with a centralized PCA under a low-rank assumption on training data. An experimental analysis reveals that it achieves a good accuracy with a reasonable communication cost even when the low-rank assumption is relaxed.

Distributed computation of average values held by nodes belonging to a self-organized network is a key task in many application areas, ranging from sensor and ad-hoc networks to networked control systems. Severe computational, communication, and energy constraints typical of these environments prompt for the design of specific solutions addressing these issues. In this context, gossip algorithms represent valuable approaches because of their simple local communication patterns, resulting into robustness to dynamic topology changes. Several variants of gossip-based techniques have been proposed, mainly focused on improvements of the convergence time, which directly impacts energy expenditure. Energy efficiency remains however a challenging issue to be addressed. In this letter, we introduce a novel energy aware distributed averaging algorithm which combines the standard randomized gossip protocol with a probabilistic load balancing technique, the power of two choices. Experimental results show that the proposed solution achieves better load balancing with respect to standard pairwise averaging, enabling considerable improvements in the network lifetime without impairing convergence time.

Distributed aggregation queries like average and sum can be implemented in different paradigms like gossip and hierarchical approaches. In the literature, these two paradigms are routinely associated with stereotypes such as “trees are fragile and complicated” and “gossip is slow and expensive”. However, a closer look reveals that these statements are not backed up by systematic studies. A fair and informative comparison is clearly needed. However, this is a hard task because the performance of protocols from the two paradigms depends on different subtleties of the environment and the implementation of the protocols. We tackle this problem by carefully designing the comparison study. We use state-of-the-art algorithms and propose the problem of monitoring the network size in the presence of churn as the ideal problem for comparing very different paradigms for global aggregation. Our simulation study helps us identify the most important factors that differentiate between gossip and spanning tree aggregation: the time needed to compute a truly global output, the properties of the underlying topology, and sensitivity to dynamism. We demonstrate the effect of these factors in different practical topologies and scenarios. Our results help us to choose the right protocol in the light of the topology and dynamism patterns.

In the last decade, several gossip-based algorithms have been introduced for data aggregation in distributed systems. The main and common advantage of these algorithms is their robustness in dynamic and fault-prone environments. However, gossip-based algorithms are not robust in hostile environments. In such environments, some malicious nodes intentionally violate the normal execution of the algorithm to distort the aggregate value. In this paper, we focus on gossip-based averaging and try to improve the security of these algorithms. First, we revise existing gossip-based averaging algorithms to present a more secure algorithm called "Pull-Adjust." Then, we develop and examine a light, transparent, and fully distributed protection system to push back malicious nodes. The simulation results show that the proposed system considerably improves the performance of the Pull-Adjust algorithm in hostile environments.

A gossip protocol aims at arriving, by means of point-to-point communications (or telephone calls), at a situation in which every agent knows all the information initially present in the network. If it is forbidden to have more than one call at the same time, the protocol is called sequential. We generalise a method, that originates from the famous coupon collector’s problem and that was proposed by John Haigh in 1981, for bounding the expected duration of sequential gossip protocols. We give two examples of protocols where this method succeeds and two examples of protocols where this method fails to give useful bounds. Our main contribution is that, although Haigh originally applied this method in a protocol where any call is available at any moment, we show that this method can be applied in protocols where the number of available calls is decreasing. Furthermore, for one of the protocols where Haigh’s method fails we were able to obtain lower bounds for the expectation using results from random graph theory.

We provide an in-depth study of the knowledge-theoretic aspects of communication in so-called gossip protocols. Pairs of agents communicate by means of calls in order to spread information—so-called secrets—within the group. Depending on the nature of such calls knowledge spreads in different ways within the group. Systematizing existing literature, we identify 18 different types of communication, and model their epistemic effects through corresponding indistinguishability relations. We then provide a classification of these relations and show its usefulness for an epistemic analysis in presence of different communication types. Finally, we explain how to formalise the assumption that the agents have common knowledge of a distributed epistemic gossip protocol.

Many distributed applications require cooperating to fuse their data in those WSNs in real time. Some of these WSNs allow interacting with publishers and subscribers (P/S) sensors. But, there exist little research works on development of causal ordering based on virtual synchronous group membership of these P/S systems, one of mandatory properties for this kind of application fields. In this paper, we propose a novel approach based on gossip protocols and virtual synchronous group membership, guaranteeing the causal message ordering in those WSNs. In the proposed protocol, a broker gossips about FLUSH including the whole set of vectors to subscribers for virtual synchronous group membership. The protocol does not end based on the acknowledgement of FLUSH, but on the maximum gossip rounds of gossip disseminations. Therefore, this protocol is appropriate for sensor networks configured with active and passive sensors in real time synchronization. Its features might result in very low cost communication overhead between brokers and subscribers with flexible consistency by cooperating to fuse their data. Simulation results show that our gossip-style dissemination protocol outperforms the previous one in terms of virtual synchronous group membership.