Search

We present \textsc{P2PTFHH} (Peer--to--Peer Time--Faded Heavy Hitters) which, to the best of our knowledge, is the first distributed algorithm for mining time--faded heavy hitters on unstructured P2P networks. \textsc{P2PTFHH} is based on the \textsc{FDCMSS} (Forward Decay Count--Min Space-Saving) sequential algorithm, and efficiently exploits an averaging gossip protocol, by merging in each interaction the involved peers' underlying data structures. We formally prove the convergence and correctness properties of our distributed algorithm and show that it is fast and simple to implement. Extensive experimental results confirm that \textsc{P2PTFHH} retains the extreme accuracy and error bound provided by \textsc{FDCMSS} whilst showing excellent scalability. Our contributions are three-fold: (i) we prove that the averaging gossip protocol can be used jointly with our augmented sketch data structure for mining time--faded heavy hitters; (ii) we prove the error bounds on frequency estimation; (iii) we experimentally prove that \textsc{P2PTFHH} is extremely accurate and fast, allowing near real time processing of large datasets., arXiv admin note: text overlap with arXiv:1806.06580

Flying Ad Hoc networks, (FANETs) in recent years, have actively been used in monitoring landscape, military and mapping terrains. However, with the advent of the emerging concept of smart cities and new business applications, these flying devices and drones have found a new use case in the medical and governance sector. But these networks suffer from the major problem of centralization. Although centralization does provide reliability and efficiency but also poses the threat of a single point of failure. Meanwhile, blockchain widely known for its decentralization is heavily researched and can be utilized in this case to offer a solution to the problem of centralization of FANETs. Therefore, in this paper, we propose a decentralized architecture of flying ad hoc nodes based on blockchain and using Practical byzantine fault tolerance (PBFT) for consensus among nodes. By employing PBFT, the architecture is not only computationally efficient and fast. In addition, we have used a gossip protocol for passing messages among nodes. Lastly, we have simulated the working of our model and the experimental results show that the proposed method works with nearly constant throughput and latency while increasing the network size and approximately constant message overhead with increase transaction for given network size.

The increasing penetration of renewable energy sources is impacting the operation of the distribution grid. Whilst they are currently placing a burden on the distribution grid, it is generally agreed that these sources could also be used for active grid control, thereby contributing to a stable and secure grid. Smart photovoltaic inverters can contribute to active grid control, by expanding their features with added functions. In this paper, we develop a novel grid voltage support algorithm for smart photovoltaic inverters, based on distributed optimization and peer-to-peer communication. The Jacobi-Proximal Alternating Direction Method of Multipliers is applied in this paper to locally optimize reactive power compensation and active power curtailment of each inverter participating in the voltage control. We propose the use of a push-sum gossip protocol to enable peer-to-peer data interchange between inverters. We also use strategies to improve the robustness of the proposed algorithm: an acceleration strategy, a feedback strategy and an anti-windup strategy. A case study is presented, demonstrating the fast convergence of the algorithm and its ability to solve the voltage problems.

Mobility-as-a-Service (MaaS) applies the everything-as-a-service paradigm of Cloud Computing to transportation: a MaaS provider offers to its users the dynamic composition of solutions of different travel agencies into a single, consistent interface. Traditionally, transits and data on mobility belong to a scattered plethora of operators. Thus, we argue that the economic model of MaaS is that of federations of providers, each trading its resources to coordinate multi-modal solutions for mobility. Such flexibility comes with many security and privacy concerns, of which insider threat is one of the most prominent. In this paper, we revise and extend previous work where we classified the potential threats of individual operators and markets of federated MaaS providers, proposing appropriate countermeasures to mitigate the problems. In addition, we consider the emerging case of Cloud-of-Things (CoT) for mobility, i.e., networks of ubiquitous, pervasive devices that provide real-time data on objects and people. Automation and pervasiveness of CoT make an additional attack surface for insiders. In an effort to limit such phenomenon, we present an overlay networking architecture, based on gossip protocols, that lets users share information on mobility with each other. A peculiarity of the architecture is that it both constrains the quality and quantity of data obtainable by insiders, optimizing the routing of requests to involve only users that are able to answer them.

Existing live video streaming systems can be classified as server (cloud) based or as peer-to-peer (P2P). The client–server approach promises stability and (Quality of Service) QoS by incurring expensive bandwidth provision cost on the server. On the other hand, P2P architecture is scalable with low bandwidth and maintenance cost. Here we propose a cloud assisted P2P live streaming architecture which is scalable and stable. In order to achieve this we have developed: (i) a scalable gossip protocol that monitors dynamically the total available bandwidth resources of the participating peers, (ii) a control strategy that dynamically allocates the bandwidth that is required. The first step towards this direction is to create a theoretical model that captures the dynamic relationship between the total bandwidth surplus/deficit and peers’ bandwidth utilization in order to be able to apply a control theoretical approach. Moreover, we quantify the impact of monitoring inaccuracies and peers’ dynamic bandwidth changes and we calculate analytically, as a function of them, the minimum amount of bandwidth overprovision that ensures the undisturbed distribution of the stream. System is evaluated through a detailed simulator of a complete P2P live streaming system and testified the uninterrupted and complete stream delivery even in very adverse bandwidth changes.

Due to large volumes of data available online, techniques such as document classification and clustering are required for organization, analysis and management of data. Similarity-based Clustering (SBC) is used by many existing systems for filtering information. Decentralized gossip-based overlays offer a simple, robust and scalable solution to SBC clustering. Convergence and communication complexity are the two key areas of concern when SBC is implemented using these overlays. Convergence guarantees accurate clustering but costs bandwidth because these systems rely on message passing to achieve convergence. In this work, we address the long tail problem, experienced by low in-degree nodes in a long tailed similarity distribution, such as power-law distribution and propose a new SBC approach, Optimum Benefit Protocol (OBP), that converges more rapidly than existing approaches and reduces the long tail. The proposed protocol only sends messages that could benefit the receiver, reducing bandwidth to one fifth of the default. Our protocol obtains at least 90% convergence for a 900 node network, starting in a random configuration, in less than 10 cycles, for all observed experiments. We used real world distributions from Yahoo, Movielens, and Epinion datasets, for experimentation.

In this work we study the problem of multi-robot coverage of a planar region when the sensory field used to approximate the density of event appearance is not known in advance. We address the problem by considering two different communication architectures: client–server and peer-to-peer . In the first architecture the robots are allowed to communicate with a central server/base station. In the second the robots communicate among neighboring peers by means of a gossip protocol in a distributed fashion. For both the architectures, we resort to nonparametric Gaussian regression approach to estimate the unknown sensory field of interest from a collection of noisy samples. We propose a probabilistic control strategy based on the posterior of the estimation error variance, which lets the robots to estimate the true sensory field with any arbitrary accuracy while simultaneously computing and exploiting the corresponding centroidal Voronoi partitions. We also present a numerically efficient approximation based on a spatial discretization to trade-off the accuracy of the estimated map against the required computational complexity. This trade-off can be tuned based on explicit estimation error bounds which depend on the spatial resolution and the Gaussian kernel parameters. Finally, we test the proposed solutions via extensive numerical simulations.

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.

Gossip algorithms is a common term to describe protocols for unreliable information dissemination in natural networks, which are not optimally designed for efficient communication between network entities. We consider application of gossip algorithms to quantum networks and show that any quantum network can be updated to optimal configuration with local operations and classical communication. This allows to seed-up -- in the best case exponentially -- the quantum information dissemination. Irrespective of the initial configuration of the quantum network, the update requiters at most polynomial number of local operations and classical communication., Comment: 5 pages, 1 figure, 15 references

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.

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.

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.

In this paper we propose a novel distributed algorithm for task assignment on heterogeneous networks. We consider a set of tasks with heterogeneous cost to be assigned to a set of nodes with heterogeneous execution speed and interconnected by a network with unknown topology represented by an undirected graph. Our objective is to minimize the execution time of the set of tasks by the networked system. We propose a local interaction rule which allows the nodes of a network to cooperatively assign tasks among themselves with a guaranteed performance with respect to the optimal assignment exploiting a gossip based randomized interaction scheme. We characterize the convergence properties of the proposed approach and provide simulation results.

