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

60th IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： Balliu, Alkida Brandt, Sebastian Hirvonen, Juho Olivetti, Dennis Rabie, Mikael Suomela, Jukka Aalto Univ Espoo Finland Swiss Fed Inst Technol Zurich Switzerland Sorbonne Univ LIP6 Paris France

ISBN: (纸本)9781728149523

There are distributed graph algorithms for finding maximal matchings and maximal independent sets in O(Delta + log* n) communication rounds;here n is the number of nodes and Delta is the maximum degree. The lower bound by Linial (1987, 1992) shows that the dependency on n is optimal: these problems cannot be solved in o(log* n) rounds even if Delta = 2. However, the dependency on Delta is a long-standing open question, and there is currently an exponential gap between the upper and lower bounds. We prove that the upper bounds are tight. We show that maximal matchings and maximal independent sets cannot be found in o(Delta + log log n/log log log n) rounds with any randomized algorithm in the LOCAL model of distributed computing. As a corollary, it follows that there is no deterministic algorithm for maximal matchings or maximal independent sets that runs in o(Delta + log n/log log n) rounds;this is an improvement over prior lower bounds also as a function of n.

关键词： Maximal matching maximal independent set distributed graph algorithms lower bounds

来源：评论

学校读者我要写书评

暂无评论

Improved distributed Approximations for Minimum-Weight Two-Edge-Connected Spanning Subgraph 19

Improved Distributed Approximations for Minimum-Weight Two-E...

引用

38th ACM Symposium on Principles of distributed Computing (PODC)

作者： Dory, Michal Ghaffari, Mohsen Technion Haifa Israel Swiss Fed Inst Technol Zurich Switzerland

ISBN: (纸本)9781450362177

The minimum-weight 2-edge-connected spanning subgraph (2-ECSS) problem is a natural generalization of thewell-studied minimumweight spanning tree (MST) problem, and it has received considerable attention in the area of network design. The latter problem asks for a minimum-weight subgraph with an edge connectivity of 1 between each pair of vertices while the former strengthens this edge-connectivity requirement to 2. Despite this resemblance, the 2-ECSS problem is considerably more complex than MST. While MST admits a linear-time centralized exact algorithm, 2-ECSS is NP-hard and the best known centralized approximation algorithm for it (that runs in polynomial time) gives a 2-approximation. In this paper, we give a deterministic distributed algorithm with round complexity of (O) over tilde (D+root n) that computes a (9+epsilon)-approximation of 2-ECSS, for any constant epsilon > 0. Up to logarithmic factors, this complexity matches the (Omega) over tilde (D + root n) lower bound that can be derived from the technique of Das Sarma et al. [STOC'11], as shown by Censor-Hillel and Dory [OPODIS'17]. Our result is the first distributed constant approximation for 2-ECSS in the nearly optimal time and it improves on a recent randomized algorithm of Dory [PODC'18], which achieved an O(log n)-approximation in (O) over tilde (D + root n) rounds. We also present an alternative algorithm for O(log n)-approximation, whose round complexity is linear in the low-congestion shortcut parameter of the network-following a framework introduced by Ghaffari and Haeupler [SODA'16]. This algorithm has round complexity (O) over tilde (D + root n) in worst-case networks but it provably runs much faster in many well-behaved graph families of interest. For instance, it runs in (O) over tilde (D) time in planar networks and those with bounded genus, bounded path-width or bounded tree-width.

关键词： distributed graph algorithms approximation algorithms distributed network design k-edge-connectivity

来源：评论

学校读者我要写书评

暂无评论

On the Complexity of distributed Splitting Problems 19

On the Complexity of Distributed Splitting Problems

引用

38th ACM Symposium on Principles of distributed Computing (PODC)

作者： Bamberger, Philipp Ghaffari, Mohsen Kuhn, Fabian Maus, Yannic Uitto, Jara Univ Freiburg Freiburg Germany Swiss Fed Inst Technol Zurich Switzerland Technion Haifa Israel

ISBN: (纸本)9781450362177

One of the fundamental open problems in the area of distributed graph algorithms is whether randomization is needed for efficient symmetry breaking. While there are poly logn-time randomized algorithms for all the classic symmetry breaking problems, for many of them, the best deterministic algorithms are almost exponentially slower. The following basic local splitting problem, which is known as weak splitting, takes a central role in this context: Each node of a graph G = (V, E) has to be colored red or blue such that each node of sufficiently large degree has at least one neighbor of each color. Ghaffari, Kuhn, and Maus [STOC '17] showed that this seemingly simple problem is complete w.r.t. the above fundamental open question in the following sense: If there is an efficient poly logn-time determinstic distributed algorithm for weak splitting, then there is such an algorithm for all locally checkable graph problems for which an efficient randomized algorithm exists. We investigate the distributed complexity of weak splitting and some closely related problems and we in particular obtain the following results: center dot We obtain efficient algorithms for special cases of weak splitting in nearly regular graphs. We show that if delta = Omega(log n) and Delta are the minimum and maximum degrees of G, weak splitting can be solved deterministically in time O(Delta/delta center dot poly(log n)). Further, if delta = Omega(log log n) and Delta <= 2(epsilon delta), the time complexity is O(Delta/delta center dot poly(log log n)). center dot We prove that the following two related problems are also complete in the same sense: (I) Color the nodes of a graph with C <= poly log n colors such that each node with a sufficiently large polylogarithmic degree has at least 2 log n different colors among its neighbors, and (II) Color the nodes with a large constant number of colors so that for each node of a sufficiently large at least logarithmic degree d(v), the number of neighbors o

关键词： distributed graph algorithms weak splitting LOCAL Model distributed symmetry breaking randomness

来源：评论

学校读者我要写书评

暂无评论

Synchronous t-Resilient Consensus in Arbitrary graphs 1

引用

21st International Symposium on Stabilization, Safety, and Security of distributed Systems (SSS)

作者： Castaneda, Armando Fraigniaud, Pierre Paz, Ami Rajsbaum, Sergio Roy, Matthieu Travers, Corentin Univ Nacl Autonoma Mexico Mexico City DF Mexico CNRS Paris France Univ Paris Paris France UNAM CONACYT CNRS Lab Solomon Lefschetz UMI LaSoL Cuernavaca Morelos Mexico Univ Toulouse LAAS CNRS CNRS Toulouse France CNRS Bordeaux France Univ Bordeaux Bordeaux France

ISBN: (数字)9783030349929

ISBN: (纸本)9783030349929;9783030349912

We study the number of rounds needed to solve consensus in a synchronous network G where at most t nodes may fail by crashing. This problem has been thoroughly studied when G is a complete graph, but very little is known when G is arbitrary. We define a notion of radius that considers all ways in which t nodes may crash, and present an algorithm that solves consensus in radius rounds. Then we derive a lower bound showing that our algorithm is optimal for vertex-transitive graphs, among oblivious algorithms.

关键词： Crash failures Consensus Combinatorial topology distributed graph algorithms

来源：评论

学校读者我要写书评

暂无评论

A Sharp Threshold Phenomenon for the distributed Complexity of the Lovasz Local Lemma 19

A Sharp Threshold Phenomenon for the Distributed Complexity ...

引用

38th ACM Symposium on Principles of distributed Computing (PODC)

作者： Brandt, Sebastian Maus, Yannic Uitto, Jara Swiss Fed Inst Technol Zurich Switzerland Technion Haifa Israel Univ Freiburg Freiburg Germany

ISBN: (纸本)9781450362177

The Lovasz Local Lemma (LLL) says that, given a set of bad events that depend on the values of some random variables and where each event happens with probability at most p and depends on at most d other events, there is an assignment of the variables that avoids all bad events if the LLL criterion ep(d + 1) < 1 is satisfied. Nowadays, in the area of distributed graph algorithms it has also become a powerful framework for developing-mostly randomizedalgorithms. A classic result by Moser and Tardos yields an O(log(2) n) algorithm for the distributed Lovasz Local Lemma [JACM'10] if ep(d + 1) < 1 is satisfied. Given a stronger criterion, i.e., demanding a smaller error probability, it is conceivable that we can find better algorithms. Indeed, for example Chung, Pettie and Su [PODC'14] gave anO(log(epd2) n) algorithm under the epd(2) < 1 criterion. Going further, Ghaffari, Harris and Kuhn introduced an 2(O)(root log log n) time algorithm given d(8)p = O(1) [FOCS'18]. On the negative side, Brandt et al. and Chang et al. showed that we cannot go below Omega(log logn) (randomized) [STOC'16] and Omega(logn) (deterministic) [FOCS'16], respectively, under the criterion p <= 2(-d). Furthermore, there is a lower bound of Omega(log* n) that holds for any criterion. In this paper, we study the dependency of the distributed complexity of the LLL problem on the chosen LLL criterion. We show that for the fundamental case of each random variable of the considered LLL instance being associated with an edge of the input graph, that is, each random variable influences at most two events, a sharp threshold phenomenon occurs at p <= 2(-d) : we provide a simple deterministic (!) algorithm that matches the Omega(log* n) lower bound in bounded degree graphs, if p < 2(-d), whereas for p = 2(-d), the Omega(log logn) randomized and the Omega(logn) deterministic lower bounds hold. In many applications variables affect more than two events;our main contribution is to extend our algorithm to the c

关键词： Lovasz Local Lemma distributed graph algorithms

来源：评论

学校读者我要写书评

暂无评论

A Simple Deterministic distributed MST Algorithm with Near-Optimal Time and Message Complexities

引用

JOURNAL OF THE ACM 2020年第2期67卷 13-13页

作者： Elkin, M. Ben Gurion Univ Negev Dept Comp Sci Beer Sheva Israel

The distributed minimum spanning tree (MST) problem is one of the most central and fundamental problems in distributed graph algorithms. Kutten and Peleg devised an algorithm with running time O(D + root n . log* n), where D is the hop diameter of the input n-vertexm-edge graph, and with message complexity O(m + n(3/2)). Peleg and Rubinovich showed that the running time of the algorithm of Kutten and Peleg is essentially tight and asked if one can achieve near-optimal running time together with near-optimal message complexity. In a recent breakthrough, Pandurangan et al. answered this question in the affirmative and devised a randomized algorithm with time (O) over tilde (D + root n) and message complexity (O) over tilde (m). They asked if such a simultaneous time- and message optimality can be achieved by a deterministic algorithm. In this article, building on the work of Pandurangan et al., we answer this question in the affirmative and devise a deterministic algorithm that computes MST in time O((D + root n) . logn) using O(m . logn + n logn . log* n) messages. The polylogarithmic factors in the time and message complexities of our algorithm are significantly smaller than the respective factors in the result of Pandurangan et al. In addition, our algorithm and its analysis are very simple and self-contained as opposed to rather complicated previous sublinear-time algorithms. Finally, we use our new algorithm to devise a randomized MST algorithm with running time (O) over tilde( mu(G, omega) + root n) and message complexity (O) over tilde(vertical bar E vertical bar), where mu-radius mu(G, omega) <= D is a graph parameter, which is typically much smaller than D. This improves a previous bound from Elkin.

关键词： distributed graph algorithms minimum spanning tree

来源：评论

学校读者我要写书评

暂无评论

Message reduction in the LOCAL model is a free lunch 33

Message reduction in the LOCAL model is a free lunch

引用

33rd International Symposium on distributed Computing, DISC 2019

作者： Bitton, Shimon Emek, Yuval Izumi, Taisuke Kutten, Shay Technion – Israel Institute of Technology Haifa Israel Nagoya Institute of Technology Japan

ISBN: (纸本)9783959771269

A new spanner construction algorithm is presented, working under the LOCAL model with unique edge IDs. Given an n-node communication graph, a spanner with a constant stretch and O(n1+Ε) edges (for an arbitrarily small constant Ε > 0) is constructed in a constant number of rounds sending O(n1+Ε) messages whp. Consequently, we conclude that every t-round LOCAL algorithm can be transformed into an O(t)-round LOCAL algorithm that sends O(t · n1+Ε) messages whp. This improves upon all previous message-reduction schemes for LOCAL algorithms that incur a logΩ(1) n blow-up of the round complexity. © Shimon Bitton, Yuval Emek, Taisuke Izumi, and Shay Kutten.

关键词： distributed graph algorithms LOCAL model Message complexity Spanner

来源：评论

学校读者我要写书评

暂无评论

Fast distributed algorithms for Connectivity and MST in Large graphs

引用

ACM TRANSACTIONS ON PARALLEL COMPUTING 2018年第1期5卷 4.1-4.22页

作者： Pandurangan, Gopal Robinson, Peter Scquizzato, Michele Univ Houston Dept Comp Sci Houston TX 77004 USA Royal Holloway Univ London London England McMaster Univ Dept Comp & Software Hamilton ON L8S 4K1 Canada KTH Royal Inst Technol Sch Elect Engn & Comp Sci SE-10044 Stockholm Sweden

Motivated by the increasing need to understand the algorithmic foundations of distributed large-scale graph computations, we study a number of 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 result is an (almost) optimal distributed randomized algorithm for graph connectivity. Our algorithm runs in (O) over tilde (n/k(2)) rounds ((O) over tilde notation hides a polylog(n) factor and an additive polylog(n) term). This improves over the best previously known bound of (O) over tilde (n/k) [Klauck et al., SODA 2015] and is optimal (up to a polylogarithmic factor) in light of an existing lower bound of (Omega) over tilde (n/k(2)). Our improved algorithm uses a bunch of techniques, including linear graph sketching, that prove useful in the design of efficient distributed graph algorithms. Using the connectivity algorithm as a building block, we then present fast randomized algorithms for computing minimum spanning trees, (approximate) min-cuts, and for many graph verification problems. All these algorithms take (O) over tilde (n/k(2)) rounds and are optimal up to polylogarithmic factors. We also show an almost matching lower bound of (Omega) over tilde (n/k(2)) rounds for many graph verification problems by leveraging lower bounds in random-partition communication complexity.

关键词： distributed graph algorithms graph sketching graph connectivity minimum spanning trees

来源：评论

学校读者我要写书评

暂无评论

Improved distributed Delta-Coloring 18

Improved Distributed Delta-Coloring

引用

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

作者： Ghaffari, Mohsen Hirvonen, Juho Kuhn, Fabian Maus, Yannic Swiss Fed Inst Technol Zurich Switzerland Univ Freiburg Freiburg Germany

ISBN: (纸本)9781450357951

We present a randomized distributed algorithm that computes a A coloring in any non-complete graph with maximum degree A > 4 in 0 (log A) + 20 (/log log n) rounds, as well as a randomized algorithm that computes a A-coloring in 0((log log n)2) rounds when A E [3, 0(1)]. Both these algorithms improve on an 0 (log3 n/log A) round algorithm of Panconesi and Srinivasan [STOC'1993], which has remained the state of the art for the past 25 years. Moreover, the latter algorithm gets (exponentially) closer to an Q (log log n) round lower bound of Brandt et al. [STOC'16].

关键词： distributed computing distributed graph algorithms graph coloring

来源：评论

学校读者我要写书评

暂无评论

On Local distributed Sampling and Counting 18

On Local Distributed Sampling and Counting

引用

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

作者： Feng, Weiming Yin, Yitong Nanjing Univ State Key Lab Novel Software Technol Nanjing Jiangsu Peoples R China

ISBN: (纸本)9781450357951

In classic distributed graph problems, each instance on a graph specifies a space of feasible solutions (e.g. all proper (Delta + 1)-list-colorings of the graph), and the task of distributed algorithm is to construct a feasible solution using local information. We study distributed sampling and counting problems, in which each instance specifies a joint distribution of feasible solutions. The task of distributed algorithm is to sample from this joint distribution, or to locally measure the volume of the probability space via the marginal probabilities. The latter task is also known as inference, which is a local counterpart of counting. For self-reducible classes of instances, the following equivalences are established in the LOCAL model up to polylogarithmic factors: For all joint distributions, approximate inference and approximate sampling are computationally equivalent. For all joint distributions defined by local constraints, exact sampling is reducible to either one of the above tasks. If further, sequentially constructing a feasible solution is trivial locally, then all above tasks are easy if and only if the joint distribution exhibits strong spatial mixing. Combining with the state of the arts of strong spatial mixing, we obtain efficient sampling algorithms in the LOCAL model for various important sampling problems, including: an O(root Delta log(3) n)-round algorithm for exact sampling matchings in graphs with maximum degree Delta, and an O(log(3) n)-round algorithm for sampling according to the hardcore model (weighted independent sets) in the uniqueness regime, which along with the Omega(diam) lower bound in [3] for sampling according to the hardcore model in the non-uniqueness regime, gives the first computational phase transition for distributed sampling.

关键词： distributed graph algorithms local computation sampling algorithms Gibbs distribution strong spatial mixing

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：