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

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

来源：评论

学校读者我要写书评

暂无评论

distributed (Δ+1)-COLORING VIA ULTRAFAST GRAPH SHATTERING

引用

SIAM JOURNAL ON computing 2020年第3期49卷 497-539页

作者： Chang, Yi-Jun Li, Wenzheng Pettie, Seth Swiss Fed Inst Technol Inst Theoret Studies CH-8092 Zurich Switzerland Stanford Univ Comp Sci Dept Stanford CA 94305 USA Univ Michigan EECS Ann Arbor MI 48109 USA

Vertex coloring is one of the classic symmetry breaking problems studied in distributed computing. In this paper we present a new algorithm for (Delta+1)-list coloring in the randomized LOCAL model running in O(Det(d)(polylogn)) time, where Det(d)(n') is the deterministic complexity of (deg+1)-list coloring on n'-vertex graphs. (In this problem, each v has a palette of size deg(v)+1.) This improves upon a previous randomized algorithm of Harris, Schneider, and Su [J. acm, 65 (2018), 19] with complexity O(root log Delta+log log n+Det(d)(poly log n)) = O(root log n). Unless Delta is small, it is also faster than the best known deterministic algorithm of Fraigniaud, Heinrich, and Kosowski [proceedings of the 57th annual IEEE symposium on Foundations of Computer Science (FOCS), 2016] and Barenboim, Elkin, and Goldenberg [proceedings of the 38th annual acm symposium on principles of distributed computing (PODC), 2018], with complexity O(root Delta log log* Delta + log* n). Our algorithm's running time is syntactically very similar to the Omega(Det(poly log n)) lower bound of Chang, Kopelowitz, and Pettie [SIAM J. Comput., 48 (2019), pp. 122-143], where Det(n') is the deterministic complexity of (Delta + 1)-list coloring on n'-vertex graphs. Although distributed coloring has been actively investigated for 30 years, the best determin- istic algorithms for (deg +1)- and (Delta + 1)-list coloring (that depend on n' but not Delta) use a black-box application of network decompositions. The recent deterministic network decomposition algorithm of Rozhoil and Ghaffari [proceedings of the 52nd annual acm SIGACT symposium on Theory of computing (STOC), 2020] implies that Det(d)(n') and Det(n') are both poly(log n'). Whether they are asymptotically equal is an open problem.

关键词： distributed algorithm local model graph coloring

来源：评论

学校读者我要写书评

暂无评论

Byzantine Agreement and Leader Election: From Classical to the Modern 21

Byzantine Agreement and Leader Election: From Classical to t...

引用

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

作者： Augustine, John Molla, Anisur Rahaman Pandurangan, Gopal IIT Madras Dept Comp Sci & Engn Chennai Tamil Nadu India Indian Stat Inst Kolkata Crypto & Secur Res Unit Kolkata W Bengal India Univ Houston Dept Comp Sci Houston TX 77204 USA

ISBN: (纸本)9781450385480

We will present the fundamentals of Byzantine agreement and leader election problems from a modern perspective. Byzantine fault tolerant protocols are at the heart of secure and robust protocols that can tolerate the presence of malicious nodes in a distributed system, such as a Peer-to-Peer (P2P) network, which allows a large number of peers to enter the network with little or no admission control. Such malicious peers acting alone or in collaboration can cause disruption of service in P2P systems. Our tutorial is largely inspired by recent P2P applications like Blockchain and cryptocurrencies that espouse permissionless settings whereby peers can anonymously and dynamically join and leave the network at will. Our presentation will be in three parts. In the first part, we will present the historic foundations of Byzantine agreement and leader election and describe the fundamentals that underlie our modern understanding of these problems. Much of the classical results focus on complete networks where nodes have global knowledge. In the second part, motivated by real-world distributed networks such as P2P networks which are typically sparse and bounded degree with nodes having only local knowledge, we focus on Byzantine protocols for sparse networks. While the first two parts will focus on static settings, motivated by modern applications such as blockchains and cryptocurrencies which operate on dynamic P2P networks, the third part will delve into Byzantine procotols for dynamic networks where nodes continuously join and leave the system. The tutorial will cover various tools and techniques that are useful in designing Byzantine protocols in sparse and dynamic networks and will discuss key open problems in the area.

关键词： Byzantine protocols leader election agreement consensus distributed algorithms blockchain sparse networks P2P networks dynamic networks

来源：评论

学校读者我要写书评

暂无评论

distributed inference for multiple DNN models in IoT environments: poster 22

Distributed inference for multiple DNN models in IoT environ...

引用

proceedings of the twenty-third International symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile computing

作者： YoungHwan Jin HyungBin Park SuKyoung Lee Yonsei University Republic of Korea

ISBN: (纸本)9781450391658

Edge computing (EC) has been promising in providing support for Deep Neural Network (DNN) applications in IoT environments. However, resources in each edge are limited as response time increases. To reduce the latency, we propose to distribute the computation of multiple DNN models to nearby IoT devices. In particular, we propose a piece-wise multilevel partitioning and scheduling algorithm to improve the completion time of DNN inference.

关键词： IoT

来源：评论

学校读者我要写书评

暂无评论

2021 principles of distributed computing Doctoral Dissertation Award

Proceedings of the Annual ACM Symposium on Principles of Dis...

引用

proceedings of the annual acm symposium on principles of distributed computing 2021年 III-IV页

作者： Aguilera, Marcos K. Attiya, Hagit Cachin, Christian Panconesi, Alessandro VMWare Palo Alto United States Technion Haifa Israel University of Bern Switzerland Sapienza University of Rome Rome Italy

来源：评论

学校读者我要写书评

暂无评论

proceedings of the annual acm symposium on principles of distributed computing

Proceedings of the Annual ACM Symposium on Principles of Dis...

引用

39th symposium on principles of distributed computing, PODC 2020

ISBN: (纸本)9781450375825

The proceedings contain 66 papers. The topics discussed include: an adaptive approach to recoverable mutual exclusion;upper and lower bounds on the space complexity of detectable objects;long-lived snapshots with polylogarithmic amortized step complexity;from Bezout's identity to space-optimal election in anonymous memory systems;brief announcement: store-collect in the presence of continuous churn with application to snapshots and lattice agreement;brief announcement: why extension-based proofs fail;exponentially faster shortest paths in the congested clique;lower bounds for distributed sketching of maximal matchings and maximal independent sets;seeing far vs. seeing wide: volume complexity of local graph problems;computing shortest paths and diameter in the hybrid network model;revisiting asynchronous fault tolerant computation with optimal resilience;and asynchronous byzantine approximate consensus in directed networks.

关键词：

来源：评论

学校读者我要写书评

暂无评论

distributed Computation and Reconfiguration in Actively Dynamic Networks 20

Distributed Computation and Reconfiguration in Actively Dyna...

引用

39th symposium on principles of distributed computing

作者： Michail, Othon Skretas, George Spirakis, Paul G. Univ Liverpool Dept Comp Sci Liverpool Merseyside England Univ Patras Comp Engn & Informat Dept Patras Greece

ISBN: (纸本)9781450375825

In this paper, we study systems of distributed entities that can actively modify their communication network. This gives rise to distributed algorithms that apart from communication can also exploit network reconfiguration in order to carry out a given task. At the same time, the distributed task itself may now require a global reconfiguration from a given initial network G(s). to a target network G(f). from a family of networks having some good properties, like small diameter. To formally capture costs associated with creating and maintaining connections, we define three reasonable edge-complexity measures: the total edge activations, the maximum activated edges per round, and the maximum activated degree of a node. We give (poly)log(n) time algorithms for the general task of transforming any G(s) into a G(f) of diameter (poly)log(n), while minimizing the edge-complexity. There is a natural trade-off between time and edge complexity. Our main lower bound shows that Omega(n) total edge activations and O(n/log n) activations per round must be paid by any algorithm (even centralized) that achieves an optimum of Theta( log n) rounds. On the positive side, we give three distributed algorithms for our general task. The first runs in O( log n) time, with at most 2n active edges per round, a total of O(n log n) edge activations, a maximum degree n - 1, and a target network of diameter 2. The second achieves bounded degree by paying an additional logarithmic factor in time and in total edge activations. It gives a target network of diameter O( log n) and uses O (n) active edges per round. Our third algorithm shows that if we slightly increase the maximum degree to polylog(n) then we can achieve a running time of o (log(2) n). This novel model of distributed computation and reconfiguration in actively dynamic networks and the proposed measures of the edge complexity of distributed algorithms, may open new avenues for research in the algorithmic theory of dynamic networks.

关键词： distributed algorithms dynamic networks reconfiguration transformation polylogarithmic time edge complexity

来源：评论

学校读者我要写书评

暂无评论

Genuinely distributed Byzantine Machine Learning 20

Genuinely Distributed Byzantine Machine Learning

引用

39th symposium on principles of distributed computing

作者： El-Mhamdi, El-Mahdi Guerraoui, Rachid Guirguis, Arsany Le Nguyen Hoang Rouault, Sebastien Ecole Polytech Fed Lausanne Lausanne VD Switzerland

ISBN: (纸本)9781450375825

Machine Learning (ML) solutions are nowadays distributed, according to the so-called server/worker architecture. One server holds the model parameters while several workers train the model. Clearly, such architecture is prone to various types of component failures, which can be all encompassed within the spectrum of a Byzantine behavior. Several approaches have been proposed recently to tolerate Byzantine workers. Yet all require trusting a central parameter server. We initiate in this paper the study of the "general" Byzantineresilient distributed machine learning problem where no individual component is trusted. In particular, we distribute the parameter server computation on several nodes. We show that this problem can be solved in an asynchronous system, despite the presence of 1/3 Byzantine parameter servers and 1/3 Byzantine workers (which is optimal). We present a new algorithm, ByzSGD, which solves the general Byzantine-resilient distributed machine learning problem by relying on three major schemes. The first, Scatter/Gather, is a communication scheme whose goal is to bound the maximum drift among models on correct servers. The second, distributed Median Contraction (DMC), leverages the geometric properties of the median in high dimensional spaces to bring parameters within the correct servers back close to each other, ensuring learning convergence. The third, Minimum-Diameter Averaging (MDA), is a statistically-robust gradient aggregation rule whose goal is to tolerate Byzantine workers. MDA requires loose bound on the variance of non-Byzantine gradient estimates, compared to existing alternatives (e.g., Krum [12]). Interestingly, ByzSGD ensures Byzantine resilience without adding communication rounds (on a normal path), compared to vanilla non-Byzantine alternatives. ByzSGD requires, however, a larger number of messages which, we show, can be reduced if we assume synchrony. We implemented ByzSGD on top of TensorFlow, and we report on our evaluation result

关键词： distributed machine learning Byzantine fault tolerance Byzantine parameter servers

来源：评论

学校读者我要写书评

暂无评论

PODC 2019 - proceedings of the 2019 acm symposium on principles of distributed computing

PODC 2019 - Proceedings of the 2019 ACM Symposium on Princip...

引用

38th acm symposium on principles of distributed computing, PODC 2019

ISBN: (纸本)9781450362177

The proceedings contain 70 papers. The topics discussed include: composable computation in discrete chemical reaction networks;how to spread a rumor: call your neighbors or take a walk?;efficient size estimation and impossibility of termination in uniform dense population protocols;on counting the population size;self-stabilizing leader election;brief announcement: logarithmic expected-time leader election in population protocol model;brief announcement: on site fidelity and the price of ignorance in swarm robotic central place foraging algorithms;improved distributed expander decomposition and nearly optimal triangle enumeration;fast approximate shortest paths in the congested clique;brief announcement: optimal distributed covering algorithms;and with great speed come small buffers: space-bandwidth tradeoffs for routing.

关键词：

来源：评论

学校读者我要写书评

暂无评论

File Systems Unfit as distributed Storage Backends: Lessons from 10 Years of Ceph Evolution 19

File Systems Unfit as Distributed Storage Backends: Lessons ...

引用

27th acm symposium on Operating Systems principles (SOSP)

作者： Aghayev, Abutalib Weil, Sage Kuchnik, Michael Nelson, Mark Ganger, Gregory R. Amvrosiadis, George Carnegie Mellon Univ Pittsburgh PA 15213 USA Red Hat Inc Raleigh NC USA

ISBN: (纸本)9781450368735

For a decade, the Ceph distributed file system followed the conventional wisdom of building its storage backend on top of local file systems. This is a preferred choice for most distributed file systems today because it allows them to benefit from the convenience and maturity of battle-tested code. Ceph's experience, however, shows that this comes at a high price. First, developing a zero-overhead transaction mechanism is challenging. Second, metadata performance at the local level can significantly affect performance at the distributed level. third, supporting emerging storage hardware is painstakingly slow. Ceph addressed these issues with BlueStore, a new backend designed to run directly on raw storage devices. In only two years since its inception, BlueStore outperformed previous established backends and is adopted by 70% of users in production. By running in user space and fully controlling the I/O stack, it has enabled space-efficient metadata and data checksums, fast overwrites of erasure-coded data, inline compression, decreased performance variability, and avoided a series of performance pitfalls of local file systems. Finally, it makes the adoption of backwards-incompatible storage hardware possible, an important trait in a changing storage landscape that is learning to embrace hardware diversity.

关键词： Ceph object storage distributed file system storage backend file system

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：