This paper considers the quasi-random rumor spreading model introduced by Doerr, Friedrich, and Sauerwald in [10], hereafter referred to as the list-based model. Each node is provided with a cyclic list of all its neighbors, and, upon reception of a message, it chooses a random position in its list, and from then on calls its neighbors in the order of the list. This model is known to perform asymptotically at least as well as the random phone-call model, for many network classes. Motivated by potential applications of the list-based model to live streaming, we are interested in its worst case behavior. Our first main result is the design of an O(m+nlog⁡n)-time algorithm that, given any n-node m-edge network G, and any source-target pair s,t∈V(G), computes the maximum number of rounds it may take for a rumor to be broadcast from s to t in G, in the list-based model. Hence, the list-based model is computationally easy to tackle in its basic version. The situation is radically different when one is considering variants of the model in which nodes are aware of the status of their neighbors, i.e., are aware of whether or not they have already received the rumor, at any point in time. Indeed, our second main result states that, unless P=NP, the worst case behavior of the list-based model with the additional feature that every node is perpetually aware of which of its neighbors have already received the rumor cannot be approximated in polynomial time within a (1n)12−ϵ multiplicative factor, for any ϵ>0. As a byproduct of this latter result, we can show that, unless P=NP, there are no PTAS enabling to approximate the worst case behavior of the list-based model, whenever every node perpetually keeps track of the subset of its neighbors which have sent the rumor to it so far.

We propose using real world mobility traces to identify tractable theoretical models for the study of distributed algorithms in mobile networks. Specifically, we derive a vehicular ad hoc network model from a large corpus of position data generated by San Francisco-area taxicabs. Unlike previous work, our model does not assume global connectivity or eventual stability. Instead, we assume only that some subset of processes might be connected through transient paths (e.g., paths that exist over time). We use this model to study the problem of prioritized gossip, in which processes attempt to disseminate messages of different priority. We present CabChat, a distributed prioritized gossip algorithm that leverages an interesting connection to the classic Tower of Hanoi problem to schedule the broadcast of packets of different priorities. Whereas previous studies of gossip leverage strong connectivity or stabilization assumptions to prove the time complexity of global termination, in our model, with its weak assumptions, we instead analyze CabChat with respect to its ability to deliver a high proportion of high priority messages over the transient paths that happen to exist in a given execution.

Gossip protocols are a common solution for content-based publish-subscribe. However, in spite of the advantages that these protocols present in comparison to other approaches, such as distributed hash tables, they also have inherent scalability issues. In this paper, CCPS (Caching Content-based Publish-Subscribe) is presented as a publish-subscribe protocol designed to address these scalability issues. Through caching, CCPS exploits search query repetition to address load balancing problems. It has been designed having in mind its use in combination with existing publish-subscribe solutions so as to improve their performance. In the paper, the protocol description together with the implementation details of its fundamental operations are provided, while CCPS performance is evaluated against standard gossip protocols.

In this paper we address a class of heterogeneous multi-vehicle task assignment and routing problems. We propose two distributed algorithms based on gossip communication: the first algorithm is based on a local exact optimization and the second is based on a local approximate greedy heuristic. We consider the case where a set of heterogeneous tasks arbitrarily distributed in a plane has to be serviced by a set of mobile robots, each with a given movement speed and task execution speed. Our goal is to minimize the maximum execution time of robots.

This paper analyzes the adoption of unstructured P2P overlay networks to build resource discovery services. We consider a simple distributed communication protocol, which is based on gossip and on the local knowledge each node has about resources hold by its neighbors. In particular, upon reception (or generation) of a novel query, a node relays the message to those neighbors that have resources whose profile matches the query. Moreover, the node gossips the query to other remaining neighbors, so that the query can be disseminated through the overlay. A mathematical analysis is provided to estimate the number of nodes receiving the query (and consequently, the portion of query hits), based on the network topology, resource availability and gossip probability. Results show that the use of unstructured networks, coupled with simple dissemination protocols, represent a viable approach to build P2P resource discovery systems.

In this paper we propose GoDisco++, a gossip based approach for information dissemination in online social community networks. GoDiscoo++ uses local information available to nodes-that is information associated with a node and its neighbors. The algorithm exploits multiple relations which may exist between nodes, and applies social principles and behavior inspired decentralized mechanisms for targeted dissemination. The dissemination process works with the dual aims of (i) maximizing the spread among relevant nodes (high recall) and (ii) minimizing spamming among non-relevant nodes (high precision). Such a designed dissemination scheme can have interesting applications like probabilistic publish/subscribe, decentralized recommendation and contextual advertisement systems, to name a few. We validate the proposed approach with simulation experiments performed using real and synthetic datasets.

