Connected Components (CC) computation is a fundamental graph analytics kernel. While BFS-sampling has emerged as the state-of-the-art approach for power-law graphs, its performance in existing implementations is severely limited by inheriting unnecessary BFS semantics. The core issue is a fundamental mismatch: BFS requires strict level-synchronization to compute shortest paths, while CC only needs eventual label consistency without ordering constraints. This semantic mismatch manifests as three critical bottlenecks: (i) severe load imbalance from vertex-centric task allocation, which fails to distribute the massive workload of high-degree hub vertices; (ii) redundant writes from dynamic push/pull mode switching, which necessitates costly frontier reconstruction; and (iii) redundant synchronization and computation from enforcing BFS’s strict ordering guarantees, which are superfluous for CC computation. We introduce FastCC , a lightweight multiprocess system-algorithm co-designed solution that breaks this semantic mismatch. The cornerstone of our approach is the strategic decision to fix the highest-degree vertex as the BFS root, creating a predictable computation topology. This enables three synergistic innovations: (1) hybrid task partitioning that employs edge-centric allocation in the critical first iteration to eliminate load imbalance at its source; (2) predictable mode switching that leverages the deterministic computation graph to bypass expensive frontier reconstruction; and (3) lightweight, custom synchronization primitives that relax BFS’s strict ordering to match CC’s eventual consistency requirements, while allowing earlier label propagation within the same iteration to reduce the overall computational workload. Extensive evaluation on large-scale real-world and synthetic power-law graphs demonstrates that FastCC achieves significant performance improvements, with speedups of 10.6-55.5× faster (average: 37.8×) over state-of-the-art CC implementations including ConnectIt and vGraph. FastCC also reduces peak memory footprint by up to 2.87× and exhibits superior, more predictable scalability. The practical efficacy of our approach is validated by its deployment as the core engine in a top-ranked GreenGraph500 solution.

Distributed deep neural network training necessitates efficient GPU collective communications, which are inherently susceptible to deadlocks. GPU collective deadlocks arise easily in distributed deep learning applications when multiple collectives circularly wait for each other. GPU collective deadlocks pose a significant challenge to the correct functioning and efficiency of distributed deep learning, and no general effective solutions are currently available. Only in specific scenarios, ad-hoc methods, making an application invoke collectives in a consistent order across GPUs, can be used to prevent circular collective dependency and deadlocks.

Diffusion models have been widely adopted in image and language generation and are now being applied to reinforcement learning. However, the application of diffusion models in offline cooperative Multi-Agent Reinforcement Learning (MARL) remains limited. Although existing studies explore this direction, they suffer from scalability or poor cooperation issues due to the lack of design principles for diffusion-based MARL. The Individual-Global-Max (IGM) principle is a popular design principle for cooperative MARL. By satisfying this principle, MARL algorithms achieve remarkable performance with good scalability. In this work, we extend the IGM principle to the Individual-Global-identically-Distributed (IGD) principle. This principle stipulates that the generated outcome of a multi-agent diffusion model should be identically distributed as the collective outcomes from multiple individual-agent diffusion models. We propose DoF, a diffusion factorization framework for Offline MARL. It uses noise factorization function to factorize a centralized diffusion model into multiple diffusion models. We theoretically show that the noise factorization functions satisfy the IGD principle. Furthermore, DoF uses data factorization function to model the complex relationship among data generated by multiple diffusion models. Through extensive experiments, we demonstrate the effectiveness of DoF. The source code is available at [https://github.com/xmu-rl-3dv/DoF](https://github.com/xmu-rl-3dv/DoF).

Intrusion detection is a crucial aspect of modern cybersecurity, aimed at identifying and responding to potential security threats within computer systems , networks, and applications. One of the major challenges faced by intrusion detection systems is the accurate detection and response to attack traffic, which is typically much lower in volume compared to normal traffic. This challenge becomes even more pronounced when the attack traffic is further classified into different attack categories, which may suffer from more severe data imbalance. To address these challenges, we present a novel approach to intrusion detection using a Multi-task Feature Fusion Pseudo-Siamese Network (MF2POSE) and a Category-distance Promotion Loss (CP Loss). The proposed MF2POSE leverages the Pseudo-Siamese Network (POSE-Net), which incorporates both a main network and a siamese network, to simultaneously perform binary-class and multi-class classification of the traffic. Furthermore, the Multi-task Feature Fusion (MF2) module enhances the multi-class classification performance of the main network by incorporating multi-scale internal features from the siamese network. Additionally, the CP Loss is introduced to aggregate the internal feature from the main network belonging to the same category, and separate the internal feature belonging to the different categories. We have conducted comprehensive experiments across two popular intrusion detection datasets, and the experimental results demonstrate the superior performance of our MF2POSE compared to existing state-of-the-art techniques, particularly in multi-class classification scenarios.

Cyber ranges require networked applications to test cyberspace events effectively. As testing becomes more advanced, it involves multiple real-world applications with flexible execution orders. However, it is increasingly challenging to orchestrate large-scale, chained, and heterogeneous Internet applications. State-of-the-art orchestration techniques face scalability issues due to inefficient representation models and entangled scheduling of events and applications. To address these issues, we present Wukong, a disentangled orchestration system in cyber ranges that disaggregates the scheduling and execution of workflows and their applications in a decentralized coordination approach. First, we overcome the heterogeneity of events with a workflow model that encodes event chains with compositional Directed Acyclic Graphs (DAGs) and unified event triggers. Second, Wukong disaggregates the execution of DAGs and applications with push-pull decentralized coordination over distributed agents. Our evaluation of Wukong on a real-world cyber range demonstrates its expressive, scalable, and efficient abilities for automatically emulating diverse event chains. The storage footprint of compositional modeling is up to 57 times smaller than that of baseline models. Wukong's response delay is 1.52 to 2.74 times shorter than state-of-the-art orchestration engines, and the scheduling delay is up to 2.16 times smaller than the baseline approach.

With the increasing volumes of data samples and deep neural network (DNN) models, efficiently scaling the training of DNN models has become a significant challenge for server clusters with AI accelerators in terms of memory and computing efficiency. Existing parallelism schemes can be broadly classified into three categories: data parallelism (splitting data samples), model parallelism (splitting model parameters), and pipeline model parallelism (splitting model layers). Hybrid approaches split data and models, offering a comprehensive solution for parallel training. However, these methods encounter limitations in efficiently scaling larger models across more computing nodes, as they incur substantial memory constraints that affect training efficiency and overall throughput. In this paper, we proposeHIPPIE, a hybrid parallel training framework designed to enhance memory efficiency and scalability of large DNN training. First, to evaluate the optimization effect more reasonably, we propose an index ofMemory Efficiency(ME) to quantify the tradeoff between throughput and memory overhead. Second, driven by the informed ME optimization objective, we automatically partition the pipeline to balance the throughput and memory. Third, we optimize the model training process via a novel hybrid parallel scheduler that improves the throughput and scalability by informed pipeline scheduling and communication scheduling with gradient-hidden optimization. Experiments on various models show thatHIPPIEachieves above 90% scaling efficiency on a 16-GPU platform. Moreover,HIPPIEincreases throughput by up to 80%, while saving 57% of memory overhead and achieving 4.18× memory-efficiency improvement.

Network traffic classification is important for network security and management. State-of-the-art classifiers use deep learning techniques to automatically extract feature vectors from the traffic, which however lose important context of the communication sessions and encapsulated text semantics. In this paper, we present a Multi-Modal Classification method named MTCM to systematically exploit the context for the classification task. We build an adaptive context-aware feature extraction framework over varying-length and dynamic packet sequences, based on the attention-aware graph neural networks and BERT. We next automatically fusion multimodal features with the Multi-Layer Perception (MLP) that unifies the graph and semantic features for the packet stream. Extensive evaluation with real-world application and abnormal network datasets show that MTCM outperforms state- of-the-art deep learning methods, and is robust for different classes of traffic data sets.

Multi-agent systems are characterized by environmental uncertainty, varying policies of agents, and partial observability, which result in significant risks. In the context of Multi-Agent Reinforcement Learning (MARL), learning coordinated and decentralized policies that are sensitive to risk is challenging. To formulate the coordination requirements in risk-sensitive MARL, we introduce the Risk-sensitive Individual-Global-Max (RIGM) principle as a generalization of the Individual-Global-Max (IGM) and Distributional IGM (DIGM) principles. This principle requires that the collection of risk-sensitive action selections of each agent should be equivalent to the risk-sensitive action selection of the central policy. Current MARL value factorization methods do not satisfy the RIGM principle for common risk metrics such as the Value at Risk (VaR) metric or distorted risk measurements. Therefore, we propose RiskQ to address this limitation, which models the joint return distribution by modeling quantiles of it as weighted quantile mixtures of per-agent return distribution utilities. RiskQ satisfies the RIGM principle for the VaR and distorted risk metrics. We show that RiskQ can obtain promising performance through extensive experiments. The source code of RiskQ is available in https://github.com/xmu-rl-3dv/RiskQ.

Distributed data-parallel training (DDP) is prevalent in large-scale deep learning. To increase the training throughput and scalability, high-performance collective communication methods such as AllReduce have recently proliferated for DDP use. However, these approaches require long communication periods with increasing model sizes. Collective communication transmits many sparse gradient values that can be efficiently compressed to reduce the required training time. State-of-the-art compression approaches do not provide mergeable compression for AllReduce and lack convergence bounds. We present a sparse sketch reducer (S2Reducer), a sparsity-preserving sketch-based collective communication method. S2Reducer preserves gradient sparsity and reduces communication costs via a bitmap informed count sketch structure and adapts to efficient AllReduce operators. We tune the count sketch organization to minimize the hash conflicts in a fixed-size budget. We prove that our method has the same convergence rate as vanilla data-parallel training and a much smaller communication overhead than those of state-of-the-art methods. We implement a GPU-accelerated S2Reducer for the Ring AllReduce-based DDP system. We perform extensive evaluations against four state-of-the-art methods across seven deep learning models. Our results show that S2Reducer converges to the same accuracy as that of state-of-the-art approaches while reducing the sparse communication overhead by up to 86% and achieving a speedup of up to$3.5\times $in distributed training.

Graph neural networks (GNNs) have been successfully applied to many important application domains on graph data. As graphs become increasingly large, existing GNN training frameworks typically use mini-batch sampling during feature aggregation to lower resource burdens, which unfortunately suffer from long memory accessing latency and inefficient data transfer of vertex features from CPU to GPU. This paper proposes 2PGraph, a system that addresses these limitations of mini-batch sampling and feature aggregation and supports fast and efficient single-GPU and distributed GNN training. First, 2PGraph presents a locality awareness GNN-training scheduling method that schedules the vertices based on the locality of the graph topology, significantly accelerating the sampling and aggregation, improving the data locality of vertex access, and limiting the range of neighborhood expansion. Second, 2PGraph proposes a GNN-layer-aware feature caching method on available GPU resources with a hit rate up to 100${\bf\%}$, which avoids redundant data transfer between CPU and GPU. Third, 2PGraph presents a self-dependence cluster-based graph partition method, achieving high sampling and cache efficiency for distributed environments. Experimental results on real-world graph datasets show that 2PGraph reduces memory access latency by up to 90${\boldsymbol{\%}}$mini-batch sampling, and data transfer time by up to 99${\boldsymbol{\%}}$. For distributed GNN training over an 8-GPU cluster, 2PGraph achieves up to 8.7$\times$performance speedup over state-of-the-art approaches.

Network monitoring solutions need to cope with increasing network traffic volumes, as a result, sketch-based monitoring methods have been extensively studied to trade accuracy for memory scalability and storage reduction. However, sketches are sensitive to skewness in network flow distributions due to hash collisions, and need complicated performance optimization to adapt to line-rate packet streams. We provide Jellyfish, an efficient sketch method that performs one-pass clustering over the network stream. One-pass clustering is realized by adapting the monitoring granularity from the whole network flow to fragments called subflows, which not only reduces the ingestion rate but also provides an efficient intermediate representation for the input to the sketch. Jellyfish provides the network-flow level query interface by reconstructing the network-flow level counters by merging subflow records from the same network flow. We provide probabilistic analysis of the expected accuracy of both existing sketch methods and Jellyfish. Real-world trace-driven experiments show that Jellyfish reduces the average estimation errors by up to six orders of magnitude for per-flow queries, by six orders of magnitude for entropy queries, and up to ten times for heavy-hitter queries.

Distributed stochastic gradient descent (SGD) approach has been widely used in large-scale deep learning, and the gradient collective method is vital to ensure the training scalability of the distributed deep learning system. Collective communication such as AllReduce has been widely adopted for the distributed SGD process to reduce the communication time. However, AllReduce incurs large bandwidth resources while most gradients are sparse in many cases since many gradient values are zeros and should be efficiently compressed for bandwidth saving. To reduce the sparse gradient communication overhead, we propose Sparse-Sketch Reducer (S2 Reducer), a novel sketch-based sparse gradient aggregation method with convergence guarantees. S2 Reducer reduces the communication cost by only compressing the non-zero gradients with count-sketch and bitmap, and enables the efficient AllReduce operators for parallel SGD training. We perform extensive evaluation against four state-of-the-art methods over five training models. Our results show that S2 Reducer converges to the same accuracy, reduces 81% sparse communication overhead, and achieves 1.8× distributed training speedup compared to state-of-the-art approaches.

The Centralized Training with Decentralized Execution paradigm (CTDE), which trains policies centrally with additional information, is important for Multi-Agent Reinforcement Learning (MARL). For CTDE, value function factorization methods make use of state during training and factorize the value function into multiple local value functions for decentralized execution. These approaches do not fully consider the relational information among agents, resulting in sub-optimal models for complex tasks. To remedy this issue, we propose QRelation which is a graph neural network approach for value function factorization. It considers both the static relations (e.g., agent types) and dynamic relations (e.g., close-by). We show that QRelation can obtain better results than state-of-the-art methods on challenging StarCraft II benchmarks.

Events spreading on social media platforms reflect current public concerns and emotions among public opinions. Heterogeneous elements of social networks and the sparse context of social messages bring significant challenges to the fine-grained social event detection task. Few existing methods can learn the inherent structure and rich semantics among social messages, nor can they effectively update the detection model in a dynamic scenario for continuously coming messages. In this paper, we design a novel Multi-Semantics Heterogeneous Graph Neural Network (MSGNN) to learn social events in a continuous detection framework. We apply the heterogeneous information network (HIN) to modeling social events, considering the heterogeneous elements and meta-paths in the social event data stream. We propose a dual-level messages aggregation mechanism to aggregate semantics between heterogeneous elements, which aggregates the local features of adjacent neighboring messages from the node level and the global semantics from the meta-path level to the current message. A semantic weight is designed for messages to filter out noise under social message streams. We conduct extensive experiments on two real-world social event datasets, and the experimental results demonstrate that our proposed model outperforms state-of-the-art models.

Cyber ranges need to run versatile network applications to increase the fidelity of the tests. With the growing complexity of cyberspace events that involve tens to hundreds of diverse applications and flexible execution orders of applications, it is increasingly challenging to orchestrate large-scale, complicated chains of heterogeneous Internet applications. State-of-the-art orchestration techniques do not scale out well due to the inefficient representation model and scheduling of network-centric and correlated Internet application activities. We present a serverless-container workflow orchestration scheme called Wukong. First, we overcome the heterogeneity of events with a workflow model that encodes event chains with compositional DAGs and unified serverless-container event triggers. Second, Wukong scales the scheduling of serverless-container workflows by automatically decomposing DAGs and push-pull coordinated event executions over distributed serverless-container runtime agents. Our evaluation on a real-world cyber range shows that Wukong is expressive, scalable and efficient for automatically emulating diverse event chains, in that the compositional modeling reduces the storage footprint over 57 to 58 times compared to baseline models, the response delay of Wukong is 1.52 to 2.74 times shorter than state-of-the-art orchestration engines, and the scheduling delay is 1.14 to 2.16 times smaller than those of the baseline approach.

The factorization of state-action value functions for Multi-Agent Reinforcement Learning (MARL) is important. Existing studies are limited by their representation capability, sample efficiency, and approximation error. To address these challenges, we propose, ResQ, a MARL value function factorization method, which can find the optimal joint policy for any state-action value function through residual functions. ResQ masks some state-action value pairs from a joint state-action value function, which is transformed as the sum of a main function and a residual function. ResQ can be used with mean-value and stochastic-value RL. We theoretically show that ResQ can satisfy both the individual global max (IGM) and the distributional IGM principle without representation limitations. Through experiments on matrix games, the predator-prey, and StarCraft benchmarks, we show that ResQ can obtain better results than multiple expected/stochastic value factorization methods.

Gradient quantization has been widely used in distributed training of deep neural network (DNN) models to reduce communication costs. However, existing quantization methods overlook that gradients have a nonuniform distribution changing over time, which can lead to significant gradient variance that requires a higher number of quantization bits (and consequently higher communication cost) to keep the validation accuracy as high as stochastic gradient descent (SGD). In this paper, we propose Cluster-Aware Sketch Quantization (CASQ), a novel sketch-based gradient quantization method for SGD. CASQ models the nonuniform distribution of gradients via clustering, and adaptively allocates appropriate numbers of hash buckets based on the statistics of different clusters to compress gradients. The extensive evaluation shows that compared to existing quantization methods CASQ-based SGD (i) achieves the same validation accuracy when decreasing quantization level from 3 bits to 2 bits, and (ii) reduces the training time to convergence by up to 43% for the same training loss.

The communication among agents is important for Multi-Agent Reinforcement Learning (MARL). In this work, we propose GraphComm, a method makes use of the relation-ships among agents for MARL communication. GraphComm takes the explicit relations (e.g., agent types), which can be provided through some knowledge background, into account to better model the relationships among agents. Besides explicit relations, GraphComm considers implicit relations, which are formed by agent interactions. GraphComm use Graph Neural Networks (GNNs) to model the relational information, and use GNNs to assist the learning of agent communication. We show that GraphComm can obtain better results than state-of-the-art methods on the challenging StarCraft II unit micromanagement tasks through extensive experimental evaluation.

To cope with increasing network rates and massive traffic volumes, sketch-based methods have been extensively studied to trade accuracy for memory scalability and storage cost. However, sketches are sensitive to hash collisions due to skewed keys in real world environment, and need complicated performance control for line-rate packet streams.We present Jellyfish, a locality-sensitive sketching framework to address these issues. Jellyfish goes beyond network flow-based sketching towards fragments of network flows called subflows. First, Jellyfish splits consecutive packets from each network flow to subflow records, which not only reduces the rate contention but also provides intermediate subflow representations in form of truncated counters. Next, Jellyfish maps similar subflow records to the same bucket array and merges those from the same network flow to reconstruct the network-flow level counters. Real-world trace-driven experiments show that Jellyfish reduces the average estimation errors by up to six orders of magnitude for per-flow queries, by six orders of magnitude for entropy queries, and up to ten times for heavy-hitter queries.

Network Representation Learning embeds each node in a network into a low-dimensional real-value vector which can be used for downstream tasks such as link prediction and recommendation. Many existing approaches use unsupervised or (semi-)supervised methods to explore the network topology and learn representations from it. In contrast, we propose, reinforcement learning network representations (RLNet), which explores the idea of using reinforcement learning to learn to explore the network and to obtain network representations. Based on reward signals, RLNet learns an actor which uses a policy to determine the network navigation actions. RLNet uses node representations to parameterize its policy, and the representations are learned together with the policy. Through experiments based on multiple datasets, we show that RLNet can obtain promising results in link prediction tasks.

Network monitoring is vital in modern clouds and data center networks that need diverse traffic statistics ranging from flow size distributions to heavy hitters. To cope with increasing network rates and massive traffic volumes, sketch based approximate measurement has been extensively studied to trade the accuracy for memory and computation cost, which unfortunately, is sensitive to hash collisions.This paper presents a clustering-preserving sketch method to be resilient to hash collisions. We provide an equivalence analysis of the sketch in terms of the K-means clustering. Based on the analysis result, we cluster similar network flows to the same bucket array to reduce the estimation variance and use the average to obtain unbiased estimation. Testbed shows that the framework adapts to line rates and provides accurate query results. Real-world trace-driven simulations show that LSS remains stable performance under wide ranges of parameters and dramatically outperforms state-of-the-art sketching structures, with over 103to 105times reduction in relative errors for per-flow queries as the ratio of the number of buckets to the number of network flows reduces from 10% to 0.1%.

Many persons share with the same name. Distinguishing different persons with the same name is important but challenging. Albeit much work has been proposed for author disambiguation, most of them do not adequately consider the heterogeneous relationships among authors and papers. In our work, ambiguous names and their related information, such as papers, conferences, titles, abstracts, etc., are constructed into a heterogeneous network which consists of different edge types. To fully incorporate all the information of the constructed network, we use Generative Adversarial Networks (GAN) to learn the network representation of the heterogeneous network. Although GAN has been used in many fields such as image generation, it hasn't been used to obtain representations for the heterogeneous network. As far as we know, our work is the first work which use adversarial training to learn heterogeneous network representation. After the representations are learned, they are partitioned into different groups each representing distinct authors. After extensive experiments on three major author disambiguation datasets, we demonstrate that our method outperforms several state-of-the-art baselines in author disambiguation problem.

Online cloud services need to fulfill clients' requests scalably and fast. State-of-the-art cloud services are increasingly deployed as a distributed service mesh. Service to service communication is frequent in the mesh. Unfortunately, problematic events may occur between any pair of nodes in the mesh, therefore, it is vital to maximize the network visibility. A state-of-the-art approach is to model pairwise RTTs based on a latent factor model represented as a low-rank matrix factorization. A latent factor corresponds to a rank-1 component in the factorization model, and is shared by all node pairs. However, different node pairs usually experience a skewed set of hidden factors, which should be fully considered in the model. In this paper, we propose a skewness-aware matrix factorization method named SMF. We decompose the matrix factorization into basic units of rank-one latent factors, and progressively combine rank-one factors for different node pairs. We present a unifying framework to automatically and adaptively select the rank-one factors for each node pair, which not only preserves the low rankness of the matrix model, but also adapts to skewed network latency distributions. Over real-world RTT data sets, SMF significantly improves the relative error by a factor of 0.2 x to 10 x, converges fast and stably, and compactly captures fine-grained local and global network latency structures.

Most existing author disambiguation work relies heavily on feature engineering or cannot use multiple paper relationships. In this work, we propose a network-embedding based method for author disambiguation. For each ambiguous name, we construct networks among papers sharing an ambiguous name, and connect papers with multiple relationships (e.g., co-authoring a paper). We focus on maximizing the gap between positive paper edges and negative edges, and propose a graph coarsening technique to learn global information. Further, we design a clustering algorithm which partitions paper representations into disjoint sets such that each set contains all papers of a unique author. Through extensive experiments, we show that our method is significantly better than the state-of-the-art author disambiguation and network-embedding methods.

User-facing services deployed in data centers must respond quickly to user actions. The measurement of network latencies is of paramount importance. Recently, a new family of compact data structures has been proposed to estimate one-way latencies. In order to achieve scalability, these new methods rely on timestamp aggregation. Unfortunately, this approach suffers from serious accuracy problems in the presence of packet loss and reordering, given that a single lost or out-of-order packet may invalidate a huge number of aggregated samples. In this paper, we unify the problem to detect lost and reordered packets within the set reconciliation framework. Although the set reconciliation approach and the data structures for aggregating packet timestamps are previously known, the combination of these two principles is novel. We present a space-efficient synopsis called reconcilable difference aggregator (RDA). RDA maximizes the percentage of useful packets for latency measurement by mapping packets to multiple banks and repairing aggregated samples that have been damaged by lost and reordered packets. RDA simultaneously obtains the average and the standard deviation of the latency. We provide a formal guarantee of the performance and derive optimized parameters. We further design and implement a user-space passive latency measurement system that addresses practical issues of integrating RDA into the network stack. Our extensive evaluation shows that compared with existing methods, our approach improves the relative error of the average latency estimation in 10-15 orders of magnitude, and the relative error of the standard deviation in 0.5-6 orders of magnitude.

Geo-distributed network applications typically use relays to process and forward timely messages among clients. The state-of-the-art approaches greedily locate a relay that is closer to clients based on an overlay that favors neighbors in the immediate vicinity of the current node. Unfortunately, as clients are unknown a priori, the optimal relay is generally outside of the immediate vicinity of the current node. Consequently, the search process often terminates at a poor local minimum. In this paper, we address these challenges by designing and implementing a distributed relay-search system called MCR. In order to accurately locate a relay closer to clients, by observing that the latency space exhibits a proximity clustering phenomenon where nodes in the same cluster are typically within close proximity, we propose an overlay called MCRing that is aware of global proximity clusters. In order to scale well under dynamic relays, we maintain the proximity clusters via a gossiping-based clustering process. Furthermore, we propose a series of algorithms to accurately locate a relay that is closer to clients and satisfies the load constraints. We prove that the relay-search process achieves close to optimal results based on a doubling dimension-based analysis in an inframetric model. Finally, extensive evaluation via simulation and PlanetLab experiments shows that MCRing is able to locate near-optimal relays.

The network distance service obtains the network latency among large-scale nodes. With increasing numbers of participating nodes, the network distance service has to balance the accuracy and the scalability. The network-coordinate methods scale well by embedding the pairwise latency into a low-dimensional coordinate system. The prediction errors are iteratively optimized by adjusting the coordinates with respect to neighbors. Unfortunately, the optimization process is vulnerable to the inaccurate coordinates, leading to destabilized positions. In this paper, we propose RMF, a relative coordinate-based distributed sparse-preserving matrix-factorization method to provide guaranteed stability for the coordinate system. In RMF, each node maintains a low-rank square matrix that is incrementally adjusted with respect to its neighbors' relative coordinates. The optimization is self-stabilizing, guaranteeing to converge and not interfered by inaccurate coordinates, since the relative coordinates do not have computational errors. By exploiting the sparse structure of the square matrix, the optimization enforces the $L_{1}$ -norm regularization to preserve the sparseness of the square matrix. Simulation results and a PlanetLab-based experiment confirm that RMF converges to stable positions within 10 to 15 rounds, and decreases the prediction errors by 10% to 20%.

Latency-sensitive multiparty applications involve intensive communication between multiple participating nodes. Relays are usually adopted for matchmaking end hosts, filtering unwanted traffics, bypassing routing outages and so on. Speeding up the relay-communication becomes increasingly important to improve the QoE of clients. Currently, no rigorous guarantees have been made for the latency-optimal relay communication. We propose a novel framework to truthfully represent the relay communication in the latency space. Real-world data sets show that nearly 90% of node triples obey the average triangle inequality, while our new model allows for the asymmetry and triangle inequality violations to occur. We propose the general triangle to rigorously locate a candidate relay closer to multiple nodes, with which we systematically analyze the feasibility of finding an optimal relay node for arbitrarily sized groups. Our results show that distributed greedy methods are able to locate optimal relays with modest communication overhead and small search hops.

Bloom filters are frequently used to perform set queries that test the existence of some items. However, Bloom filters face a dilemma: the transmission bandwidth and the accuracy cannot be optimized simultaneously. This dilemma is particularly severe for transmitting Bloom filters to remote nodes when the network bandwidth is limited. We propose a novel Bloom filter BloomTree that consists of a tree-structured organization of smaller Bloom filters, each one using a set of independent hash functions. BloomTree spreads items across levels that are compressed to reduce the transmission bandwidth need. We investigate in detail under which conditions BloomTree performs better than the compressed Bloom filter and the standard Bloom filter.

Summary The problem of flash data dissemination refers to transmitting time‐critical data to a large group of distributed receivers in a timely manner, which widely exists in many mission‐critical applications and Web services. However, existing approaches for flash data dissemination fail to ensure the timely and efficient transmission, because of the unpredictability of the dissemination process. Overlay routing has been widely used as an efficient routing primitive for providing better end‐to‐end routing quality by detouring inefficient routing paths in the real networks. To improve the predictability of the flash data dissemination process, we propose a bandwidth and latency sensitive overlay routing approach named BLOR, by optimizing the overlay routing and avoiding inefficient paths in flash data dissemination. BLOR tries to select optimal routing paths in terms of network latency, bandwidth capacity, and available bandwidth in nature, which has never been studied before. Additionally, a location‐aware unstructured overlay topology construction algorithm, an unbiased top‐kdominance model, and an efficient semi‐distributed information management strategy are proposed to assist the routing optimization of BLOR. Extensive experiments have been conducted to verify the effectiveness and efficiency of the proposals with real‐world data sets. Copyright © 2014 John Wiley & Sons, Ltd.

To guarantee the reliability of distributed storage systems, erasure coding, as a redundant scheme, has received increasingly attention because it can greatly improve the space efficiency compared with the replica schemes. However, it takes a long time and consumes a lot of network bandwidth for erasure coding to repair the lost data on failed nodes. The state-of-art studies focus on the repairing optimization for the single-node-failure context. Real-world experiments have clearly shown that multi-node failures indeed happen in cloud storage systems. Borrowing single-node repairing techniques to the multi-node setting faces challenges on the efficiency. We propose a mutually cooperative recovery scheme MCRTREE based on the tree structure for multiple node failures. MCRTREE improves the bandwidth utilization and reduces the repair time by the construction of regeneration trees between each new node (denoted as newcomers) and alive nodes (denoted as providers). Further, MCRTREE reduces the size of the data volumes to be transmitted for the repair process. Numerical experiments show that MCRTREE consumes less storage cost and the maintenance bandwidth compared with other redundancy recovery schemes. Trace-driven simulation results reveal that the MCRTREE reduces the regeneration time by 30% - 50%, improves the successful regeneration probability by 10% - 20% and the data availability by 10% - 20% compared with the typical repair schemes.

Proximity ranking according to end-to-end network distances (e.g., Round-Trip Time, RTT) can reveal detailed proximity information, which is important in network management and performance diagnosis in distributed systems. However, to the best of our knowledge, there has been no similar work on this subject in the P2P computing field. We present a distributed rating method iRank, that enables proximity rankings by providing discrete ratings in a distributed manner. It formulates the proximity ranking as a rating problem that faithfully captures the proximity based on noisy distance measurements scalably and practically. The primary challenge in inferring proximity rankings is enforcing distributed ratings with complex rating policies. Our solution is based on reconstructing ratings by decomposing a centralized rating method Maximum Margin Matrix Factorization (MMMF) into independent sub-problems, that can be efficiently solved in a decentralized manner. By relaxing the dependence on infrastructure nodes that are a single point of failure and limit scalability, iRank can gracefully handle network churns. Through real network latency data sets, we demonstrate that iRank can predict ratings with low distortion, which are smaller than 20 percentage worse than the centralized method, in the context of synthetic complex rating policies.

Predicting network latencies between Internet hosts can efficiently support large-scale Internet applications, e.g., file sharing service and the overlay construction. Several study use the hyperbolic space to model the Internet dense-core and many-tendril structure. However, existing hyperbolic space based embedding approaches are not designed for accurate latency estimation in the distributed context. We present HyperSpring, which estimates latency by modelling a mass spring system in the hyperbolic similar with Vivaldi. HyperSpring adopts coordinate initialization to speed up the convergence of coordinate computation, uses multiple-round symmetric updates to escape from bad local minima, and stabilizes coordinates by compensating RTT measurements to reduce the coordinate drifts. Evaluation results based on a network trace of 226 PlanetLab nodes indicate that, compared to Euclidean-space based Vivaldi, hyperspring provides performance improvements for most nodes, and incurs slightly higher distortions for a small number of nodes.