mpm + gossip   27

The Promise and Limitations of Gossip Protocols
What are the uses to which gossip is particularly well-matched, and what are its limitations? What alternatives are there to gossip-based solutions, and when would we be better-off using a non-gossip protocol? When, in effect, is gossip the technology of choice?
gossip 
6 days ago by mpm
Gossip-Based Computation of Aggregate Information
In this paper, we study the problem of computing aggregates with gossip-style protocols. Our first contribution is an analysis of simple gossip-based protocols for the computations of sums, averages, random samples, quantiles, and other aggregate functions, and we show that our protocols converge exponentially fast to the true answer when using uniform gossip.Our second contribution is the definition of a precise notion of the speed with which a node’s data diffuses through the network. We show that this diffusion speed is at theheart of the approximation guarantees for all of the above problems. We analyze the diffusion speed of uniform gossip in the presence of node and link failures, as well as for flooding-based mechanisms. The latter expose interesting connections to random walks on graphs
gossip 
9 weeks ago by mpm
Scuttlebutt Protocol Guide
Scuttlebutt is a protocol for building decentralized applications that work well offline and that no one person can control. Because there is no central server, Scuttlebutt clients connect to their peers to exchange information. This guide describes the protocols used to communicate within the Scuttlebutt network.
p2p  protocol  discovery  service-location  membership  gossip 
november 2018 by mpm
Stable and Consistent Membership at Scale with Rapid
We present the design and evaluation of Rapid, a distributed membership service. At Rapid’s core is a scheme for multi-process cut detection (CD) that revolves around two key insights: (i) it suspects a failure of a process only after alerts arrive from multiple sources, and (ii) when a group of processes experience problems, it detects failures of the entire group, rather than conclude about each process individually. Implementing these insights translates into a simple membership algorithm with low communication overhead.
overlay  membership  protocol  gossip 
october 2018 by mpm
Rapid is a scalable distributed membership service
We present Rapid, a scalable, distributed membership system that is stable in the face of a diverse range of failure scenarios, and provides participating processes a strongly consistent view of the system's membership.
membership  gossip  protocol  cluster  overlay 
october 2018 by mpm
Stable and Consistent Membership at Scale with Rapid
We present the design and evaluation of Rapid, a distributed membership service. At Rapid's core is a scheme for multi-process cut detection (CD) that revolves around two key insights: (i) it suspects a failure of a process only after alerts arrive from multiple sources, and (ii) when a group of processes experience problems, it detects failures of the entire group, rather than conclude about each process individually. Implementing these insights translates into a simple membership algorithm with low communication overhead.
membership  gossip  failure-detector 
august 2018 by mpm
Ant-Inspired Dynamic Task Allocation via Gossiping
We study the distributed task allocation problem in multi-agent systems, where each agent selects a task in such a way that, collectively, they achieve a proper global task allocation. In this paper, inspired by ant colonies, we propose several scalable and efficient algorithms to dynamically allocate the agents as the task demands vary. Similar to ants, in our algorithms, each agent obtains sufficient information to make its local decision by gossiping with the other ants. Our algorithms vary in their advantages and disadvantages, with respect to (1) how fast they react to dynamic demands change, (2) how many agents need to switch tasks, (3) whether extra agents are needed, and (4) whether they are resilient to faults
gossip  ants 
july 2017 by mpm
Lifeguard : SWIM-ing with Situational Awareness
we define a set of extensions to SWIM that allow a member to dynamically adjust its timeouts to mitigate timeliness issues. We call these extensions Lifeguard
protocol  gossip 
july 2017 by mpm
Thicket: A protocol for building and maintaining multiple trees in a p2p overlay
One way to efficiently disseminate information in a P2P overlay is to rely on a spanning tree. However, in a tree, interior nodes support a much higher load than leaf nodes. Also, the failure of a single node can break the tree, impairing the reliability of the dissemination protocol. These problems can be addressed by using multiple trees, such that each node is interior in just a few trees and a leaf node in the remaining; the multiple trees approach allows to achieve load distribution and also to send redundant information for fault-tolerance. This paper proposes Thicket, a decentralized algorithm to efficiently build and maintain such multiple trees over a single unstructured overlay network. The algorithm has been implemented and is extensively evaluated using simulation in a P2P overlay with 10.000 nodes
gossip  overlay 
october 2015 by mpm
Hyphen: A Hybrid Protocol for Generic Overlay Construction in P2P Environments
We describe Hyphen, a middleware for overlay construction and maintenance that supports a range of overlay topologies with custom properties, and show how it can replace topology construction for a variety of application-level multicast systems. Unlike previous efforts, Hyphen can construct and maintain a range of overlay topologies such as trees and forests with specific optimisation goals such as low latency or high bandwidth
gossip  overlay 
october 2015 by mpm
plumtree
Plumtree is an implementation of Plumtree[1], the epidemic broadcast protocol. It is extracted from the implementation in riak_core[2]. Instead of the riak_core ring and riak's ring gossip protocol, it includes a standalone membership gossip, built around riak_dt[3]'s ORSWOT[4]
broadcast  gossip  erlang 
october 2015 by mpm
Data Dissemination: From Academia to Industry
Disseminating information across a large set of processes is a classic problem in distributed systems. In this talk we will present and discuss several classes of epidemic solutions for achieving reliable broadcast across a large number of processes that can be found in the scientific literature, and briefly explore their strong and weak points. Then we will focus on a concrete approach based on the combination of different gossiping techniques such that implicit, albeit robust, spanning trees can be leveraged to disseminate information both reliably and efficiently. We further discuss how this technique which spawned from academia, ended up being used in Industry, as a part of the Cluster Metadata Subsystem of Basho's Riak. We'll explore some of the key differences between the original academic proposal and its applications on Riak and discuss the practical reasons that motivated these modifications. Finally, we will discuss some future techniques that Basho is currently exploring.
alm  gossip 
november 2014 by mpm
Epidemic Broadcast Trees
There is an inherent trade-off between epidemic and deterministic tree-based broadcast primitives. Tree-based approaches have a small message complexity in steady-state but are very fragile in the presence of faults. Gossip, or epidemic, protocols have a higher message complexity but also offer much higher resilience.

This paper proposes an integrated broadcast scheme that combines both approaches. We use a low cost scheme to build and maintain broadcast trees embedded on a gossip-based overlay. The protocol sends the message payload preferably via tree branches but uses the remaining links of the gossip overlay for fast recovery and expedite tree healing. Experimental evaluation presented in the paper shows that our new strategy has a low overhead and that is able to support large number of faults while maintaining a high reliability. This paper proposes an integrated broadcast scheme that combines both approaches. We use a low cost scheme to build and maintain broadcast trees embedded on a gossip-based overlay...
alm  gossip 
november 2014 by mpm
Searching in Unstructured Overlays Using Local Knowledge and Gossip
This paper analyzes a class of dissemination algorithms for the discovery of distributed contents in Peer-to-Peer unstructured overlay networks. The algorithms are a mix of protocols employing local knowledge of peers' neighborhood and gossip. By tuning the gossip probability and the depth k of the k-neighborhood of which nodes have information, we obtain different dissemination protocols employed in literature over unstructured P2P overlays. The provided analysis and simulation results confirm that, when properly configured, these schemes represent a viable approach to build effective P2P resource discovery in large-scale, dynamic distributed systems
gossip  search  p2p  overlay 
march 2014 by mpm
Serf
Serf is a decentralized solution for service discovery and orchestration that is lightweight, highly available, and fault tolerant
discovery  gossip 
november 2013 by mpm
Adaptive Push-Then-Pull Gossip Algorithm for Scale-free Networks
Real life networks are generally modelled as scale free networks. Information diffusion in such networks in decentralised environment is a difficult and resource consuming affair. Gossip algorithms have come up as a good solution to this problem. In this paper, we have proposed Adaptive First Push Then Pull gossip algorithm. We show that algorithm works with minimum cost when the transition round to switch from Adaptive Push to Adaptive Pull is close to Round(log(N)). Furthermore, we compare our algorithm with Push, Pull and First Push Then Pull and show that the proposed algorithm is the most cost efficient in Scale Free networks
gossip 
october 2013 by mpm
GEMS: Gossip-Enabled Monitoring Service for Scalable Heterogeneous Distributed Systems
We present experiments and analytical projections demonstrating scalability, fast response times and low resource utilization requirements, making GEMS a potent solution for resource monitoring in distributed computing
gossip  protocol  monitoring 
november 2012 by mpm
Chinese-Whispers
A generic gossip based state replication and failure detection service. The network transport is UDP unicast
java  consistency  base  gossip 
november 2012 by mpm
SWIM: Scalable Weakly-consistent Infection-style Process Group Membership Protocol
The SWIM effort is motivated by the unscalability of traditional heart-beating protocols, which either impose network loads that grow quadratically with group size, or compromise response times or false positive frequency w.r.t. detecting process crashes
gossip 
june 2011 by mpm
Buffer Management in Probabilistic Peer-to-Peer Communication Protocols
We examine how the buffer size should be chosen to challenge the multiple delivery problem
gossip  alm 
june 2011 by mpm
Gossip-Based Broadcast
This chapter provides an introduction to gossip-based broadcast on largescale unstructured peer-to-peer overlay networks: it surveys the main results in the field, discusses techniques to build and maintain the overlays that support efficient dissemination strategies, and provides an in-depth discussion and experimental evaluation of two concrete protocols, named HyParView and Plumtree
gossip  overlay  alm 
june 2011 by mpm
T-Man: Gossip-based overlay topology management
In this paper we propose a generic protocol, T-Man, for constructing and maintaining a large class of topologies
overlay  gossip 
june 2011 by mpm
Lightweight probabilistic broadcast
This paper presents Lightweight Probabilistic Broadcast (lpbcast), a novel gossip-based broadcast algorithm which preserves the inherent throughput scalability of traditional gossip-based algorithms and adds a notion of membership management scalability: every process only knows a random subset of fixed size of the processes in the system.
gossip  alm 
june 2011 by mpm
Gossip versus Deterministic Flooding: Low Message Overhead and High Reliability for Broadcasting on Small Networks
We present a protocol that superficially resembles rumor mongering but is deterministic. We show that this new protocol has most of the same attractions as rumor mongering
gossip  alm 
june 2011 by mpm
A Case for End System Multicast
In this paper, we study these performance concerns in the context of the Narada protocol. In Narada, end systems selforganize into an overlay structure using a fully distributed protocol. Further, end systems attempt to optimize the e#ciency of the overlay by adapting to network dynamics and by considering application level performance
gossip  overlay  alm 
june 2011 by mpm
NeEM: Network-friendly Epidemic Multicast
The NeEM library provides an implementation of epidemic multicast (also called probabilistic or gossip-based) in wide-area networks by using multiple TCP/IP connections in a non-blocking fashion. The resulting overlay network is automatically managed by the protocol.
java  gossip  protocol 
march 2009 by mpm

Copy this bookmark:



description:


tags: