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

38th acm symposium on principles of distributed computing (PODC)

作者： Ghaffari, Mohsen Kuhn, Fabian Swiss Fed Inst Technol CH-8092 Zurich Switzerland Univ Freiburg D-79110 Freiburg Germany

ISBN: (纸本)9781450362177

We attempt to better understand randomization in local distributed graph algorithms by exploring how randomness is used and what we can gain from it: We first ask the question of how much randomness is needed to obtain efficient randomized algorithms. We show that for all locally checkable problems with poly logn-time randomized algorithms, there are such algorithms even if either (I) there is a only a single (private) independent random bit in each poly logn-neighborhood of the graph, (II) the (private) bits of randomness of different nodes are only poly lognwise independent, or (III) there are only poly logn bits of global shared randomness (and no private randomness). Second, we study how much we can improve the error probability of randomized algorithms. For all locally checkable problems with poly logn-time randomized algorithms, we show that there are such algorithms that succeed with probability 1-n-2(epsilon(log logn)2) and more generallyT -round algorithms, for T = polylog n, with success probability 1 - n-2(epsilon log2 T). We also show that poly logn-time randomized algorithms with success probability 1 - 2(-2log epsilon) n for some epsilon > 0 can be derandomized to poly logn-time deterministic algorithms. Both of the directions mentioned above, reducing the amount of randomness and improving the success probability, can be seen as partial derandomization of existing randomized algorithms. In all the above cases, we also show that any significant improvement of our results would lead to a major breakthrough, as it would imply significantly more efficient deterministic distributed algorithms for a wide class of problems.

关键词： distributed symmetry breaking randomness shared randomness LOCAL model CONGEST model

来源：评论

学校读者我要写书评

暂无评论

distributed Minimum Degree Spanning Trees 19

Distributed Minimum Degree Spanning Trees

引用

38th acm symposium on principles of distributed computing (PODC)

作者： Dinitz, Michael Halldorsson, Magnus M. Izumi, Taisuke Newport, Calvin Johns Hopkins Univ Baltimore MD 21218 USA Reykjav Univ Reykjavik Iceland Nagoya Inst Technol Nagoya Aichi Japan Georgetown Univ Washington DC USA

ISBN: (纸本)9781450362177

The minimum degree spanning tree (MDST) problem requires the construction of a spanning tree T for graph G, such that the maximum degree of T is the smallest among all spanning trees of G. Let d be this MDST degree for a given graph. In this paper, we present a randomized distributed approximation algorithm for the MDST problem that constructs a spanning tree with maximum degree in O(d + logn). With high probability in n, the algorithm runs in O((D + root n) log(4) n) rounds, in the broadcast-CONGEST model, where D is the graph diameter and n is the graph size. We then show how to derandomize this algorithm, obtaining the same asymptotic guarantees on degree and time complexity, but now requiring the standard CONGEST model. Although efficient approximation algorithms for the MDST problem have been known in the sequential setting since the 1990's (finding an exact solution is NP-hard), our algorithms are the first efficient distributed solutions. We conclude by proving a lower bound that establishes that any randomized MDST algorithm that guarantees a maximum degree in (Omega) over tilde (d) requires (Omega) over tilde (n(1/3)) rounds, and any deterministic solution requires (Omega) over tilde (n(1/2)) rounds. These bounds proves our deterministic algorithm to be asymptotically optimal, and eliminates the possibility of significantly more efficient randomized solutions.

关键词： CONGEST spanning tree minimum degree

来源：评论

学校读者我要写书评

暂无评论

Quantum distributed Algorithm for the All-Pairs Shortest Path Problem in the CONGEST-CLIQUE Model 19

Quantum Distributed Algorithm for the All-Pairs Shortest Pat...

引用

38th acm symposium on principles of distributed computing (PODC)

作者： Izumi, Taisuke Le Gall, Francois Nagoya Inst Technol Showa Ku Nagoya Aichi Japan Kyoto Univ Grad Sch Informat Sakyo Ku Kyoto Japan

ISBN: (纸本)9781450362177

The All-Pairs Shortest Path problem (APSP) is one of the most central problems in distributed computation. In the CONGEST-CLIQUE model, in which n nodes communicate with each other over a fully connected network by exchanging messages of O(log n) bits in synchronous rounds, the best known general algorithm for APSP uses (O) over tilde (n(1/3)) rounds. Breaking this barrier is a fundamental challenge in distributed graph algorithms. In this paper we investigate for the first time quantum distributed algorithms in the CONGEST-CLIQUE model, where nodes can exchange messages of O(log n) quantum bits, and show that this barrier can be broken: we construct a (O) over tilde (n(1/4))-round quantum distributed algorithm for the APSP over directed graphs with polynomial weights in the CONGEST-CLIQUE model. This speedup in the quantum setting contrasts with the case of the standard CONGEST model, for which Elkin et al. (PODC 2014) showed that quantum communication does not offer significant advantages over classical communication. Our quantum algorithm is based on a relationship discovered by Vassilevska Williams and Williams (Jacm 2018) between the APSP and the detection of negative triangles in a graph. The quantum part of our algorithm exploits the framework for quantum distributed search recently developed by Le Gall and Magniez (PODC 2018). Our main technical contribution is a method showing how to implement multiple quantum searches (one for each edge in the graph) in parallel without introducing congestions.

关键词： distributed algorithms quantum algorithms all-pairs shortest paths CONGEST-CLIQUE model

来源：评论

学校读者我要写书评

暂无评论

Partially Replicated Causally Consistent Shared Memory: Lower Bounds and An Algorithm 19

Partially Replicated Causally Consistent Shared Memory: Lowe...

引用

38th acm symposium on principles of distributed computing (PODC)

作者： Xiang, Zhuolun Vaidya, Nitin H. Univ Illinois Champaign IL 61820 USA Georgetown Univ Washington DC 20057 USA

ISBN: (纸本)9781450362177

The focus of this paper is on causal consistency in a partially replicated distributed shared memory (DSM) system that provides the abstraction of shared read/write registers. Maintaining causal consistency in distributed shared memory systems has received significant attention in the past, mostly on full replication wherein each replica stores a copy of all the registers in the shared memory. To ensure causal consistency, all causally preceding updates must be performed before an update is performed at any given replica. Therefore, some mechanism for tracking causal dependencies is required, such as vector timestamps with the number of vector elements being equal to the number of replicas in the context of full replication. In this paper, we investigate causal consistency in partially replicated systems, wherein each replica may store only a subset of the shared registers. Building on the past work, this paper makes three key contributions: We present a necessary condition on the metadata (which we refer as a timestamp) that must be maintained by each replica to be able to track causality accurately. The necessary condition identifies a set of directed edges in a share graph that a replica's timestamp must keep track of. We present an algorithm for achieving causal consistency using a timestamp that matches the above necessary condition, thus showing that the condition is necessary and sufficient. We define a measurement of timestamp space size and present a lower bound (in bits) on the size of the timestamps. The lower bound matches our algorithm in several special cases.

关键词： distributed shared memory causal consistency tight conditions lower bounds

来源：评论

学校读者我要写书评

暂无评论

Efficient Multiparty Interactive Coding for Insertions, Deletions, and Substitutions [Extended Abstract] 19

Efficient Multiparty Interactive Coding for Insertions, Dele...

引用

38th acm symposium on principles of distributed computing (PODC)

作者： Gelles, Ran Kalai, Yael Tauman Ramnarayan, Govind Bar Ilan Univ Ramat Gan Israel Microsoft Res Redmond WA USA MIT 77 Massachusetts Ave Cambridge MA 02139 USA

ISBN: (纸本)9781450362177

In the field of interactive coding, two or more parties wish to carry out a distributed computation over a communication network that may be noisy. The ultimate goal is to develop efficient coding schemes that can tolerate a high level of noise while increasing the communication by only a constant factor (i.e., constant rate). In this work we consider synchronous communication networks over an arbitrary topology, in the powerful adversarial insertion-deletion noise model. Namely, the noisy channel may adversarially alter the content of any transmitted symbol, as well as completely remove a transmitted symbol or inject a new symbol into the channel. We provide efficient, constant rate schemes that successfully conduct any computation with high probability as long as the adversary corrupts at most epsilon/m fraction of the total communication, where m is the number of links in the network and epsilon is a small constant. This scheme assumes an oblivious adversary which is independent of the parties' inputs and randomness. We can remove this assumption and resist a worst-case adversary at the price of being resilient to epsilon/m log m errors. While previous work considered the insertion-deletion noise model in the two-party setting, to the best of our knowledge, our scheme is the first multiparty scheme that is resilient to insertions and deletions. Furthermore, our scheme is the first computationally efficient scheme in the multiparty setting that is resilient to adversarial noise.

关键词： interactive coding distributed algorithms error correcting codes

来源：评论

学校读者我要写书评

暂无评论

Asynchronous Arbitrary Pattern Formation: the effects of a rigorous approach

引用

distributed computing 2019年第2期32卷 91-132页

作者： Cicerone, Serafino Di Stefano, Gabriele Navarra, Alfredo Univ Aquila Dept Informat Engn Comp Sci & Math Via Vetoio I-67100 Laquila Italy Univ Perugia Dept Math & Comp Sci Via Vanvitelli 1 I-06123 Perugia Italy

Given any multiset F of points in the Euclidean plane and a set R of robots such that |R|=|F|, the Arbitrary Pattern Formation (APF) problem asks for a distributed algorithm that moves robots so as to reach a configuration similar to F. Similarity means that robots must be disposed as F regardless of translations, rotations, reflections, uniform scalings. Initially, each robot occupies a distinct position. When active, a robot operates in standard Look-Compute-Move cycles. Robots are asynchronous, oblivious, anonymous, silent and execute the same distributed algorithm. So far, the problem has been mainly addressed by assuming chirality, that is robots share a common left-right orientation. We are interested in removing such a restriction. While working on the subject, we faced several issues that required close attention. We deeply investigated how such difficulties were overcome in the literature, revealing that crucial arguments for the correctness proof of the existing algorithms have been neglected. The systematic lack of rigorous arguments with respect to necessary conditions required for providing correctness proofs deeply affects the validity as well as the relevance of strategies proposed in the literature. Here we design a new deterministic distributed algorithm that fully characterizes APF showing its equivalence with the well-known Leader Election problem in the asynchronous model without chirality. Our approach is characterized by the use of logical predicates in order to formally describe our algorithm as well as its correctness. In addition to the relevance of our achievements, our techniques might help in revising previous results. In fact, it comes out that well-established results like (Fujinaga et al. in SIAM J Comput 44(3):740-785, 2015), more recent approaches like (Bramas and Tixeuil, in: proceedings of the 35th acm SIGACT-SIGOPS symposium on principles of distributed computing (PODC), 2016;Bramas and Tixeuil, in: proceedings of the 18th interna

关键词： distributed algorithms Mobile robots Asynchrony Pattern formation

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Strongly Linearizable Implementations of Snapshots and Other Types 19

Strongly Linearizable Implementations of Snapshots and Other...

引用

38th acm symposium on principles of distributed computing (PODC)

作者： Ovens, Sean Woelfel, Philipp Univ Calgary Calgary AB Canada

ISBN: (纸本)9781450362177

Linearizability is the gold standard of correctness conditions for shared memory algorithms, and historically has been considered the practical equivalent of atomicity. However, it has been shown [16] that replacing atomic objects with linearizable implementations can affect the probability distribution of execution outcomes in randomized algorithms. Thus, linearizable objects are not always suitable replacements for atomic objects. A stricter correctness condition called strong linearizability has been developed and shown to be appropriate for randomized algorithms in a strong adaptive adversary model [16]. We devise several new lock-free strongly linearizable implementations from atomic registers. In particular, we give the first strongly linearizable lock-free snapshot implementation that uses bounded space. This improves on the unbounded space solution of Denysyuk and Woelfel [14]. As a building block, our algorithm uses a lock-free strongly linearizable ABA-detecting register. We obtain this object by modifying the wait-free linearizable ABA-detecting register of Aghazadeh and Woelfel [5], which, as we show, is not strongly linearizable. Aspnes and Herlihy [8] identified a wide class of types that have wait-free linearizable implementations. These types require that any pair of operations either commute, or one overwrites the other. Aspnes and Herlihy gave a general wait-free linearizable implementation of such types, employing an atomic snapshot object. We show that this implementation is strongly linearizable, proving that all types in this class have a lock-free strongly linearizable implementation from atomic registers.

关键词： distributed algorithms shared memory strong linearizability snapshots ABA lock-freedom

来源：评论

学校读者我要写书评

暂无评论

Secure distributed computing Made (Nearly) Optimal 19

Secure Distributed Computing Made (Nearly) Optimal

引用

38th acm symposium on principles of distributed computing (PODC)

作者： Parter, Merav Yogev, Eylon Weizmann Inst Sci Rehovot Israel Technion Haifa Israel

ISBN: (纸本)9781450362177

In this paper, we study secure distributed algorithms that are nearly optimal, with respect to running time, for the given input graph G. Roughly speaking, an algorithm is secure if the nodes learn only their final output while gaining no information on the input (or output) of other nodes. A graph theoretic framework for secure distributed computation was recently introduced by the authors (SODA 2019). This framework is quite general and it is based on a new combinatorial structure called private neighborhood trees: a collection of n trees T (u(1)), ... , T (u(n)) such that each tree T (u(i)) spans the neighbors of ui without going through ui. Intuitively, each tree T (u(i)) allows all neighbors of ui to exchange a secret that is hidden from ui. The efficiency of the framework depends on two key parameters of these trees: their depth and the amount of overlap. In a (d, c)-private neighborhood trees each tree T (u(i)) has depth O(d) and each edge e is an element of G appears in at most O(c) different trees. An existentially optimal construction of private neighborhood trees with d = O(Delta center dot D) and c = (O) over tilde (D) was1 presented therein. We make two key contributions: Universally Optimal Private Trees: We show a combinatorial construction of nearly (universally) optimal (d, c)-private neighborhood trees with d + c = (O) over tilde (OPT(G)) for any input graph G. Perhaps surprisingly, we show that OPT(G) is equal to the best depth possible for these trees even without the congestion constraint. We also present efficient distributed constructions of these private trees. Optimal Secure Computation: Using the optimal constructions above, we get a secure compiler for distributed algorithms where the overhead for each round is (O) over tilde (poly(Delta) center dot OPT(G)). As our second key contribution, we design an optimal compiler with an overhead of merely (O) over tilde (OPT(G)) per round for a class of "simple" algorithms. This class includes many

关键词： distributed algorithms multi-party computation private neighborhood trees secure computation

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: Optimal distributed Covering Algorithms 38

Brief Announcement: Optimal Distributed Covering Algorithms

引用

38th acm symposium on principles of distributed computing (PODC)

作者： Ben-Basat, Ran Even, Guy Kawarabayashi, Ken-ichi Schwartzman, Gregory Harvard Univ Cambridge MA 02138 USA Tel Aviv Univ Tel Aviv Israel Natl Inst Informat Tokyo Tokyo Japan

ISBN: (纸本)9781450362177

We present a time-optimal deterministic distributed algorithm for approximating a minimum weight vertex cover in hypergraphs of rank f. This problem is equivalent to the Minimum Weight Set Cover problem in which the frequency of every element is bounded by f. The approximation factor of our algorithm is (f + epsilon). Let Delta denote the maximum degree in the hypergraph. Our algorithm runs in the congest model and requires O(log Delta/log log Delta) rounds, for constants epsilon is an element of (0, 1] and f is an element of N+. This is the first distributed algorithm for this problem whose running time does not depend on the vertex weights nor the number of vertices. Thus adding another member to the exclusive family of provably optimal distributed algorithms. For constant values of f and epsilon, our algorithm improves over the (f + epsilon)-approximation algorithm of [16] whose running time is O(log Delta + log W), where W is the ratio between the largest and smallest vertex weights in the graph. Our algorithm also achieves an f-approximation for the problem in O(f log n) rounds, improving over the classical result of [13] that achieves a running time of O(f log(2) n). Finally, for weighted vertex cover (f = 2) our algorithm achieves a deterministic running time of O(log n), matching the randomized previously best result of [14]. We also show that integer covering-programs can be reduced to the Minimum Weight Set Cover problem in the distributed setting. This allows us to achieve an (f + epsilon)-approximate integral solution in O((1 + f/logn) center dot (log Delta/log log Delta + (f center dot logM)(1.01) center dot log epsilon(-1) center dot (log Delta)(0.01))) rounds, where f bounds the number of variables in a constraint, Delta bounds the number of constraints a variable appears in, and M = max {1, inverted right perpendicular1/a(min)inverted left perpendicular}, where amin is the smallest normalized constraint coefficient. This significantly improves over t

关键词： distributed computing Graph algorithms Primal dual Set cover Vertex cover

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：