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

36th International symposium on distributed computing, DISC 2022

作者： Dufoulon, Fabien Kutten, Shay Moses, William K. Pandurangan, Gopal Peleg, David Department of Computer Science University of Houston HoustonTX United States Faculty of Industrial Engineering and Management Technion - Israel Institute of Technology Haifa Israel Department of Computer Science and Applied Mathematics Weizmann Institute of Science Rehovot Israel

ISBN: (纸本)9783959772556

A singularly (near) optimal distributed algorithm is one that is (near) optimal in two criteria, namely, its time and message complexities. For synchronous CONGEST networks, such algorithms are known for fundamental distributed computing problems such as leader election [Kutten et al., Jacm 2015] and Minimum Spanning Tree (MST) construction [Pandurangan et al., STOC 2017, Elkin, PODC 2017]. However, it is open whether a singularly (near) optimal bound can be obtained for the MST construction problem in general asynchronous CONGEST networks. In this paper, we present a randomized distributed MST algorithm that, with high probability, computes an MST in asynchronous CONGEST networks and takes Õ(D1+Ε + √n) time and Õ(m) messages1, where n is the number of nodes, m the number of edges, D is the diameter of the network, and Ε > 0 is an arbitrarily small constant (both time and message bounds hold with high probability). Since (Equation presented)(D + √n) and Ω(m) are respective time and message lower bounds for distributed MST construction in the standard KT0 model, our algorithm is message optimal (up to a polylog(n) factor) and almost time optimal (except for a DΕ factor). Our result answers an open question raised in Mashregi and King [DISC 2019] by giving the first known asynchronous MST algorithm that has sublinear time (for all D = O(n1-Ε)) and uses Õ(m) messages. Using a result of Mashregi and King [DISC 2019], this also yields the first asynchronous MST algorithm that is sublinear in both time and messages in the KT1 CONGEST model. A key tool in our algorithm is the construction of a low diameter rooted spanning tree in asynchronous CONGEST that has depth Õ(D1+Ε) (for an arbitrarily small constant Ε > 0) in Õ(D1+Ε) time and Õ(m) messages. To the best of our knowledge, this is the first such construction that is almost singularly optimal in the asynchronous setting. This tree construction may be of independent interest as it can also be used for efficiently perfor

关键词： distributed computer systems

来源：评论

学校读者我要写书评

暂无评论

Improved Byzantine Agreement under an Adaptive Adversary 25

Improved Byzantine Agreement under an Adaptive Adversary

引用

proceedings of the acm symposium on principles of distributed computing

作者： Fabien Dufoulon Gopal Pandurangan School of Computing and Communications Lancaster University Lancaster United Kingdom United Kingdom Department of Computer Science University of Houston Houston Texas USA

ISBN: (纸本)9798400718854

Byzantine agreement is a fundamental problem in fault-tolerant distributed computing that has been studied intensively for the last four decades. Much of the research has focused on a static Byzantine adversary, where the adversary is constrained to choose the Byzantine nodes in advance of the protocol's execution. This work focuses on the harder case of an adaptive Byzantine adversary that can choose the Byzantine nodes adaptively based on the protocol's execution. While efficient O(log n)-round protocols (n is the total number of nodes) are known for the static adversary (Ben-Or, Goldwasser, Vaikuntanathan, FOCS 2006) tolerating up to t < n/(3 + ϵ) Byzantine nodes, [EQUATION] rounds is a well-known lower bound for adaptive adversary [Bar-Joseph and Ben-Or, PODC 1998]. The best-known protocol for adaptive adversary runs in O(t/log n) rounds [Chor and Coan, IEEE Trans. Soft. Engg., 1985].This work presents a synchronous randomized Byzantine agreement protocol under an adaptive adversary that improves over previous results. Our protocol works under the powerful adaptive rushing adversary in the full information model. That is, we assume that the Byzantine nodes can behave arbitrarily and maliciously, have knowledge about the entire state of the network at every round, including random choices made by all the nodes up to and including the current round, have unlimited computational power, and may collude among themselves. Furthermore, the adversary can adaptively corrupt up to t < n/3 nodes based on the protocol's execution. We present a simple randomized Byzantine agreement protocol that runs in O(min{t2 log n/n, t/log n}) rounds that improves over the long-standing bound of O(t/log n) rounds due to Chor and Coan [IEEE Trans. Soft. Engg., 1985]. Our bound is significantly better than that of Chor and Coan for t = o(n/log2 n) and approaches the Bar-Joseph and Ben-Or [PODC 1998] lower bound of [EQUATION] rounds when t approaches [EQUATION].

关键词： secure computation

来源：评论

学校读者我要写书评

暂无评论

