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

acm symposium on principles of distributed computing (PODC)

作者： Fraigniaud, Pierre Paz, Ami Rajsbaum, Sergio Univ Paris Cite IRIF Paris France CNRS Paris France Univ Nacl Autonoma Mexico Inst Matemat Mexico City Mexico

ISBN: (纸本)9781450392624

We study two fundamental problems of distributed computing, consensus and approximate agreement, through a novel approach for proving lower bounds and impossibility results, that we call the asynchronous speedup theorem. For a given n-process task Pi and a given computational model M, we define a new task, called the closure of Pi with respect to M. The asynchronous speedup theorem states that if a task Pi is solvable in t >= 1 rounds in M, then its closure w.r.t. M is solvable in t - 1 rounds in... We prove this theorem for iterated models, as long as the model allows solo executions. We illustrate the power of our asynchronous speedup theorem by providing a new proof of the wait-free impossibility of consensus using read/write registers, and a new proof of the wait-free impossibility of solving consensus using registers and test&set objects for n > 2. The proof is merely by showing that, in each case, the closure of consensus (w.r.t. the corresponding model) is consensus itself. Our main application is the study of the power of additional objects, namely test&set and binary consensus, for wait-free solving approximate agreement faster. By analyzing the closure of approximate agreement w.r.t. each of the two models, we show that while these objects are more powerful than read/write registers from the computability perspective, they are not more powerful as far as helping solving approximate agreement faster is concerned.

关键词： Lower Bounds distributed Algorithms Consensus Approximate Agreement Combinatorial Topology

来源：评论

学校读者我要写书评

暂无评论

Universally-Optimal distributed Exact Min-Cut 22

Universally-Optimal Distributed Exact Min-Cut

引用

acm symposium on principles of distributed computing (PODC)

作者： Ghaffari, Mohsen Zuzic, Goran MIT Cambridge MA 02139 USA Swiss Fed Inst Technol Zurich Switzerland

ISBN: (纸本)9781450392624

We present a universally-optimal distributed algorithm for the exact weighted min-cut. The algorithm is guaranteed to complete in (O) over tilde (D + root n) rounds on every graph, recovering the recent result of Dory, Efron, Mukhopadhyay, and Nanongkai [STOC'21], but runs much faster on structured graphs. Specifically, the algorithm completes in (O) over tilde (D) rounds on (weighted) planar graphs or, more generally, any (weighted) excluded-minor family. We obtain this result by designing an aggregation-based algorithm: each node receives only an aggregate of the messages sent to it. While somewhat restrictive, recent work shows any such black-box algorithm can be simulated on any minor of the communication network. Furthermore, we observe this also allows for the addition of (a small number of) arbitrarily-connected virtual nodes to the network. We leverage these capabilities to design a min-cut algorithm that is significantly simpler compared to prior distributed work. We hope this paper showcases how working within this paradigm yields simple-to-design and ultra-efficient distributed algorithms for global problems. Our main technical contribution is a distributed algorithm that, given any tree T, computes the minimum cut that 2-respects T (i.e., cuts at most 2 edges of T) in universally near-optimal time. Moreover, our algorithm gives a deterministic (O) over tilde (D)-round 2-respecting cut solution for excluded-minor families and a deterministic (O) over tilde (D + root n)-round solution for general graphs, the latter resolving a question of Dory, et al. [STOC'21]

关键词： exact minimum cut distributed algorithms message-passing algorithms CONGEST model minor-aggregation model low-congestion shortcuts universal optimality

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: Deterministic Consensus and Checkpointing with Crashes: Time and Communication Efficiency 22

Brief Announcement: Deterministic Consensus and Checkpointin...

引用

acm symposium on principles of distributed computing (PODC)

作者： Chlebus, Bogdan S. Kowalski, Dariusz R. Olkowski, Jan Augusta Univ Sch Comp & Cyber Sci Augusta GA 30912 USA Univ Maryland Dept Comp Sci College Pk MD USA

ISBN: (纸本)9781450392624

