检索结果-内蒙古大学图书馆

37th ACM SIGACT-SIGOPS Symposium on Principles of distributed Computing (PODC)

作者： Haeupler, Bernhard Hershkowitz, D. Ellis Wajc, David Carnegie Mellon Univ Pittsburgh PA 15213 USA

ISBN: (纸本)9781450357951

distributed graph algorithms that separately optimize for either the number of rounds used or the total number of messages sent have been studied extensively. However, algorithms simultaneously efficient with respect to both measures have been elusive. For example, only very recently was it shown that for Minimum Spanning Tree (MST), an optimal message and round complexity is achievable (up to polylog terms) by a single algorithm in the CONGEST model of communication. In this paper we provide algorithms that are simultaneously round- and message-optimal for a number of well-studied distributed optimization problems. Our main result is such a distributed algorithm for the fundamental primitive of computing simple functions over each part of a graph partition. From this algorithm we derive round- and message-optimal algorithms for multiple problems, including MST, Approximate Min-Cut and Approximate Single Source Shortest Paths, among others. On general graphs all of our algorithms achieve worst-case optimal (O) over tilde (D + root n) round complexity and (O) over tilde (m) message complexity. Furthermore, our algorithms require an optimal (O) over tilde (D) rounds and (O) over tilde (n) messages on planar, genus-bounded, treewidth-bounded and pathwidth-bounded graphs.(1)

关键词： distributed graph algorithms Low-congestion shortcuts CONGEST Part-wise Aggregation

来源：评论

学校读者我要写书评

暂无评论

Adaptive Runtime Features For distributed graph algorithms 25

Adaptive Runtime Features For Distributed Graph Algorithms

引用

25th IEEE International Conference on High Performance Computing, Data and Analytics (HiPC)

作者： Firoz, Jesun Sahariar Zalewski, Marcin Suetterlein, Joshua Lumsdaine, Andrew Indiana Univ Bloomington IN 47405 USA Pacific Northwest Natl Lab Seattle WA USA Univ Washington Seattle WA 98195 USA

ISBN: (纸本)9781538683866

Performance of distributed graph algorithms can benefit greatly by forming rapport between algorithmic abstraction and the underlying runtime system that is responsible for scheduling work and exchanging messages. However, due to their dynamic and irregular nature of computation, distributed graph algorithms written in different programming models impose varying degrees of workload pressure on the runtime. To cope with such vastly different workload characteristics, a runtime has to make several trade-offs. One such trade-off arises, for example, when the runtime scheduler has to choose among alternatives such as whether to execute algorithmic work, or progress the network by probing network buffers, or throttle sending messages (termed flow control). This trade-off decides between optimizing the throughput of a runtime scheduler by increasing the rate of execution of algorithmic work, and reducing the latency of the network messages. Another trade-off exists when a decision has to be made about when to send aggregated messages in buffers (message coalescing). This decision chooses between trading off latency for network bandwidth and vice versa. At any instant, such trade-offs emphasize either on improving the quantity of work being executed (by maximizing the scheduler throughput) or on improving the quality of work (by prioritizing better work). However, encoding static policies for different runtime features (such as flow control, coalescing) can prevent graph algorithms from achieving their full potentials, thus can undermine the actual performance of a distributed graph algorithm. In this paper, we investigate runtime support for distributed graph algorithms in the context of two paradigms: variants of well-known Bulk-Synchronous Parallel model and asynchronous programming model. We explore generic runtime features such as message coalescing (aggregation) and flow control and show that execution policies of these features need to be adjusted over time to make

关键词： distributed graph algorithms distributed runtimes

来源：评论

学校读者我要写书评

暂无评论

A graph Theoretic Approach for Resilient distributed algorithms 22

A Graph Theoretic Approach for Resilient Distributed Algorit...

引用

ACM Symposium on Principles of distributed Computing (PODC)

作者： Parter, Merav Weizmann Inst Sci Rehovot Israel

ISBN: (纸本)9781450392624

Following the immense recent advances in distributed networks, the explosive growth of the Internet, and our increased dependency on these infrastructures, guaranteeing the uninterrupted operation of communication networks has become a major objective in network algorithms. The modern instantiations of distributed networks, such as the Bitcoin network and cloud computing, introduce new security challenges that deserve urgent attention in both theory and practice.

关键词： distributed graph algorithms Information Theoretic Security CONGEST

来源：评论

学校读者我要写书评

暂无评论

An efficient distributed algorithm for centering a spanning tree of a biconnected graph

引用

INFORMATION PROCESSING LETTERS 1996年第3期59卷 145-150页

作者： Aranha, RFM Rangan, CP INDIAN INST TECHNOL DEPT COMP SCI & ENGNMADRAS 600036TAMIL NADUINDIA

Given a biconnected graph G with n vertices, m edges and a vertex r, the centering of a spanning tree problem asks for a spanning tree T of G with the given vertex r as center of T. In this paper we present an O(m) message complexity and O(n) time complexity distributed algorithm for centering a spanning tree of a biconnected graph.

关键词： algorithms distributed graph algorithms biconnected graphs st-numbering center spanning tree

来源：评论

学校读者我要写书评

暂无评论

On the distributed Complexity of Large-Scale graph Computations

引用

ACM TRANSACTIONS ON PARALLEL COMPUTING 2021年第2期8卷 1–28页

作者： Pandurangan, Gopal Robinson, Peter Scquizzato, Michele Univ Houston Dept Comp Sci 3551 Cullen Blvd Houston TX 77204 USA City Univ Hong Kong Dept Comp Sci Kowloon 83 Tat Chee Ave Hong Kong Peoples R China Univ Padua Dept Math Via Trieste 63 I-35121 Padua Italy

Motivated by the increasing need to understand the distributed algorithmic foundations of large-scale graph computations, we study some fundamental graph problems in a message-passing model for distributed computing where k >= 2 machines jointly perform computations on graphs with n nodes (typically, n >> k). The input graph is assumed to be initially randomly partitioned among the k machines, a common implementation in many real-world systems. Communication is point-to-point, and the goal is to minimize the number of communication rounds of the computation. Our main contribution is the General Lower Bound Theorem, a theorem that can be used to show non-trivial lower bounds on the round complexity of distributed large-scale data computations. This result is established via an information-theoretic approach that relates the round complexity to the minimal amount of information required by machines to solve the problem. Our approach is generic, and this theorem can be used in a "cookbook" fashion to show distributed lower bounds for several problems, including non-graph problems. We present two applications by showing (almost) tight lower bounds on the round complexity of two fundamental graph problems, namely, PageRank computation and triangle enumeration. These applications show that our approach can yield lower bounds for problems where the application of communication complexity techniques seems not obvious or gives weak bounds, including and especially under a stochastic partition of the input. We then present distributed algorithms for PageRank and triangle enumeration with a round complexity that (almost) matches the respective lower bounds;these algorithms exhibit a round complexity that scales superlinearly in k, improving significantly over previous results [Klauck et al., SODA 2015]. Specifically, we show the following results: PageRank: We show a lower bound of (Omega) over tilde (n/k(2)) rounds and present a distributed algorithm that computes an approxim

关键词： distributed graph algorithms PageRank triangle enumeration lower bounds

来源：评论

学校读者我要写书评

暂无评论

graph TRAVERSAL TECHNIQUES AND THE MAXIMUM FLOW PROBLEM IN distributed COMPUTATION

引用

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING 1983年第4期9卷 504-512页

作者： CHEUNG, TY Department of Computer Science University of Ottawa

This paper shows that graph traversal techniques have fundamental differences between serial and distributed computations in their behaviors, computational complexities, and effects on the design of graph algorithms. It has three major parts. Section I describes the computational environment for the design and description of distributed graph algorithms in terms of an architectural model for message exchanges. The computational complexity is measured in terms of the number of messages transmitted. Section II presents several distributed algorithms for the pure traversal, depth-first search, and breadth-first search techniques. Their complexities are also given. Through these descriptions are brought out some of the intrinsic differences in the behaviors and complexities of the fundamental traversal techniques between a serial and a distributed computation environment. Section III gives the distributed version of the Ford and Fulkerson algorithm for the maximum flow problem by means of depth-first search, the largest-augmentation search and breadth-first search. The complexities of these methods are found to be 0(f*|A|), 0((l + logM/(M-1)f*|V||A|) and O(|V|6), respectively, where f* is the maximum flow value of the problem, M is the maximum number of ucs in a cut, |V| is the number of vertices, and |A| is the number of arcs. Lastly, it is shown that the largest augmentation search may be a better method than the other two. This is contrary to the known results in serial computation.

关键词： Model distributed Computation distributed graph algorithms graph Traversal Techniques Maximum Network Flow Problem

来源：评论

学校读者我要写书评

暂无评论

Fast distributed approximation for TAP and 2-edge-connectivity

引用

distributed COMPUTING 2020年第2期33卷 145-168页

作者： Censor-Hillel, Keren Dory, Michal Technion Dept Comp Sci Haifa Israel

The tree augmentation problem (TAP) is a fundamental network design problem, in which the input is a graph G and a spanning tree T for it, and the goal is to augment T with a minimum set of edges Aug from G, such that T boolean OR Aug is 2-edge-connected. TAP has been widely studied in the sequential setting. The best known approximation ratio of 2 for the weighted case dates back to the work of Frederickson and JaJa (SIAM J Comput 10(2):270-283, 1981). Recently, a 3/2-approximation was given for unweighted TAP by Kortsarz and Nutov (ACM Trans algorithms 12(2):23, 2016). Recent breakthroughs give an approximation of 1.458 for unweighted TAP (Grandoni et al. in: Proceedings of the 50th annual ACM SIGACT symposium on theory of computing (STOC 2018), 2018), and approximations better than 2 for bounded weights (Adjiashvili in: Proceedings of the twenty-eighth annual ACM-SIAM symposium on discrete algorithms (SODA), 2017;Fiorini et al. in: Proceedings of the twenty-ninth annual ACM-SIAM symposium on discrete algorithms (SODA 2018), New Orleans, LA, USA, 2018. 10.1137/1.9781611975031.53). In this paper, we provide the first fast distributed approximations for TAP. We present a distributed 2-approximation for weighted TAP which completes in O(h) rounds, where h is the height of T. When h is large, we show a much faster 4-approximation algorithm for the unweighted case, completing in O(D+root nlog*n) rounds, where n is the number of vertices and D is the diameter of G. Immediate consequences of our results are an O(D)-round 2-approximation algorithm for the minimum size 2-edge-connected spanning subgraph, which significantly improves upon the running time of previous approximation algorithms, and an O(h(MST)+root nlog*n)-round 3-approximation algorithm for the weighted case, where h(MST) is the height of the MST of the graph. Additional applications are algorithms for verifying 2-edge-connectivity and for augmenting the connectivity of any connected spanning subgraph to 2.

关键词： distributed graph algorithms Approximation algorithms distributed network design Connectivity augmentation

来源：评论

学校读者我要写书评

暂无评论

Stability and Resilience of distributed Information Spreading in Aggregate Computing

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2023年第1期68卷 454-461页

作者： Mo, Yuanqiu Dasgupta, Soura Beal, Jacob Westlake Univ Inst Adv Technol Westlake Inst Adv Study Hangzhou 310024 Peoples R China Univ Iowa Iowa IA 52242 USA Shandong Comp Sci Ctr Shandong Prov Key Lab Comp Networks Jinan Jinan 250014 Peoples R China Raytheon BBN Technol Cambridge MA 02138 USA

Spreading informationthrough a network of devices is a core activity for most distributed systems. Self-stabilizing algorithms for information spreading are one of the key building blocks enabling aggregate computing to provide resilient coordination in open complex distributed systems. This article improves a general spreading block in the aggregate computing literature by making it resilient to network perturbations, establishes its global uniform asymptotic stability, and proves that it is ultimately bounded under persistent disturbances. The ultimate bounds depend only on the magnitude of the largest perturbation and the network diameter, and three design parameters trading off competing aspects of performance. For example, as in many dynamical systems, values leading to greater resilience to network perturbations slow convergence and vice versa.

关键词： Aggregate computing distributed graph algorithms multiagent systems nonlinear stability ultimate bounds

来源：评论

学校读者我要写书评

暂无评论

DECENTRALIZED LOW-STRETCH TREES VIA LOW DIAMETER graph DECOMPOSITIONS

引用

SIAM JOURNAL ON COMPUTING 2024年第2期53卷 247-286页

作者： Becker, Ruben Emek, Yuval Ghaffari, Mohsen Lenzen, Christoph CaFoscari Univ Venice I-30123 Venice Italy Technion Israel Inst Technol IL-3200003 Haifa Israel MIT Cambridge MA 02139 USA CISPA Helmholtz Ctr Informat Secur Saarland Informat Campus D-66123 Saarbrucken Germany

We study the problem of approximating the distances in an undirected weighted graph G by the distances in trees based on the notion of stretch. Focusing on decentralized models of computation such as the CONGEST, PRAM, and semi-streaming models, our main results are as follows: (1) We develop a simple randomized algorithm that constructs a spanning tree such that the expected stretch of every edge is O(log(3) n), where n is the number of nodes in G. If G is unweighted, then this algorithm can be implemented to run in O(hop(G)) rounds in the CONGEST model, where hop(G) is the hop-diameter of G;thus our algorithm is asymptotically optimal in this case. In the weighted case, the run-time of the algorithm matches the currently best known bound for exact single source shortest path (SSSP) computations, which despite recent progress is still separated from the lower bound of Omega(root n + hop(G)) by polynomial factors. A naive attempt to replace exact SSSP computations with approximate ones in order to improve the complexity in the weighted case encounters a fundamental challenge, as the underlying decomposition technique fails to work under distance approximation. (2) We overcome this obstacle by developing a technique termed blurry ball growing. This technique, in combination with a clever algorithmic idea of Miller, Peng, and Xu (SPAA 2013), allows us to obtain low diameter graph decompositions with small edge cutting probabilities based solely on approximate SSSP computations. (3) Using these decompositions, we in turn obtain metric tree embedding algorithms in the vein of the celebrated work of Bartal (FOCS 1996), whose computational complexity is optimal up to polylogarithmic factors not only in the CONGEST model but also in the PRAM and semi-streaming models. Our embeddings have the additional useful property that the tree can be mapped back to the original graph such that each edge is "used" only logarithmically many times. This property is of interest for capaci

关键词： distributed graph algorithms parallel graph algorithms (semi-)streaming graph algorithms metric tree embeddings low-stretch trees graph decompositions

来源：评论

学校读者我要写书评

暂无评论

An incremental distributed algorithm for computing biconnected components in dynamic graphs

引用

ALGORITHMICA 1998年第3期22卷 305-329页

作者： Swaminathan, B Goldman, KJ Washington Univ Dept Comp Sci St Louis MO 63130 USA

This paper describes a distributed algorithm for computing the biconnected components of a dynamically changing graph. Our algorithm has a worst-case communication complexity of O (b + c) messages for an edge insertion and O (b' + c) messages for an edge removal, and a worst-case time complexity of O (c) for both operations, where c is the maximum number of biconnected components in any of the connected components during the operation, b is the number of nodes in the biconnected component containing the new edge, and b' is the number of nodes in the biconnected component just before the deletion. The algorithm is presented in two stages. First, a serial algorithm is presented in which topology updates occur one at a time. Then, building on the serial algorithm, an algorithm is presented in which concurrent update requests are serialized within each connected component. The problem is motivated by the need to implement causal ordering of messages efficiently in a dynamically changing communication structure.

关键词： biconnected components distributed graph algorithms dynamic configuration

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：