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

33rd IEEE International Parallel and distributed Processing Symposium (IPDPS)

作者： Bamberger, Philipp Kuhn, Fabian Maus, Yannic Univ Freiburg Freiburg Germany

ISBN: (纸本)9781728112466

We define a generalization of local distributed graph problems to (synchronous round-based) dynamic networks and present a framework for developing algorithms for these problems. The algorithms should satisfy non-trivial guarantees in every round. The guarantees should be stronger the more stable the graph has been during the last few rounds and coincide with the definition of the static graph problem if no topological change appeared recently. Moreover, if only a constant neighborhood around some part of the graph is stable during an interval, the algorithms should quickly converge to a solution for this part of the graph that remains unchanged throughout the interval. We demonstrate our generic framework with two classic distributed graph problems, namely (degree+1)-vertex coloring and maximal independent set (MIS). To illustrate the given guarantees consider the vertex coloring problem: Any conflict between two nodes caused by a newly inserted edge is resolved within T = O(log n) rounds. During this conflict resolving both nodes always output colors that are not in conflict with their respective 'old' neighbors. The largest color that a node is allowed to output is determined by the number of distinct neighbors that it has seen in the last T rounds.

关键词： highly dynamic networks distributed graph algorithms maximal independent set (MIS) vertex coloring

来源：评论

学校读者我要写书评

暂无评论

An Automatic Speedup Theorem for distributed Problems 19

An Automatic Speedup Theorem for Distributed Problems

引用

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

作者： Brandt, Sebastian Swiss Fed Inst Technol Zurich Switzerland

ISBN: (纸本)9781450362177

Recently, Brandt et al. [STOC'16] proved a lower bound for the distributed Lovasz Local Lemma, which has been conjectured to be tight for sufficiently relaxed LLL criteria by Chang and Pettie [FOCS'17]. At the heart of their result lies a speedup technique that, for graphs of girth at least 2t + 2, transforms any t -round algorithm for one specific LLL problem into a (t - 1)-round algorithm for the same problem. We substantially improve on this technique by showing that such a speedup exists for any locally checkable problem Pi, with the difference that the problem Pi(1) the inferred (t - 1)-round algorithm solves is not (necessarily) the same problem as Pi. Our speedup is automatic in the sense that there is a fixed procedure that transforms a description for Pi into a description for Pi(1) and reversible in the sense that any (t - 1)-round algorithm for Pi(1) can be transformed into a t-round algorithm for Pi. In particular, for any locally checkable problem. with exact deterministic time complexity T (n, Delta) <= t on graphs with n nodes, maximum node degree Delta, and girth at least 2t + 2, there is a sequence of problems Pi(1), Pi(2),... with time complexities T (n, Delta) - 1, T (n, Delta) - 2,..., that can be inferred from Pi. As a first application of our generalized speedup, we solve a longstanding open problem of Naor and Stockmeyer [STOC'93]: we show that weak 2-coloring in odd-degree graphs cannot be solved in o(log*Delta) rounds, thereby providing a matching lower bound to their upper bound.

关键词： distributed graph algorithms locally checkable problems weak coloring

来源：评论

学校读者我要写书评

暂无评论

A Topological Perspective on distributed Network algorithms 26th

A Topological Perspective on Distributed Network Algorithms

引用

26th International Colloquium on Structural Information and Communication Complexity (SIROCCO)

作者： 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 CNRS Toulouse France CNRS Bordeaux France Univ Bordeaux Bordeaux France

ISBN: (纸本)9783030249212;9783030249229

More than two decades ago, combinatorial topology was shown to be useful for analyzing distributed fault-tolerant algorithms in shared memory systems and in message passing systems. In this work, we show that combinatorial topology can also be useful for analyzing distributed algorithms in networks of arbitrary structure. To illustrate this, we analyze consensus, set-agreement, and approximate agreement in networks, and derive lower bounds for these problems under classical computational settings, such as the LOCAL model and dynamic networks.

关键词： distributed computing distributed graph algorithms Combinatorial topology

来源：评论

学校读者我要写书评

暂无评论

Lower Bounds for Maximal Matchings and Maximal Independent Sets 60

Lower Bounds for Maximal Matchings and Maximal Independent S...

引用

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：