2022 principles of distributed computing Doctoral Dissertation Award 22

2022 Principles of Distributed Computing Doctoral Dissertati...

引用

proceedings of the 2022 acm symposium on principles of distributed computing

作者： Yehuda Afek Keren Censor-Hillel Pierre Fraigniaud Seth Gilbert Gopal Pandurangan Gadi Taubenfeld Tel-Aviv University Tel-Aviv Israel Technion Haifa Israel CNRS and Université Paris Cité Paris France National University of Singapore Singapore Singapore University of Houston Houston TX USA Reichman University Herzelia Israel

ISBN: (纸本)9781450392624

Many exceptionally high-quality doctoral dissertations were submitted for the 2022 principles of distributed computing Doctoral Dissertation Award. After careful long deliberation, the award committee decided to share the award among two:⋅ Dr. Naama Ben-David for her dissertation ''Theoretical Foundations for Practical Concurrent and distributed Computation.''⋅ Dr. Manuela Fischer for her dissertation ''Local Algorithms for Classic Graph Problems.''

关键词：

来源：评论

学校读者我要写书评

暂无评论

Fast distributed approximation for TAP and 2-edge-connectivity

引用

distributed computing 2020年第2期33卷 145-168页

作者： Censor-Hillel, Keren Dory, Michal Technion Dept Comp Sci Haifa Israel

The tree augmentation problem (TAP) is a fundamental network design problem, in which the input is a graph G and a spanning tree T for it, and the goal is to augment T with a minimum set of edges Aug from G, such that T boolean OR Aug is 2-edge-connected. TAP has been widely studied in the sequential setting. The best known approximation ratio of 2 for the weighted case dates back to the work of Frederickson and JaJa (SIAM J Comput 10(2):270-283, 1981). Recently, a 3/2-approximation was given for unweighted TAP by Kortsarz and Nutov (acm Trans Algorithms 12(2):23, 2016). Recent breakthroughs give an approximation of 1.458 for unweighted TAP (Grandoni et al. in: proceedings of the 50th annual acm SIGACT symposium on theory of computing (STOC 2018), 2018), and approximations better than 2 for bounded weights (Adjiashvili in: proceedings of the twenty-eighth annual acm-SIAM symposium on discrete algorithms (SODA), 2017;Fiorini et al. in: proceedings of the twenty-ninth annual acm-SIAM symposium on discrete algorithms (SODA 2018), New Orleans, LA, USA, 2018. 10.1137/1.9781611975031.53). In this paper, we provide the first fast distributed approximations for TAP. We present a distributed 2-approximation for weighted TAP which completes in O(h) rounds, where h is the height of T. When h is large, we show a much faster 4-approximation algorithm for the unweighted case, completing in O(D+root nlog*n) rounds, where n is the number of vertices and D is the diameter of G. Immediate consequences of our results are an O(D)-round 2-approximation algorithm for the minimum size 2-edge-connected spanning subgraph, which significantly improves upon the running time of previous approximation algorithms, and an O(h(MST)+root nlog*n)-round 3-approximation algorithm for the weighted case, where h(MST) is the height of the MST of the graph. Additional applications are algorithms for verifying 2-edge-connectivity and for augmenting the connectivity of any connected spanning subgraph to 2.

关键词： distributed graph algorithms Approximation algorithms distributed network design Connectivity augmentation

来源：评论

学校读者我要写书评

暂无评论

Keynote: Time is not a Healer: Before and After 24

Keynote: Time is not a Healer: Before and After

引用

proceedings of the 43rd acm symposium on principles of distributed computing

作者： Nicola Santoro School of Computer Science Carleton University Ottawa Canada

ISBN: (纸本)9798400706684

distributed computing has been concerned with the topics of faults and failures from its very beginning (before PODC was born). The consensus problem was at the forefront of the research efforts, and an extensive body of literature on the subject was developed very quickly (e.g., [5, 6, 11, 20]). The beautiful proof of the impossibility of consensus under asynchrony [7] put to rest the unsuccessful attempts to prove otherwise, and gave an even stronger impetus to the focus on synchronous *** paper Time is not a Healer [16], which we shall denote by {T¬H}, was concerned with the problem of agreement in synchronous systems where failures have mostly a transient and ubiquitous nature; that is, faults can occur anywhere in the system and, following a failure, normal functioning can resume after a finite (although unpredictable) time. These type of dynamic failures, however, could not be handled by the traditional failure models developed for the consensus and related *** the significance and novelty of the scientific and technical contributions of {T¬H}, including the model, the proof technique, and the unexpected results. Incidentally, while known for its results on omissions, {T¬H} contains also tight bounds on corruptions, additions, and the Byzantine combination of all. While known for its impossibility results, it has tight possibility results, which hold in situations for which the traditional models indicate impossibility. Over the decades, triggered by these results, an extensive literature has been developed (e.g., [3, 4, 8, 9, 13, 15, 19, 21]).The relatively recent developments in communication technology and advent of new virtual systems (e.g., wireless mobile networks, social networks) have driven the research in distributed computing to investigate problems (including consensus) in dynamic networks (e.g., [2, 10, 12]); this has inevitably brought to light the immediate connection between such networks and the ones subject to dynamic omiss

关键词： theory of distributed computation synchronous systems dynamic faults agreement dynamic networks

来源：评论

学校读者我要写书评

暂无评论

Synthesizing optimal collective algorithms 21

Synthesizing optimal collective algorithms

引用

26th acm SIGPLAN symposium on principles and Practice of Parallel Programming, PPoPP 2021

作者： Cai, Zixian Liu, Zhengyang Maleki, Saeed Musuvathi, Madanlal Mytkowicz, Todd Nelson, Jacob Saarikivi, Olli Research School of Computer Science Australian National University Canberra ACT Australia School of Computing University of Utah Salt Lake CityUT United States Microsoft Research RedmondWA United States

ISBN: (纸本)9781450382946

Collective communication algorithms are an important component of distributed computation. Indeed, in the case of deep-learning, collective communication is the Amdahl's bottleneck of data-parallel training. This paper introduces SCCL (for Synthesized Collective Communication Library), a systematic approach to synthesizing collective communication algorithms that are explicitly tailored to a particular hardware topology. SCCL synthesizes algorithms along the Pareto-frontier spanning from latency-optimal to bandwidth-optimal implementations of a collective. The paper demonstrates how to encode the synthesis problem as a quantifier-free SMT formula which can be discharged to a theorem prover. We show how our carefully built encoding enables SCCL to scale. We synthesize novel latency and bandwidth optimal algorithms not seen in the literature on two popular hardware topologies. We also show how SCCL efficiently lowers algorithms to implementations on two hardware architectures (NVIDIA and AMD) and demonstrate competitive performance with hand optimized collective communication libraries. © 2021 acm.

关键词： Bandwidth

来源：评论

学校读者我要写书评

暂无评论

Almost Universally Optimal distributed Laplacian Solvers via Low-Congestion Shortcuts 36

Almost Universally Optimal Distributed Laplacian Solvers via...

引用

36th International symposium on distributed computing, DISC 2022

作者： Anagnostides, Ioannis Lenzen, Christoph Haeupler, Bernhard Zuzic, Goran Gouleakis, Themis Carnegie Mellon University PittsburghPA United States CISPA Helmholtz Center for Information Security Saarbrücken Germany ETH Zürich Switzerland National University of Singapore Singapore

ISBN: (纸本)9783959772556