We study consensus and checkpointing in synchronous distributed systems. There are n nodes that communicate by sending messages, and any two nodes can communicate directly. The nodes are prone to crashing, with an upper bound t on the number of crashes. Algorithms use overlay networks of choice to save on the amount of communication. We explore using Ramanujan graphs as such overlay networks. We demonstrate that Ramanujan graphs have topological properties conducive to fault-tolerance and time/communication efficiency of distributed algorithms. Our consensus algorithm assumes binary input values, runs in O(t) time and sends O(n+t log t) bits. The algorithm sends the optimum number O(n) of bits for t = O(n/log n), thus for this range of t it improves on the algorithm by Galil, Mayer and Yung [FOCS 1995] that also sends O(n) bits but works in exponential time. The consensus algorithm can be implemented such that a node sends a message to at most one node at a round while maintaining the asymptotic time and communication performance bounds. Our checkpointing algorithm runs in linear time O(n) and with O(n log(7) n) messages. It improves on the most communication-efficient and time-optimal algorithm by Galil, Mayer and Yung [FOCS 1995], which may have O(n(1+epsilon)) messages sent, for any chosen constant epsilon > 0.

关键词： distributed algorithm message passing synchrony node crash consensus checkpointing Ramanujan graph runtime performance communication performance

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: Almost Universally Optimal distributed Laplacian Solver 22

Brief Announcement: Almost Universally Optimal Distributed L...

引用

acm symposium on principles of distributed computing (PODC)

作者： Anagnostides, Ioannis Lenzen, Christoph Haeupler, Bernhard Zuzic, Goran Gouleakis, Themis Carnegie Mellon Univ Pittsburgh PA 15213 USA CISPA Helmholtz Ctr Informat Secur Saarbrucken Germany Swiss Fed Inst Technol Zurich Switzerland Natl Univ Singapore Singapore Singapore

ISBN: (纸本)9781450392624

This paper refines the distributed Laplacian solver recently developed by Forster, Goranci, Liu, Peng, Sun, and Ye (FOCS '21) via the Ghaffari-Haeupler framework (SODA '16) of low-congestion shortcuts. Specifically, if is an element of > 0 is the error of the Laplacian solver, we obtain two main results. First, in the supported version of the CONGEST model, we establish an almost universally optimal Laplacian solver. Namely, we show that any Laplacian system on an..-node graph with shortcut quality SQ(G) can be solved after n(o)( 1) SQ(G) log(1/is an element of) rounds, almost matching our lower bound of e Omega( SQ(G)) rounds on any graph G Our techniques also imply almost universally optimal Laplacian solvers in the full generality of CONGEST, conditional on the efficient construction of shortcuts. In particular, they unconditionally imply a novel Dn(o)(1) log( 1/is an element of) Laplacian solver for excluded-minor graphs with hop-diameter... Moreover, following a recent line of work in distributed algorithms, we consider a hybrid communication model which enhances CONGEST with limited global power in the form of the nodecapacitated clique (NCC) model. In this model, we show the existence of a Laplacian solver with round complexity Dn(o)(1) log( 1/is an element of). The unifying thread of these results, and our main technical contribution, is the development of nearly-optimal distributed algorithms for a novel congested generalization of the standard part-wise aggregation problem. This primitive accelerates the Laplacian solver of Forster, Goranci, Liu, Peng, Sun, and Ye, and we believe it will find further applications in the future.

关键词： distributed algorithms Laplacian solvers universal optimality Hybrid model

来源：评论

学校读者我要写书评

暂无评论

Narrowing the LOCAL-CONGEST Gaps in Sparse Networks via Expander Decompositions 22

Narrowing the LOCAL-CONGEST Gaps in Sparse Networks via Expa...

引用

acm symposium on principles of distributed computing (PODC)

作者： Chang, Yi-Jun Su, Hsin-Hao Natl Univ Singapore Singapore Singapore Boston Coll Boston MA 02467 USA

ISBN: (纸本)9781450392624

Many combinatorial optimization problems, including maximum weighted matching and maximum independent set, can be approximated within (1 +/-epsilon) factors in poly(log n, 1/epsilon) rounds in the LOCAL model via network decompositions [Ghaffari, Kuhn, and Maus, STOC 2018]. These approaches, however, require sending messages of unlimited size, so they do not extend to the more realistic CONGEST model, which restricts the message size to be O(log n) bits. For example, despite the long line of research devoted to the distributed matching problem, it still remains a major open problem whether an (1 - epsilon)-approximate maximum weighted matching can be computed in poly(log n, 1/epsilon) rounds in the CONGEST model. In this paper, we develop a generic framework for obtaining poly(log n, 1/epsilon)-round (1 +/- epsilon)-approximation algorithms for many combinatorial optimization problems, including maximum weighted matching, maximum independent set, and correlation clustering, in graphs excluding a fixed minor in the CONGEST model. This class of graphs covers many sparse network classes that have been studied in the literature, including planar graphs, bounded-genus graphs, and bounded-treewidth graphs. Furthermore, we show that our framework can be applied to give an efficient distributed property testing algorithm for an arbitrary minor-closed graph property that is closed under taking disjoint union, significantly generalizing the previous distributed property testing algorithm for planarity in [Levi, Medina, and Ron, PODC 2018 & distributed computing 2021]. Our framework uses distributed expander decomposition algorithms [Chang and Saranurak, FOCS 2020] to decompose the graph into clusters of high conductance. We show that any graph excluding a fixed minor admits small edge separators. Using this result, we show the existence of a high-degree vertex in each cluster in an expander decomposition, which allows the entire graph topology of the cluster to be routed to a

关键词： distributed graph algorithms expander decompositions matching

来源：评论

学校读者我要写书评

暂无评论

PPoPP 2022 - proceedings of the 27th acm SIGPLAN symposium on principles and Practice of Parallel Programming

PPoPP 2022 - Proceedings of the 27th ACM SIGPLAN Symposium o...

引用

27th acm SIGPLAN symposium on principles and Practice of Parallel Programming, PPoPP 2022

ISBN: (纸本)9781450392044

The proceedings contain 46 papers. The topics discussed include: stream processing with dependency-guided synchronization;mashup: making serverless computing useful for HPC workflows via hybrid execution;parallel block-delayed sequences;near-optimal sparse Allreduce for distributed deep learning;Vapro: performance variance detection and diagnosis for production-run parallel applications;interference relation-guided SMT solving for multi-threaded program verification;extending the limit of molecular dynamics with ab initio accuracy to 10 billion atoms;scaling graph traversal to 281 trillion edges with 40 million cores;asymmetry-aware scalable locking;the performance power of software combining in persistence;and multi-queues can be state-of-the-art priority schedulers.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: distributed Algorithms for Minimum Dominating Set Problem and Beyond, a New Approach 36

Brief Announcement: Distributed Algorithms for Minimum Domin...

引用

36th International symposium on distributed computing, DISC 2022

作者： Alipour, Sharareh Salari, Mohammadhadi Tehran Institute for Advanced Studies Iran Simon Fraser University Burnaby Canada

ISBN: (纸本)9783959772556

In this paper, we study the minimum dominating set (MDS) problem and the minimum total dominating set (MTDS) problem. We propose a new idea to compute approximate MDS and MTDS. This new approach can be implemented in a distributed model or parallel model. We also show how to use this new approach in other related problems such as set cover problem and k-distance dominating set problem. © Sharareh Alipour and Mohammadhadi Salari.

关键词： distributed computer systems

来源：评论

学校读者我要写书评

暂无评论

Time-optimal construction of overlay networks

引用

distributed computing 2023年第3期36卷 313-347页

作者： Goette, Thorsten Hinnenthal, Kristian Scheideler, Christian Werthmann, Julian Paderborn Univ Dept Comp Sci Warburger Str 100 D-33098 Paderborn Germany

This article shows how to construct an overlay network of constant degree and diameter O(log n) in O(log n) time starting from an arbitrary weakly connected graph. We assume a synchronous communication network in which nodes can send messages to nodes they know the identifier of, and new connections can be established by sending node identifiers. Suppose the initial network's graph is weakly connected and has constant degree. In that case, our algorithm constructs the desired topology with each node sending and receiving only O(log n) messages in each round in O(log n) time w.h.p., which beats the currently best O(log3/2 n) time algorithm of Gotte et al. (International colloquium on structural information and communication complexity (SIROCCO), Springer, 2019). Since the problem cannot be solved faster than by using pointer jumping for O(log n) rounds (which would even require each node to communicate Q(n) bits), our algorithm is asymptotically optimal. We achieve this speedup by using short random walks to repeatedly establish random connections between the nodes that quickly reduce the conductance of the graph using an observation of Kwok and Lau (Approximation, randomization, and combinatorial optimization. Algorithms and techniques (APPROX/RANDOM 2014), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2014). Additionally, we show how our algorithm can be used to efficiently solve graph problems in hybrid networks (Augustine et al. in proceedings of the fourteenth annual acm-SIAM symposium on discrete algorithms, SIAM, 2020). Motivated by the idea that nodes possess two different modes of communication, we assume that communication of the initial edges is unrestricted, whereas only polylogarithmically many messages can be sent over edges that have been established throughout an algorithm's execution. For an (undirected) graph G with arbitrary degree, we show how to compute connected components, a spanning tree, and biconnected components in O(log n) time w.h.p.