The K-Means algorithm for cluster analysis is one of the most influential and popular data mining methods. Its straightforward parallel formulation is well suited for distributed memory systems with reliable interconnection networks, such as massively parallel processors and clusters of workstations. However, in large-scale geographically distributed systems the straightforward parallel algorithm can be rendered useless by a single communication failure or high latency in communication paths. The lack of scalable and fault tolerant global communication and synchronisation methods in large-scale systems has hindered the adoption of the K-Means algorithm for applications in large networked systems such as wireless sensor networks, peer-to-peer systems and mobile ad hoc networks. This work proposes a fully distributed K-Means algorithm (EpidemicK-Means) which does not require global communication and is intrinsically fault tolerant. The proposed distributed K-Means algorithm provides a clustering solution which can approximate the solution of an ideal centralised algorithm over the aggregated data as closely as desired. A comparative performance analysis is carried out against the state of the art sampling methods and shows that the proposed method overcomes the limitations of the sampling-based approaches for skewed clusters distributions. The experimental analysis confirms that the proposed algorithm is very accurate and fault tolerant under unreliable network conditions (message loss and node failures) and is suitable for asynchronous networks of very large and extreme scale.

Gossip-based peer-to-peer protocols proved to be very efficient for supporting dynamic and complex information exchange among distributed peers. They are useful for building and maintaining the network topology itself as well as to support a pervasive diffusion of the information injected into the network. This is very useful in a world where there is a growing need to access and be aware of many types of distributed resources like Internet pages, shared files, online products, news and information. Finding flexible, scalable and efficient mechanisms addressing this topic is a key issue, even with relevant social and economic aspects. In this paper, we propose the general architecture of a system whose aim is to exploit the collaborative exchange of information between peers in order to build a system able to gather similar users and spread useful suggestions among them.

This paper studies a decentralized, randomized gossip algorithm for computing a majority vote amongst the binary decisions associated to n nodes organized in a fixed, ad-hoc network. It is indicated how this problem can be reduced to computing the global average using a standard, randomized gossip algorithm. Then, we illustrate how the majority vote problem allows one to formulate individual stopping rules deciding when an individual node makes its final verdict. Finally, we will provide an illustration of how well the algorithm and associated stopping rule behaves.

Information from others can be unreliable. Humans nevertheless act on such information, including gossip, to make various social calculations, thus raising the question of whether individuals can sort through social information to identify what is, in fact, true. Inspired by empirical literature on people's decision-making when considering gossip, we built an agent-based simulation model to examine how well simple decision rules could make sense of information as it propagated through a network. Our simulations revealed that a minimalistic decision-rule 'Bit-wise mode' - which compared information from multiple sources and then sought a consensus majority for each component bit within the message - was consistently the most successful at converging upon the truth. This decision rule attained high relative fitness even in maximally noisy networks, composed entirely of nodes that distorted the message. The rule was also superior to other decision rules regardless of its frequency in the population. Simulations carried out with variable agent memory constraints, different numbers of observers who initiated information propagation, and a variety of network types suggested that the single most important factor in making sense of information was the number of independent sources that agents could consult. Broadly, our model suggests that despite the distortion information is subject to in the real world, it is nevertheless possible to make sense of it based on simple Darwinian computations that integrate multiple sources.

Critical probability of a cellular automaton is investigated via a novel approach of back-ultradiscretization. Specifically, back-ultradiscretization of a gossip protocol provides a conservative yet analytical lower bound, which is usually hard to be evaluated in the form of cellular automata. Comparison of theoretical and numerical values are provided for several representative grids to evaluate efficacy of the proposed approach.

We propose using real world mobility traces to identify tractable theoretical models for the study of distributed algorithms in mobile networks. Specifically, we derive a vehicular ad hoc network model from a large corpus of position data generated by San Francisco-area taxicabs. Unlike previous work, our model does not assume global connectivity or eventual stability. Instead, we assume only that some subset of processes might be connected through transient paths (e.g., paths that exist over time). We use this model to study the problem of prioritized gossip, in which processes attempt to disseminate messages of different priority. We present CabChat, a distributed prioritized gossip algorithm that leverages an interesting connection to the classic Tower of Hanoi problem to schedule the broadcast of packets of different priorities. Whereas previous studies of gossip leverage strong connectivity or stabilization assumptions to prove the time complexity of global termination, in our model, with its weak assumptions, we instead analyze CabChat with respect to its ability to deliver a high proportion of high priority messages over the transient paths that happen to exist in a given execution.

Peer-to-peer Desktop Grids provide integrated computational resources by leveraging autonomous desktop computers located at the edge of the Internet to offer high computing power. The arbitrary arrival and serving rates of tasks on peers impedes the high throughput in large-scale P2P Grids. We propose a novel autonomous resource allocation scheme, which can maximize the throughput of self-organizing P2P Grid systems. Our design possesses three key features: (1) high adaptability to dynamic environment by proactive and convex-optimal estimation of nodes' volatile states; (2) minimized task migration conflict probability (upper bound can be limited to 2%) of over-utilized nodes individually shifting surplus loads; (3) a load-status conscious gossip protocol for optimizing distributed resource discovery effect. Based on a real-life user's workload and capacity distribution, the simulation results show that our approach could get significantly improved throughput with 23.6-47.1% reduction on unprocessed workload compared to other methods. We also observe high scalability of our solution under dynamic peer-churning situations.

In this paper, we analyze distributed average consensus algorithms, both deterministic and gossip based, with respect to a new metric related to the energy cost of communication among agents. We first introduce a new notion of communication complexity as a metric to assess the energy efficiency properties of consensus algorithms. We provide explicit formulas to compute the communication complexity of deterministic algorithms and gossip based algorithms depending on different stopping criteria. We also show that the gossip based algorithms have less communication complexity than the deterministic counterparts under mild conditions, usually satisfied by a large number of networks. We also show that the gossip algorithm with minimum communication complexity can be effectively computed as the solution of a convex optimization problem.

Large-scale overlay networks have become crucial ingredients of fully-decentralized appli- cations and peer-to-peer systems. Depending on the task at hand, overlay networks are organized into different topologies, such as rings, trees, semantic and geographic proximity networks. We argue that the central role overlay networks play in decentralized applica- tion development requires a more systematic study and effort towards understanding the possibilities and limits of overlay network construction in its generality. Our contribu- tion in this paper is a gossip protocol called T-MAN that can build a wide range of overlay networks from scratch, relying only on minimal assumptions. The protocol is fast, robust, and very simple. It is also highly configurable as the desired topology itself is a parameter in the form of a ranking method that orders nodes according to preference for a base node to select them as neighbors. The paper presents extensive empirical analysis of the protocol along with theoretical analysis of certain aspects of its behavior. We also describe a prac- tical application of T-MAN for building CHORD distributed hash table overlays efficiently from scratch.

We present Brahms, an algorithm for sampling random nodes in a large dynamic system prone to malicious behavior. Brahms stores small membership views at each node, and yet overcomes Byzantine attacks by a linear portion of the system. Brahms is composed of two components. The first is an attack-resilient gossip-based membership protocol. The second component extracts independent uniformly random node samples from the stream of node ids gossiped by the first. We evaluate Brahms using rigorous analysis, backed by simulations, which show that our theoretical model captures the protocol's essentials. We study two representative attacks, and show that with high probability, an attacker cannot create a partition between correct nodes. We further prove that each node's sample converges to an independent uniform one over time. To our knowledge, no such properties were proven for gossip protocols in the past.

This paper abstracts the problem of network nodes discovering one another in a network of unknown size using all-to-all gossip. The problem is studied in terms of evolving directed graphs where each vertex represents a participating node and each edge represents one node’s knowledge about another. Ideally, such a graph has diameter one, i.e., each node knows all others. Nodes share their knowledge by sending gossip messages. Gossip among the nodes allows them to discover one another, decreasing the diameter of the graph. Here this problem is considered in several synchronous settings under different assumptions about the ability of the participating nodes to communicate. Specifically, the following aspects of communication are considered: (1) the ability of the nodes to multicast gossip messages, and (2) the size of the messages. The results describe the lower and upper bounds on the number of synchronous rounds required for the participants to discover each other. A particular question of interest is: if the network size is unknown, how does a node know that it has discovered all other nodes? Given a weakly-connected graph describing the initial knowledge of the nodes, every node in our algorithm can stop the discovery process knowing that there are no unknown nodes—this is done without any prior knowledge of the total number of nodes participating in the computation.

In this paper we present a novel probabilistic protocol for path discovery in Mobile Ad Hoc Networks (MANETs). The protocol implements what we call a polarized gossiping algorithm. While in the classical gossip algorithm each node forwards a message with the same probability, our proposal is characterized by a variable gossiping probability, which is high enough only for sustaining the spreading process towards the destination. The gossiping probability of a node is determined by the difference between its proximity to the destination and the proximity to the destination of the node from which the message was received. Differently from other proposals no external location service support, e.g., via GPS, is required. Rather, the proximity is estimated from the ''inside'' of the network using periodic beacons for determining the time elapsed since a node met the destination and the dwell time of a node with the destination. These information are then exploited by nodes to modulate their gossiping probability. The paper reports a mathematical model for the analysis of the algorithm along with an extensive simulation study of its implementation, which shows the suitability of the proposed solution.

Many ad hoc routing algorithms rely on broadcast flooding for location discovery or, more generally, for secure routing applications. Flooding is a robust algorithm but because of its extreme redundancy, it is impractical in dense networks. Indeed in large wireless networks, the use of flooding algorithms may lead to broadcast storms where the number of collisions is so large that it causes system failure. To prevent broadcast storms, many mechanisms that reduce redundant transmissions have been proposed that reduce retransmission overhead either deterministically or probabilistically. Gossip is a probabilistic algorithm in which packet retransmission is based on the outcome of coin tosses. The retransmission probability can be fixed, dynamic or adaptive. With dynamic gossip, local information is used to determine the retransmission probability. With adaptive gossip, the decision to relay is adjusted adaptively based on the outcome of coin tosses, the local network structure, and the local response to the flooding call. The goal of gossip is to minimize the number of retransmissions, while retaining the main benefits of flooding, e.g., universal coverage, minimal state retention, and path length preservation. In this paper we consider ways to reduce the number of redundant transmissions in flooding while guaranteeing security. We present several new gossip protocols that exploit local connectivity to adaptively correct propagation failures and protect against Byzantine attacks. A main contribution of this work is that we introduce a cell-grid approach that allows us to analytically prove performance and security protocol properties. The last two gossip protocols that we give are fully adaptive, i.e., they automatically correct all faults and guarantee delivery, the first such protocols to the best of our knowledge.

This paper addresses the issue of improving multicast packet delivery in mobile ad hoc networks and proposes an adaptive mechanism called Protocol-Independent Packet Delivery Improvement Service (PIDIS) to recover lost multicast packets. PIDIS provides its packet-delivery improvement services to any multicast routing protocol for mobile ad hoc networks by exploiting the mechanism of swarm intelligence to make intelligent decisions about where to fetch the lost multicast packets from. PIDIS is a gossip protocol, and nodes using PIDIS are only concerned with which neighbor nodes to gossip with to recover the most lost packets, rather than which member nodes to gossip with. Thus, it does not rely on membership information in a multicast scenario, which is often difficult to get. PIDIS employs the beneficial aspects of probabilistic routing and adapts well to mobility. PIDIS achieves probabilistic improvement in multicast packet delivery and, unlike other gossip-based schemes, does not need to maintain information about group members from which lost multicast packets are retrieved. Further, the operations of PIDIS do not rely on any underlying routing protocol or primitive, and can be incorporated into any ad hoc multicast routing protocol. We incorporated PIDIS over ODMRP [On-Demand Multicast Routing Protocol in Multihop Wireless Mobile Networks, Kluwer Mobile Networks and Applications, 2000], and compared it against Anonymous Gossip (AG) [International Conference on Distributed Computing Systems (ICDCS 2001) Phoenix, Arizona, April 2001] implemented over ODMRP, and ODMRP itself. Our simulation results show that ODMRP+PIDIS is more efficient and performs better than ODMRP+AG and ODMRP in terms of multicast packet delivery, end-to-end delay, and MAC layer overheads. We attribute the better performance and lower MAC overheads of ODMRP+PIDIS to the efficient gossiping made possible by using the swarm intelligence techniques.

Gossip-based broadcasting has recently gained popularity as a potentially effective solution for disseminating information in large-scale distributed applications. In this paper we propose a simple counter-based optimization for gossip-based broadcast protocols, aimed at enhancing reliability in the face of node failures. The basic idea is to have each node retransmit a broadcast message when the node has received the same message only a few times; a node thus can autonomously perceive the status of message dissemination and promote it when necessary. The usefulness of the technique is demonstrated through simulation results.

The problems of gossiping and broadcasting have been widely studied. The basic gossip problem is defined as follows: there are n individuals, with each individual having an item of gossip. The goal is to communicate each item of gossip to every other individual. Communication typically proceeds in rounds, with the objective of minimizing the number of rounds. One popular model, called the telephone call model, allows for communication to take place on any chosen matching between the individuals in each round. Each individual may send (receive) a single item of gossip in a round to (from) another individual. In the broadcasting problem, one individual wishes to broadcast an item of gossip to everyone else. In this paper, we study generalizations of gossiping and broadcasting. The basic extensions are: (a) each item of gossip needs to be broadcast to a specified subset of individuals and (b) several items of gossip may be known to a single individual. We study several problems in this framework that generalize gossiping and broadcasting. Our study of these generalizations was motivated by the problem of managing data on storage devices, typically a set of parallel disks. For initial data distribution, or for creating an initial data layout we may need to distribute data from a single server or from a collection of sources.

This paper provides an extensive experimental evaluation of the gossip technique for constructing scalable and reliable multicast protocols. This evaluation has been done by simulating several gossip and non gossip-based multicast protocols in a network simulator NS2. The evaluation comprises of three parts: (1) a comparison of the gossip technique with other traditional message loss detection and recovery techniques, (2) an extensive performance evaluation of the gossip technique under several different operating parameters, and (3) an evaluation of how the performance of a gossip-based multicast protocol is affected by varying various gossip parameters. The main conclusion of the paper is that the gossip technique is certainly a useful technique for constructing scalable and reliable multicast protocols. However, it performs poorly under some specific operating conditions, and its performance is affected by the selection criteria used to select a gossip subgroup and gossip period. Based on the results of this experimental evaluation, the paper identifies three major factors that critically affect the scalability and reliability of a multicast protocol. These are (1) percentage of overhead messages exchanged, (2) overhead message concentration, and (3) application characteristics that determine message arrival rate and message arrival pattern.

When striving for reliability, multicast protocols are most commonly designed as deterministic solutions. Such an approach seems to make the reasoning about reliability guarantees (traditionally, binary, “all-or-nothing”-like) in the face of packet losses and/or node crashes. It is however precisely this determinism that tends to become a limiting factor when aiming at both reliability and scalability, particularly in highly dynamic networks, e.g., ad hoc networks. Gossip-based multicast protocols appear to be a viable path towards providing multicast reliability guarantees. Such protocols embrace the non-deterministic nature of ad hoc networks, providing analytically predictable probabilistic reliability guarantees at a reasonable overhead. This paper presents the Route Driven Gossip (RDG) protocol, a gossip-based multicast protocol designed precisely to meet a more practical specification of probabilistic reliability in ad hoc networks. Our RDG protocol can be deployed on any basic on-demand routing protocol, achieving a high level of reliability without relying on any inherent multicast primitive. We illustrate our RDG protocol by layering it on top of the “bare” Dynamic Source Routing protocol, and convey our claims of reliability and scalability through both analysis and simulation.

Consider a distributed system running a protocol in which processes exchange information by passing messages. The gossip problem for the protocol is the following: Whenever a process q receives a message from another process p, q must be able to decide which of p and q has more recent information about r, for every other process r in the system. With this data, q is in a position to update its knowledge about the global state of the system. We propose a solution wherein to each message of the protocol, the sender adds information about its current state of knowledge about other processes. We do not add any new messages to the underlying computation. The additional information tagged onto each message is uniformly bounded if the channels are bounded. This means that for systems with bounded channels, the overhead of maintaining the latest gossip is a constant, independent of the length of the underlying computation. Moreover, gossip information can be used to implement bounded channels by inhibiting the sending of new messages over channels that are potentially full. Our solution to the gossip problem has several applications in the analysis of distributed systems. Many distributed algorithms rely, either explicitly or implicitly, on the local information available at a process about the global state of the system. Using our scheme, each process can ensure that during a computation it always maintains the best possible information about every other process. At a theoretical level, the gossip problem plays an important role in formal characterizations of finite-state message-passing systems., © Elsevier

Each of n nodes of a communication network has a piece of information (gossip) which should be made known to all other nodes. Gossiping is done by sending letters. In a unit of time each node can either send one letter to a neighbor or receive one such letter, containing one gossip currently known to the sender. Letters reach their destinations with constant probability 0

A very simple solution can be given to the gossip problem [1] which may be formulated as follows: There are n gossips each of which knows some gossip not known to the others. They communicate by telephone, and whenever one gossip calls another, they tell each other all they know at that time. How many calls are required before each gossip knows everything?