mpm + overlay   34

Partisan is the design of an alternative runtime system for improved scalability and reduced latency in actor applications
erlang  actors  performance  overlay 
5 weeks ago 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
eBPF, Sockets, Hop Distance and manually writing eBPF assembly
A friend gave me an interesting task: extract IP TTL values from TCP connections established by a userspace program. This seemingly simple task quickly exploded into an epic Linux system programming hack
ebpf  networking  overlay 
april 2018 by mpm
Rendezvous Hashing
Regardless of the reason for consistent hashing’s popularity, I feel the go-to technique should instead be rendezvous hashing.
topology  overlay 
october 2017 by mpm
Find Your Place: Simple Distributed Algorithms for Community Detection
Given an underlying network, the \emph{averaging dynamics} is the following distributed process: Initially, each node locally chooses a value in {−1,1}, uniformly at random and independently of other nodes. Then, in each consecutive round, every node updates its local value to the average of its neighbors, at the same time applying an elementary, local clustering rule that only depends on the current and the previous values held by the node. Under various models of graphs with a sparse balanced cut, that include the stochastic block model, we show that the process resulting from this simple protocol produces in logarithmic time a clustering that exactly or approximately (depending on the model) reflects the underlying cut. We also prove that a natural extension of this algorithm solves the community detection problem on a regular version of the stochastic block model with more than two communities. Rather surprisingly, our results provide a rigorous evidence of the ability of natural dynamics to solve a computational problem that is non-trivial in a centralized setting.
overlay  nc 
july 2016 by mpm
Towards a Universal Approach for Monotonic Searchability in Self-Stabilizing Overlay Networks
For overlay networks, the ability to recover from a variety of problems like membership changes or faults is a key element to preserve their functionality. In recent years, various self-stabilizing overlay networks have been proposed that have the advantage of being able to recover from any illegal state. However, the vast majority of these networks cannot give any guarantees on its functionality while the recovery process is going on. We are especially interested in searchability, i.e., the functionality that search messages for a specific identifier are answered successfully if a node with that identifier exists in the network
july 2016 by mpm
Perfect Consistent Hashing
Consistent Hashing functions are widely used for load balancing across a variety of applications. However, the original presentation and typical implementations of Consistent Hashing rely on randomised allocation of hash codes to keys which results in a flawed and approximately-uniform allocation of keys to hash codes. We analyse the desired properties and present an algorithm that perfectly achieves them without resorting to any random distributions. The algorithm is simple and adds to our understanding of what is necessary to create a consistent hash function
overlay  dht 
january 2016 by mpm
Meridian: Lightweight Positioning
Meridian is a peer-to-peer overlay network for performing location-aware node and path selection in large-scale distributed systems. It provides a simple lightweight framework for keeping track of location information for participating nodes, without using virtual coordinates. Instead, it builds a distributed, failure resilient overlay graph, maintains the graph using a gossip protocol, and performs direct measurements in response to queries
overlay  nc 
november 2015 by mpm
Network Coordinate Research at Harvard
We are researching how to develop stable and accurate large-scale network coordinate systems and what one can do with such systems once they exist
overlay  nc  networking 
november 2015 by mpm
The Locator/ID Separation Protocol (LISP)
This document describes a network-layer-based protocol that enables separation of IP addresses into two new numbering spaces: Endpoint Identifiers (EIDs) and Routing Locators (RLOCs). No changes are required to either host protocol stacks or to the "core" of the Internet infrastructure. The Locator/ID Separation Protocol (LISP) can be incrementally deployed, without a "flag day", and offers Traffic Engineering, multihoming, and mobility benefits to early adopters, even when there are relatively few LISP-capable sites.
networking  addressing  overlay 
november 2015 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
Self-Healing Protocols for Connectivity Maintenance in Unstructured Overlays
In this paper, we discuss on the use of self-organizing protocols to improve the reliability of dynamic Peer-to-Peer (P2P) overlay networks. Two similar approaches are studied, which are based on local knowledge of the nodes' 2nd neighborhood. The first scheme is a simple protocol requiring interactions among nodes and their direct neighbors. The second scheme adds a check on the Edge Clustering Coefficient (ECC), a local measure that allows determining edges connecting different clusters in the network. The performed simulation assessment evaluates these protocols over uniform networks, clustered networks and scale-free networks. Different failure modes are considered. Results demonstrate the effectiveness of the proposal
overlay  fault-tolerance 
july 2015 by mpm
The State of NAT Traversal
Lots of people think NAT is a show-stopper for peer to peer communication, but it isn’t. More than 90% of NATs can be traversed, with most being traversable in reliable and deterministic ways.
networking  overlay 
september 2014 by mpm
Babel is a loop-avoiding distance-vector routing protocol for IPv6 and IPv4 with fast convergence properties. It is based on the ideas in DSDV, AODV and Cisco's EIGRP, but is designed to work well not only in wired networks but also in wireless mesh networks, and has been extended with support for overlay networks
networking  overlay 
september 2014 by mpm
Building Self-Stabilizing Overlay Networks with the Transitive Closure Framework
Overlay networks are expected to operate in hostile environments, where node and link failures are commonplace. One way to make overlay networks robust is to design self-stabilizing overlay networks, i.e., overlay networks that can handle node and link failures without any external supervision. In this paper, we first describe a simple framework, which we call the Transitive Closure Framework (TCF), for the self-stabilizing construction of an extensive class of overlay networks. Like previous se...
august 2014 by mpm
A Fast, Minimal Memory, Consistent Hash Algorithm
We present jump consistent hash, a fast, minimal memory, consistent hash algorithm that can be expressed in about 5 lines of code. In comparison to the algorithm of Karger et al., jump consistent hash requires no storage, is faster, and does a better job of evenly dividing the key space among the buckets and of evenly dividing the workload when the number of buckets changes. Its main limitation is that the buckets must be numbered sequentially, which makes it more suitable for data storage applications than for distributed web caching
overlay  algorithm 
july 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
Topology-aware Content-centric Networking
Making data the first class entity, Information-Centric Networking (ICN) replaces conventional host-to-host model with content sharing model. However, the huge amount of content and the volatility of replicas cached across the Internet pose significant challenges for addressing content only by name. In this paper, we propose a topology-aware name-based routing protocol which combines the benefits of location-oriented routing and content-centric routing together. We adopt a URL-like naming scheme, which defines register locations and content identifier. Node with copies sends Register messages towards a register using location-oriented routing protocols. All en-path routers record forwarding entries in forwarding table (FIB) as the ”bread crumb” to this content. Following the bread crumb, routers know the ”best” topology path to the available copies. An Interest is either forwarded towards a ”known”copy by the content identifier, or towards the register nodes where it would find the bread crumb to the ”best” copies. Compared with the existing flooding or name resolution methods, Our design shows a good potential in terms of scalability, availability and overhead
ccn  networking  overlay 
august 2013 by mpm
The goal of the Scalable Distributed Information Management System (SDIMS) project is to develop a "distributed operating systems control plane" that will serve as the backbone for a large-scale distributed services. SDIMS aggregates information about large-scale networked systems to provide detailed views of nearby information and rare events and summary views of common, global information.
distributed  monitoring  overlay 
december 2011 by mpm
The Totem Single-Ring Ordering and Membership Protocol
The Totem single-ring protocol supports consistent concurrent operations by placing a total order on broadcast messages.
alm  overlay 
june 2011 by mpm
A Fault-Tolerant Token based Atomic Broadcast Algorithm
This paper presents the first token based atomic broadcast algorithm that uses an unreliable failure detector instead of a group membership service
fault-tolerance  alm  overlay 
june 2011 by mpm
Census: Location-Aware Membership Management for Large-Scale Distributed Systems
We present Census, a platform for building large-scale distributed applications. Census provides a membership service and a multicast mechanism
alm  overlay 
june 2011 by mpm
A Comparative Study of Application Layer Multicast Protocols
In this paper, we describe a set of application layer multicast protocols that have been proposed in recent literature, classify them based on some properties and present a comparison of performance and applicability of these schemes
alm  overlay 
june 2011 by mpm
A Survey and Comparison of End-System Overlay Multicast Solutions Suitable for Network Centric Warfare
In this paper we describe a variety of proposed end-system multicast solutions and classify them according to characteristics such as overlay building technique, management, and scalability.
alm  overlay 
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
Network Awareness and Failure Resilience In Self-Organising Overlay Networks
In this paper, we propose an algorithm called the localiser which addresses these three key challenges. The localiser refines the overlay in a way that reflects geographic locality so as to reduce network load. Simultaneously, it helps to evenly balance the number of neighbours of each node in the overlay, thereby sharing the load evenly as well as improving the resilience to random node failures or disconnections.
overlay  fault-tolerance 
june 2011 by mpm
VRing: A Case for Building Application-Layer Multicast Rings (Rather Than Trees)
This paper presents the design, analysis and performance evaluation of VRing, a novel application-layer multicast (ALM) protocol that establishes a virtual ring as an overlay network among the multicast group members in a self-organizing and distributed manner
overlay  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
Overlay Weaver: An Overlay Construction Toolkit
Overlay Weaver is an overlay construction toolkit, which supports overlay algorithm designers in addition to application developers
dht  p2p  networking  overlay 
june 2011 by mpm
Structured Peer-to-Peer Overlay
topology  overlay 
july 2007 by mpm
The Chord/DHash Project
The Chord project aims to build scalable, robust distributed systems using peer-to-peer ideas
cluster  dht  toplogy  overlay 
july 2007 by mpm

Copy this bookmark: