ﻻ يوجد ملخص باللغة العربية
In this paper, we propose a new construction of constantdegree expanders motivated by their application in P2P overlay networks and in particular in the design of robust trees overlay. Our key result can be stated as follows. Consider a complete binary tree T and construct a random pairing {Pi} between leaf nodes and internal nodes. We prove that the graph GPi obtained from T by contracting all pairs (leaf-internal nodes) achieves a constant node expansion with high probability. The use of our result in improving the robustness of tree overlays is straightforward. That is, if each physical node participating to the overlay manages a random pair that couples one virtual internal node and one virtual leaf node then the physical-node layer exhibits a constant expansion with high probability. We encompass the difficulty of obtaining this random tree virtualization by proposing a local, selforganizing and churn resilient uniformly-random pairing algorithm with O(log2 n) running time. Our algorithm has the merit to not modify the original tree virtual overlay (we just control the mapping between physical nodes and virtual nodes). Therefore, our scheme is general and can be applied to a large number of tree overlay implementations. We validate its performances in dynamic environments via extensive simulations.
We present improved distributed algorithms for triangle detection and its variants in the CONGEST model. We show that Triangle Detection, Counting, and Enumeration can be solved in $tilde{O}(n^{1/2})$ rounds. In contrast, the previous state-of-the-ar
An $(epsilon,phi)$-expander decomposition of a graph $G=(V,E)$ is a clustering of the vertices $V=V_{1}cupcdotscup V_{x}$ such that (1) each cluster $V_{i}$ induces subgraph with conductance at least $phi$, and (2) the number of inter-cluster edges i
The performance of distributed and data-centric applications often critically depends on the interconnecting network. Applications are hence modeled as virtual networks, also accounting for resource demands on links. At the heart of provisioning such
In this note, we study the expander decomposition problem in a more general setting where the input graph has positively weighted edges and nonnegative demands on its vertices. We show how to extend the techniques of Chuzhoy et al. (FOCS 2020) to thi
The minimum spanning tree (MST) construction is a classical problem in Distributed Computing for creating a globally minimized structure distributedly. Self-stabilization is versatile technique for forward recovery that permits to handle any kind of