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

Time-space trade-offs in population protocols for the majority problem

distributed computing 2021年第2期34卷 91-111页

作者： Berenbrink, Petra Elsaesser, Robert Friedetzky, Tom Kaaser, Dominik Kling, Peter Radzik, Tomasz Univ Hamburg Vogt Kolln Str 3 D-22527 Hamburg Germany Univ Salzburg Jakob Haringer Str 2 A-5020 Salzburg Austria Univ Durham Lower Mountjoy South Rd Durham DH1 3LE England Kings Coll London Strand CampusBush House London WC2B 4BG England

Population protocols are a model for distributed computing that is focused on simplicity and robustness. A system ofnidentical agents (finite state machines) performs a global task like electing a unique leader or determining the majority opinion when each agent has one of two opinions. Agents communicate in pairwise interactions with randomly assigned communication partners. Quality is measured in two ways: the number of interactions to complete the task and the number of states per agent. We present protocols for the majority problem that allow for a trade-off between these two measures. Compared to the only other trade-off result (Alistarh et al. in proceedings of the 2015 acm symposium on principles of distributed computing, Donostia-San Sebastian, 2015), we improve the number of interactions by almost a linear factor. Furthermore, our protocols can be made uniform (working correctly without any information on the population sizen), yielding the first uniform majority protocols that stabilize in a subquadratic number of interactions.

关键词： distributed computing Majority Population protocols Stochastic processes

来源：评论

学校读者我要写书评

暂无评论

Strong-Diameter Network Decomposition 21

Strong-Diameter Network Decomposition

引用

40th acm SIGACT-SIGOPS symposium on principles of distributed computing (PODC)

作者： Chang, Yi-Jun Ghaffari, Mohsen Swiss Fed Inst Technol Zurich Switzerland

ISBN: (纸本)9781450385480

Network decomposition is a central concept in the study of distributed graph algorithms. We present the first polylogarithmic-round deterministic distributed algorithm with small messages that constructs a strong-diameter network decomposition with polylogarithmic parameters. Concretely, a (C, D) strong-diameter network decomposition is a partitioning of the nodes of the graph into disjoint clusters, colored with C colors, such that neighboring clusters have different colors and the subgraph induced by each cluster has a diameter at most D. In the weak-diameter variant, the requirement is relaxed by measuring the diameter of each cluster in the original graph, instead of the subgraph induced by the cluster. A recent breakthrough of Rozhon and Ghaffari [STOC 2020] presented the first poly(log n)-round deterministic algorithm for constructing a weak-diameter network decomposition where C and D are both in poly(log n). Their algorithm uses small O(log n)-bit messages. One can transform their algorithm to a strong-diameter network decomposition algorithm with similar parameters. However, that comes at the expense of requiring unbounded messages. The key remaining qualitative question in the study of network decompositions was whether one can achieve a similar result for strong-diameter network decompositions using small messages. We resolve this question by presenting a novel technique that can transform any black-box weak-diameter network decomposition algorithm to a strong-diameter one, using small messages and with only moderate loss in the parameters.

关键词： ball carving distributed graph algorithms network decomposition

来源：评论

学校读者我要写书评

暂无评论

2022 Edsger W. Dijkstra Prize in distributed computing 22

2022 Edsger W. Dijkstra Prize in Distributed Computing

引用

proceedings of the 2022 acm symposium on principles of distributed computing

作者： Marcos Aguiliera Andrea Richa Alexander Schwarzmann Alessandro Panconesi Christian Scheideler Philipp Woelfel VMware Research Germany Arizona State University AZ USA Augusta University APO AA Sapienza Università Di Roma Rome Italy Universität Paderborn Paderborn Germany University of Calgary Calgary AB Canada

ISBN: (纸本)9781450392624

The Edsger W. Dijkstra Prize in distributed computing is awarded for outstanding papers on the principles of distributed computing, whose significance and impact on the theory or practice of distributed computing have been evident for at least a decade. It is sponsored jointly by the acm symposium on principles of distributed computing (PODC) and the EATCS symposium on distributed computing (DISC). The prize is presented annually, with the presentation taking place alternately at PODC and DISC.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: computing Power of Hybrid Models in Synchronous Networks 36

Brief Announcement: Computing Power of Hybrid Models in Sync...

引用

36th International symposium on distributed computing, DISC 2022

作者： Fraigniaud, Pierre Montealegre, Pedro Paredes, Pablo Rapaport, Ivan Ríos-Wilson, Martín Todinca, Ioan IRIF Université Paris Cité CNRS France Faculty of Engineering and Science Universidad Adolfo Ibáñez Santiago Chile Department of Mathematical Engineering University of Chile Santiago Chile DIM-CMM UMI 2807 CNRS University of Chile Santiago Chile LIFO Université d'Orléans France INSA Centre-Val de Loire Bourges France

ISBN: (纸本)9783959772556

During the last two decades, a small set of distributed computing models for networks have emerged, among which LOCAL, CONGEST, and Broadcast Congested Clique (BCC) play a prominent role. We consider hybrid models resulting from combining these three models. That is, we analyze the computing power of models allowing to, say, perform a constant number of rounds of CONGEST, then a constant number of rounds of LOCAL, then a constant number of rounds of BCC, possibly repeating this figure a constant number of times. We specifically focus on 2-round models, and we establish the complete picture of the relative powers of these models. That is, for every pair of such models, we determine whether one is (strictly) stronger than the other, or whether the two models are incomparable. © Pierre Fraigniaud, Pedro Montealegre, Pablo Paredes, Ivan Rapaport, Martín Ríos-Wilson, and Ioan Todinca.

关键词： computing power

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: The Complexity Landscape of Dynamic distributed Subgraph Finding 25

Brief Announcement: The Complexity Landscape of Dynamic Dist...

引用

proceedings of the acm symposium on principles of distributed computing

作者： Yi-Jun Chang Lyuting Chen Yanyu Chen Gopinath Mishra Mingyang Yang National University of Singapore Singapore Singapore

ISBN: (纸本)9798400718854

Bonne and Censor-Hillel (ICALP 2019) initiated the study of distributed subgraph finding in dynamic networks of limited bandwidth. For the case where the target subgraph is a clique, they determined the tight bandwidth complexity bounds in nearly all settings. However, several open questions remain, and very little is known about finding subgraphs beyond cliques. In this work, we consider these questions and explore subgraphs beyond *** finding cliques, we establish an Ω (log log n) bandwidth lower bound for one-round membership-detection under edge insertions only and an Ω (log log log n) bandwidth lower bound for one-round detection under both edge insertions and node insertions. Moreover, we demonstrate new algorithms to show that our lower bounds are tight in bounded-degree networks when the target subgraph is a triangle. Prior to our work, no lower bounds were known for these *** finding subgraphs beyond cliques, we present a complete characterization of the bandwidth complexity of the membership-listing problem for every target subgraph, every number of rounds, and every type of topological change: node insertions, node deletions, edge insertions, and edge deletions. We also show partial characterizations for one-round membership-detection and listing.

关键词： distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

Contention Resolution with Predictions 21

Contention Resolution with Predictions

引用

40th acm SIGACT-SIGOPS symposium on principles of distributed computing (PODC)

作者： Gilbert, Seth Newport, Calvin Vaidya, Nitin Weaver, Alex Natl Univ Singapore Singapore Singapore Georgetown Univ Washington DC 20057 USA

ISBN: (纸本)9781450385480

In this paper, we consider contention resolution algorithms that are augmented with predictions about the network. We begin by studying the natural setup in which the algorithm is provided a distribution defined over the possible network sizes that predicts the likelihood of each size occurring. The goal is to leverage the predictive power of this distribution to improve on worst-case time complexity bounds. Using a novel connection between contention resolution and information theory, we prove lower bounds on the expected time complexity with respect to the Shannon entropy of the corresponding network size random variable, for both the collision detection and no collision detection assumptions. We then analyze upper bounds for these settings, assuming now that the distribution provided as input might differ from the actual distribution generating network sizes. We express their performance with respect to both entropy and the statistical divergence between the two distributions-allowing us to quantify the cost of poor predictions. Finally, we turn our attention to the related perfect advice setting, parameterized with a length b >= 0, in which all active processes in a given execution are provided the best possible b bits of information about their network. We provide tight bounds on the speed-up possible with respect to b for deterministic and randomized algorithms, with and without collision detection. These bounds provide a fundamental limit on the maximum power that can be provided by any predictive model with a bounded output size.

关键词： distributed algorithms contention resolution

来源：评论

学校读者我要写书评

暂无评论

Exponential Speedup over Locality in MPC with Optimal Memory 36

Exponential Speedup over Locality in MPC with Optimal Memory

引用

36th International symposium on distributed computing, DISC 2022

作者： Balliu, Alkida Brandt, Sebastian Fischer, Manuela Latypov, Rustam Maus, Yannic Olivetti, Dennis Uitto, Jara Gran Sasso Science Institute L'Aquila Italy CISPA Helmholtz Center for Information Security Saarbrücken Germany ETH Zürich Switzerland Aalto University Espoo Finland TU Graz Austria

ISBN: (纸本)9783959772556

Locally Checkable Labeling (LCL) problems are graph problems in which a solution is correct if it satisfies some given constraints in the local neighborhood of each node. Example problems in this class include maximal matching, maximal independent set, and coloring problems. A successful line of research has been studying the complexities of LCL problems on paths/cycles, trees, and general graphs, providing many interesting results for the LOCAL model of distributed computing. In this work, we initiate the study of LCL problems in the low-space Massively Parallel Computation (MPC) model. In particular, on forests, we provide a method that, given the complexity of an LCL problem in the LOCAL model, automatically provides an exponentially faster algorithm for the low-space MPC setting that uses optimal global memory, that is, truly linear. While restricting to forests may seem to weaken the result, we emphasize that all known (conditional) lower bounds for the MPC setting are obtained by lifting lower bounds obtained in the distributed setting in tree-like networks (either forests or high girth graphs), and hence the problems that we study are challenging already on forests. Moreover, the most important technical feature of our algorithms is that they use optimal global memory, that is, memory linear in the number of edges of the graph. In contrast, most of the state-of-the-art algorithms use more than linear global memory. Further, they typically start with a dense graph, sparsify it, and then solve the problem on the residual graph, exploiting the relative increase in global memory. On forests, this is not possible, because the given graph is already as sparse as it can be, and using optimal memory requires new solutions. © Alkida Balliu, Sebastian Brandt, Manuela Fischer, Rustam Latypov, Yannic Maus, Dennis Olivetti, and Jara Uitto.

关键词： distributed computer systems

来源：评论

学校读者我要写书评

暂无评论

Separating Bounded and Unbounded Asynchrony for Autonomous Robots: Point Convergence with Limited Visibility 21

Separating Bounded and Unbounded Asynchrony for Autonomous R...

引用

40th acm SIGACT-SIGOPS symposium on principles of distributed computing (PODC)

作者： Kirkpatrick, David Kostitsyna, Irina Navarra, Alfredo Prencipe, Giuseppe Santoro, Nicola Univ British Columbia Dept Comp Sci Vancouver BC Canada TU Eindhoven Dept Math & Comp Sci Eindhoven Netherlands Univ Perugia Dept Math & Comp Sci Perugia Italy Univ Dip Informat Pisa Italy Carleton Univ Sch Comp Sci Ottawa ON Canada

ISBN: (纸本)9781450385480

We consider distributed computations, by identical autonomous mobile entities, that solve the Point Convergence problem: given an arbitrary initial configuration of entities, disposed in the Euclidean plane, move in such a way that, for all epsilon > 0, a configuration is eventually reached and maintained in which the separation between all entities is at most epsilon. The problem has been previously studied in a variety of settings. Our study concerns the minimal assumptions under which entities, moving asynchronously with limited and unknown visibility range and subject to limited imprecision in measurements, can be guaranteed to converge in this way. We present an algorithm that solves Point Convergence, provided the degree of asynchrony is bounded by some arbitrarily large but fixed constant. This provides a strong positive answer to a decade old open question posed by Katreniak. We also prove that, in an otherwise comparable setting, Point Convergence is impossible with unbounded asynchrony. This serves to distinguish the power of bounded and unbounded asynchrony in the control of autonomous mobile entities, settling at the same time a long-standing question whether in the Euclidean plane synchronous entities are more powerful than asynchronous ones.

关键词： Mobile robots distributed geometric algorithms Asynchrony

来源：评论

学校读者我要写书评

暂无评论

Low-Congestion Shortcuts for Graphs Excluding Dense Minors 21

Low-Congestion Shortcuts for Graphs Excluding Dense Minors

引用

40th acm SIGACT-SIGOPS symposium on principles of distributed computing (PODC)

作者： Ghaffari, Mohsen Haeupler, Bernhard Swiss Fed Inst Technol Zurich Switzerland Carnegie Mellon Univ Pittsburgh PA 15213 USA

ISBN: (纸本)9781450385480

We prove that any n-node graph G with diameter D admits shortcuts with congestion O(delta D log n) and dilation O(delta D), where delta is the maximum edge-density of any minor of G. Our proof is simple and constructive with a (Theta) over tilde(delta D)-round(1) distributed construction algorithm. Our results are tight up to logarithmic factors and generalize, simplify, unify, and strengthen several prior results. For example, for graphs excluding a fixed minor, i.e., graphs with constant delta, only (O) over tilde (D-2) bound was known based on a very technical proof that relies on the Robertson-Seymour Graph Structure Theorem. A direct consequence of our result is this: many graph families, including any minor-excluded ones, have near-optimal (Theta) over tilde (D)-round distributed algorithms for many fundamental communication primitives and optimization problems in the standard synchronous message-passing model with logarithmic message sizes, i.e., the CONGEST model. These problems include minimum spanning tree, minimum cut approximation, and shortest-path approximations.

关键词： distributed graph algorithms low-congestion shortcuts minor-exluded graphs planar graphs congestion dilation minimum spanning tree

来源：评论

学校读者我要写书评

暂无评论

Tight Bounds on Channel Reliability via Generalized Quorum Systems 25

Tight Bounds on Channel Reliability via Generalized Quorum S...

引用

proceedings of the acm symposium on principles of distributed computing

作者： Alejandro Naser-Pastoriza Gregory Chockler Alexey Gotsman Fedor Ryabinin IMDEA Software Institute Madrid Spain Universidad Politécnica de Madrid Madrid Spain University of Surrey UK Guildford United Kingdom

ISBN: (纸本)9798400718854

Communication channel failures are a major concern for the developers of modern fault-tolerant systems. However, while tight bounds for process failures are well-established, extending them to include channel failures has remained an open problem. We introduce generalized quorum systems -- a framework that characterizes the necessary and sufficient conditions for implementing atomic registers, atomic snapshots, lattice agreement and consensus under arbitrary patterns of process-channel failures. Generalized quorum systems relax the connectivity constraints of classical quorum systems: instead of requiring bidirectional reachability for every pair of write and read quorums, they only require some write quorum to be unidirectionally reachable from some read quorum. This weak connectivity makes implementing registers particularly challenging, because it precludes the traditional request/response pattern of quorum access, making classical solutions like ABD inapplicable. To address this, we introduce novel logical clocks that allow write and read quorums to reliably track state updates without relying on bidirectional connectivity.

关键词： distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：