关键词： distributed protocol Peer-to-peer network Randomized algorithm Expander

来源：评论

学校读者我要写书评

暂无评论

Reducing carbon emissions of distributed systems: a multi-objective approach 24

Reducing carbon emissions of distributed systems: a multi-ob...

引用

20th Brazilian symposium on Informations Systems (SBSI) - Perspectives and Trends in Information Systems in Digital Agriculture

作者： Almeida, Guilherme do O, Marcelo T. Francesquini, Emilio Cordeiro, Daniel Univ Sao Paulo Escola Artes Ciencias & Humanidades Sao Paulo SP Brazil Univ Fed ABC Ctr Matemat Comp & Cognicao Santo Andre SP Brazil

ISBN: (纸本)9798400709968

Context The growing usage of platforms for distributed computing and their workloads are requiring more energy to power data centers, and the current consumption is already high. The increasing availability of green energy sources brings opportunities to reduce carbon emissions. Problem It is hard to create software aiming for both performance (makespan) and low brown energy usage. To reduce carbon emissions on distributed platforms, developers need an easy way to program efficiently applications and achieve these objectives. Solution Using OpenMP is an easy way to create and run distributed applications. This paper proposes the use of OpenMP with a new energy-aware scheduling algorithm that aims to minimize brown energy consumption and makespan. IS theory Our multiobjective algorithm (G-MOHEFT) deals with Complexity theory to leverage the Dynamic capabilities of modern distributed platforms. The algorithm implements a heuristic for adapting and redistributing workloads accordingly to different scenarios. Method Containers were used to simulate a distributed OpenMP Cluster (OMPC) platform. Different simulations using previously measured data were used to distribute workloads in different combinations of green energy availability. Summary of Results We study the solution tradeoffs obtained using G-MOHEFT, which varies from saving none to some brown energy consumption by keeping the same or increasing the makespan in exchange. Depending on the scenario, it could even reduce the brown energy consumption to zero. Contributions and impacts to IS Developers can use our algorithm to easily develop distributed software with a reduced carbon footprint using OpenMP in OMPC.

关键词： Tasks scheduling Green energy distributed computing Parallel computing OpenMP

来源：评论

学校读者我要写书评

暂无评论

Early Adapting to Trends: Self-Stabilizing Information Spread using Passive Communication 22

Early Adapting to Trends: Self-Stabilizing Information Sprea...

引用

acm symposium on principles of distributed computing (PODC)

作者： Korman, Amos Vacus, Robin Tel Aviv Univ French Natl Ctr Sci Res CNRS French Israeli Lab Fdn Comp Sci UMI FILOFOCSUP7HUJIWISInt Joint Res Unit Tel Aviv Israel French Natl Ctr Sci Res CNRS Inst Res Fundamental Comp Sci IRIF Paris France

ISBN: (纸本)9781450392624

How to efficiently and reliably spread information in a system is one of the most fundamental problems in distributed computing. Recently, inspired by biological scenarios, several works focused on identifying the minimal communication resources necessary to spread information under faulty conditions. Here we study the self-stabilizing bit-dissemination problem, introduced by Boczkowski, Korman, and Natale in [SODA 2017]. The problem considers a fully-connected network of n agents, with a binary world of opinions, one of which is called correct. At any given time, each agent holds an opinion bit as its public output. The population contains a source agent which knows which opinion is correct. This agent adopts the correct opinion and remains with it throughout the execution. We consider the basic PULL model of communication, in which each agent observes relatively few randomly chosen agents in each round. The goal of the non-source agents is to quickly converge on the correct opinion, despite having an arbitrary initial configuration, i.e., in a self-stabilizing manner. Once the population converges on the correct opinion, it should remain with it forever. Motivated by biological scenarios in which animals observe and react to the behavior of others, we focus on the extremely constrained model of passive communication, which assumes that when observing another agent the only information that can be extracted is the opinion bit of that agent. We prove that this problem can be solved in a poly-logarithmic in n number of rounds with high probability, while sampling a logarithmic number of agents at each round. Previous works solved this problem faster and using fewer samples, but they did that by decoupling the messages sent by agents from their output opinion, and hence do not fit the framework of passive communication. Moreover, these works use complex recursive algorithms with refined clocks that are unlikely to be used by biological entities. In contrast, our propo

关键词： Consensus protocols Population protocols Biological distributed algorithms Self-stabilization Passive communication

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：