Discrepancy Analysis of a New Randomized Diffusion Algorithm

2018/02/19 by Takeharu Shiraga, Shiraga, Takeharu
Computer Science · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Parallel #Privacy-Preserving Technologies in Data #Stochastic Gradient Optimization Techniques #and Cluster Computing (cs.DC)

paper · pdf · doi:10.48550/arxiv.1802.06532

openalex publication_date 2018/02/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

For an arbitrary initial configuration of discrete loads over vertices of a distributed graph, we consider the problem of minimizing the \em discrepancy between the maximum and minimum loads among all vertices. For this problem, this paper is concerned with the ability of natural diffusion-based iterative algorithms: at each discrete and synchronous time step on an algorithm, each vertex is allowed to distribute its loads to each neighbor (including itself) without occurring negative loads or using the information of previous time steps. In this setting, this paper presents a new \em randomized diffusion algorithm like multiple random walks. Our algorithm archives O(√(d log N)) discrepancy for any d-regular graph with N vertices with high probability, while \em deterministic diffusion algorithms have Ω(d) lower bound. Furthermore, we succeed in generalizing our algorithm to any symmetric round matrix. This yields that O(√ d_max log N) discrepancy for arbitrary graphs without using the information of maximum degree d_max.

Related

• Discrete Load Balancing in Heterogeneous Networks with a Focus on Second-Order Diffusion
• Improved Analysis of Deterministic Load-Balancing Schemes
• Randomized Optimal Transport on a Graph: framework and new distance\n measures
• Diffusion Methods for Classification with Pairwise Relationships
• Speeding up random walk mixing by starting from a uniform vertex