In this paper, we refine the (almost) existentially optimal distributed Laplacian solver recently developed by Forster, Goranci, Liu, Peng, Sun, and Ye (FOCS '21) into an (almost) universally optimal distributed Laplacian solver. Specifically, when the topology is known (i.e., the Supported-CONGEST model), we show that any Laplacian system on an n-node graph with shortcut quality SQ(G) can be solved after no(1)SQ(G) log(1/Ε) rounds, where Ε is the required accuracy. This almost matches our lower bound that guarantees that any correct algorithm on G requires (Equation presented)(SQ(G)) rounds, even for a crude solution with Ε ≤ 1/2. Several important implications hold in the unknown-topology (i.e., standard CONGEST) case: for excluded-minor graphs we get an almost universally optimal algorithm that terminates in D · no(1) log(1/Ε) rounds, where D is the hop-diameter of the network;as well as no(1) log(1/Ε)-round algorithms for the case of SQ(G) ≤ no(1), which holds for most networks of interest. Conditioned on improvements in state-of-the-art constructions of low-congestion shortcuts, the CONGEST results will match the Supported-CONGEST ones. 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 node-capacitated clique (NCC) model. In this model, we show the existence of a Laplacian solver with round complexity no(1) log(1/Ε). The unifying thread of these results, and our main technical contribution, is the study of a novel ρ-congested generalization of the standard part-wise aggregation problem. We develop near-optimal algorithms for this primitive in the Supported-CONGEST model, almost-optimal algorithms in (standard) CONGEST (with the additional overhead due to standard barriers), as well as a simple algorithm for bounded-treewidth graphs with a quadratic dependence on the congestion ρ. This primitive can be readily used to accelerate the Lap

关键词： Topology

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: Rise and Shine Efficiently! The Complexity of Adversarial Wake-up 25

Brief Announcement: Rise and Shine Efficiently! The Complexi...

引用

proceedings of the acm symposium on principles of distributed computing

作者： Peter Robinson Ming Ming Tan Augusta University Augusta USA

ISBN: (纸本)9798400718854

We study the wake-up problem in distributed networks, where an adversary awakens a subset of nodes at arbitrary times, and the goal is to wake up all other nodes as quickly as possible by sending only few messages. We prove the following lower bounds:• We first consider the setting where each node receives advice from an oracle who can observe the entire network, but does not know which nodes are awake initially. More specifically, we consider the KT0 LOCAL model with advice, where the nodes have no prior knowledge of their neighbors. We prove that any randomized algorithm must send [EQUATION] messages if nodes receive only O (β) bits of advice on average.• For the KT1 assumption, where each node knows its neighbors' IDs from the start, we show that any (k + 1)-time algorithm requires Ω(n1+1/k) messages. Our result is the first super-linear (in n) lower bound, for a problem that does not require individual nodes to learn a large amount of information about the network topology, which may be of independent interest. This applies even to the synchronous KT1 LOCAL model, where the computation is structured into rounds and messages can be of unbounded *** complement our lower bound results, we present several new algorithms:• We give an asynchronous KT1 LOCAL algorithm that solves the wake-up problem with a time and message complexity of O (n log n) with high probability.• We introduce the notion of awake distance ρawk, which is upper-bounded by the network diameter, and present a synchronous KT1 LOCAL algorithm that takes O (ρawk) rounds and sends [EQUATION] messages with high probability.• We give deterministic advising schemes in the asynchronous KT0 CONGEST model (with advice). In particular, we obtain an O(ρawk log2 n)-time advising scheme that sends O(n log2 n) messages, while requiring O(log2 n) bits of advice per node.

关键词： distributed wake-up

来源：评论

学校读者我要写书评

暂无评论

Random Walks on Huge Graphs at Cache Efficiency 21

Random Walks on Huge Graphs at Cache Efficiency

引用

28th acm symposium on Operating Systems principles (SOSP)

作者： Yang, Ke Ma, Xiaosong Thirumuruganathan, Saravanan Chen, Kang Wu, Yongwei Tsinghua Univ Dept Comp Sci & Technol Beijing Natl Res Ctr Informat Sci & Technol BNRis Beijing Peoples R China Hamad Bin Khalifa Univ Qatar Comp Res Inst Ar Rayyan Qatar Beijing HaiZhi XingTu Technol Co Ltd Beijing Peoples R China

ISBN: (纸本)9781450387095

Data-intensive applications dominated by random accesses to large working sets fail to utilize the computing power of modern processors. Graph random walk, an indispensable workhorse for many important graph processing and learning applications, is one prominent case of such applications. Existing graph random walk systems are currently unable to match the GPU-side node embedding training speed. This work reveals that existing approaches fail to effectively utilize the modern CPU memory hierarchy, due to the widely held assumption that the inherent randomness in random walks and the skewed nature of graphs render most memory accesses random. We demonstrate that there is actually plenty of spatial and temporal locality to harvest, by careful partitioning, rearranging, and batching of operations. The resulting system, FlashMob, improves both cache and memory bandwidth utilization by making memory accesses more sequential and regular. We also found that a classical combinatorial optimization problem (and its exact pseudo-polynomial solution) can be applied to complex decision making, for accurate yet efficient data/task partitioning. Our comprehensive experiments over diverse graphs show that our system achieves an order of magnitude performance improvement over the fastest existing system. It processes a 58GB real graph at higher per-step speed than the existing system on a 600KB toy graph fitting in the L2 cache.

关键词： graph computing random walk memory cache

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: Collect in the Presence of Continuous Churn with Application to Snapshots and Lattice Agreement 20

Brief Announcement: Collect in the Presence of Continuous Ch...

引用

39th symposium on principles of distributed computing

作者： Attiya, Hagit Kumari, Sweta Somani, Archit Welch, Jennifer L. Technion Haifa Israel Texas A&M Univ College Stn TX 77843 USA

ISBN: (纸本)9781450375825

A popular programming technique that contributes to designing provably-correct distributed applications is to use shared objects for interprocess communication, instead of more low-level techniques. Although shared objects are a convenient abstraction, they are not generally provided in large-scale distributed systems; instead, the processes keep individual copies of the data and communicate by sending messages to keep the copies consistent. Traditional distributed computing considers a static system, with known bounds on the number of fixed computing nodes and the number of possible failures. Dynamic distributed systems allow nodes to enter and leave the system at will, either due to failures and recoveries, moving in the real world, or changes to the systems' composition. Motivating applications include those in peer-to-peer, sensor, mobile, and social networks, as well as server farms.

关键词： distributed computer systems

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：