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

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

来源：评论

学校读者我要写书评

暂无评论

Exact Byzantine Consensus on Undirected Graphs under Local Broadcast Model 19

Exact Byzantine Consensus on Undirected Graphs under Local B...

引用

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

作者： Khan, Muhammad Samir Naqvi, Syed Shalan Vaidya, Nitin H. Univ Illinois Champaign IL 61820 USA Georgetown Univ Washington DC USA

ISBN: (纸本)9781450362177

This paper considers the Byzantine consensus problem for nodes with binary inputs. The nodes are interconnected by a network represented as an undirected graph, and the system is assumed to be synchronous. Under the classical point-to-point communication model, it is well-known that the following two conditions are both necessary and sufficient to achieve Byzantine consensus among n nodes in the presence of up to f Byzantine faulty nodes: n >= 3f + 1 and vertex connectivity at least 2f +1. In the classical point-to-point communication model, it is possible for a faulty node to equivocate, i.e., transmit conflicting information to different neighbors. Such equivocation is possible because messages sent by a node to one of its neighbors are not overheard by other neighbors. This paper considers the local broadcast model. In contrast to the point-to-point communication model, in the local broadcast model, messages sent by a node are received identically by all of its neighbors. Thus, under the local broadcast model, attempts by a node to send conflicting information can be detected by its neighbors. Under this model, we show that the following two conditions are both necessary and sufficient for Byzantine consensus: vertex connectivity at least left perpendicular3f /2right perpendicular + 1 and minimum node degree at least 2f. Observe that the local broadcast model results in a lower requirement for connectivity and the number of nodes n, as compared to the point-to-point communication model. We extend the above results to a hybrid model that allows some of the Byzantine faulty nodes to equivocate. The hybrid model bridges the gap between the point-to-point and local broadcast models, and helps to precisely characterize the trade-off between equivocation and network requirements.

关键词： complexity and impossibility results for distributed computing fault-tolerance reliability self-organization self-stabilization

来源：评论

学校读者我要写书评

暂无评论

distributed and Streaming Linear Programming in Low Dimensions 19

Distributed and Streaming Linear Programming in Low Dimensio...

引用

38th acm SIGMOD-SIGACT-SIGAI symposium on principles of Database Systems (PODS)

作者： Assadi, Sepehr Karpov, Nikolai Zhang, Qin Princeton Univ Princeton NJ 08544 USA Indiana Univ Bloomington IN USA

ISBN: (纸本)9781450362276

We study linear programming and general LP-type problems in several big data (streaming and distributed) models. We mainly focus on low dimensional problems in which the number of constraints is much larger than the number of variables. Low dimensional LP-type problems appear frequently in various machine learning tasks such as robust regression, support vector machines, and core vector machines. As supporting large-scale machine learning queries in database systems has become an important direction for database research, obtaining efficient algorithms for low dimensional LP-type problems on massive datasets is of great value. In this paper we give both upper and lower bounds for LP-type problems in distributed and streaming models. Our bounds are almost tight when the dimensionality of the problem is a fixed constant.

关键词： distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

An energy management system at the edge based on reinforcement learning 20

An energy management system at the edge based on reinforceme...

引用

proceedings of the IEEE/acm 24th International symposium on distributed Simulation and Real Time Applications

作者： F. Cicirelli A. F. Gentile E. Greco A. Guerrieri G. Spezzano A. Vinci National Research Council of Italy Italy

In this work, we propose an IoT edge-based energy management system devoted to minimizing the energy cost for the daily-use of in-home appliances. The proposed approach employs a load scheduling based on a load shifting technique, and it is designed to operate in an edge-computing environment naturally. The scheduling considers all together time-variable profiles for energy cost, energy production, and energy consumption for each shiftable appliance. Deadlines for load termination can also be expressed. In order to address these goals, the scheduling problem is formulated as a Markov decision process and then processed through a reinforcement learning technique. The approach is validated by the development of an agent-based real-world test case deployed in an edge context.

关键词： internet of things edge computing multi-agent systems energy management systems reinforcement learning

来源：评论

学校读者我要写书评

暂无评论

Engineering distributed Systems that We Can Trust (and Also Run) 19

Engineering Distributed Systems that We Can Trust (and Also ...

引用

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

作者： Sergey, Ilya Yale NUS Coll Singapore Singapore Natl Univ Singapore Singapore Singapore

ISBN: (纸本)9781450362177

The interest in formal methods and verification of correctness-critical distributed systems is on the rise in the past few years. But what are the gains from proving statements about software in full mathematical rigour? Do they justify the high cost of verification? And how far can we extend our trust in formal methods when talking about realistic distributed systems and their client programs?This talk is in three parts. First, I will provide an overview of the state of the art in machine-assisted reasoning about distributed consensus protocols, their implementations, and applications. Next, I will discuss the trade-offs that have to be made in order to enable mechanised proofs about runnable systems code, as well as implications of the assumptions made to describe the real-world execution environments. Lastly, I will focus on the ongoing work propelled by the programming languages community towards engineering modular proofs about distributed protocols-a way to build correct-by-construction composite systems from verified reusable components.

关键词： Verification Formal Methods distributed Systems Proofs Modularity

来源：评论

学校读者我要写书评

暂无评论

A Round-Efficient distributed Betweenness Centrality Algorithm 19

A Round-Efficient Distributed Betweenness Centrality Algorit...

引用

24th acm SIGPLAN symposium on principles and Practice of Parallel Programming (PPoPP)

作者： Hoang, Loc Pontecorvi, Matteo Dathathri, Roshan Gill, Gurbinder You, Bozhi Pingali, Keshav Ramachandran, Vijaya Univ Texas Austin Austin TX 78712 USA Nokia Bell Labs Paris France Xi An Jiao Tong Univ Xian Peoples R China

ISBN: (纸本)9781450362252

We present Min-Rounds BC (MRBC), a distributed-memory algorithm in the CONGEST model that computes the betweenness centrality (BC) of every vertex in a directed unweighted n-node graph in O(n) rounds. Min-Rounds BC also computes all-pairs-shortest-paths (APSP) in such graphs. It improves the number of rounds by at least a constant factor over previous results for unweighted directed APSP and for unweighted BC, both directed and undirected. We implemented MRBC in D-Galois, a state-of-the-art distributed graph analytics system, incorporated additional optimizations enabled by the D-Galois model, and evaluated its performance on a production cluster with up to 256 hosts using power-law and road networks. Compared to the BC algorithm of Brandes, on average, MRBC reduces the number of rounds by 14.0x and the communication time by 2.8x for the graphs in our test suite. As a result, MRBC is 2.1x faster on average than Brandes BC for real-world web-crawls on 256 hosts.

关键词： Web crawler

来源：评论

学校读者我要写书评

暂无评论

Towards the Locality of Vizing's Theorem 2019

Towards the Locality of Vizing's Theorem

引用

51st Annual acm SIGACT symposium on Theory of computing (STOC)

作者： Su, Hsin-Hao Vu, Hoa T. Boston Coll Chestnut Hill MA 02167 USA

ISBN: (纸本)9781450367059

Vizing showed that it suffices to color the edges of a simple graph using Delta + 1 colors, where Delta is the maximum degree of the graph. However, up to this date, no efficient distributed edge-coloring algorithm is known for obtaining such coloring, even for constant degree graphs. The current algorithms that get closest to this number of colors are the randomized (Delta + (Theta) over tilde(root Delta))-edge-coloring algorithm that runs in polylog( n) rounds by Chang et al. [SODA 2018] and the deterministic (Delta + polylog(n))-edge-coloring algorithm that runs in poly(Delta, log n) rounds by Ghaffari et al. [STOC 2018]. We present two distributed edge-coloring algorithms that run in poly(Delta, log n) rounds. The first algorithm, with randomization, uses only Delta + 2 colors. The second algorithm is a deterministic algorithm that uses Delta + O(log n/log log n) colors. Our approach is to reduce the distributed edge-coloring problem into an online and restricted version of balls-into-bins problem. If l is the maximum load of the bins, our algorithm uses Delta + 2l - 1 colors. We show how to achieve l = 1 with randomization and l = O(log n/log log n) without randomization.

关键词： distributed algorithms edge coloring randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Exact Gaussian Process Regression with distributed Computations 19

Exact Gaussian Process Regression with Distributed Computati...

引用

34th acm/SIGAPP Annual International symposium on Applied computing (SAC)

作者： Duc-Trung Nguyen Filippone, Maurizio Michiardi, Pietro EURECOM Campus Sophia Tech Biot France

ISBN: (纸本)9781450359337

Gaussian Processes (GPs) are powerful non-parametric Bayesian models for function estimation, but suffer from high complexity in terms of both computation and storage. To address such issues, approximation methods have flourished in the literature, including model approximations and approximate inference. However, these methods often sacrifice accuracy for scalability. In this work, we present the design and evaluation of a distributed method for exact GP inference, that achieves true model parallelism using simple, high-level distributed computing frameworks. Our experiments show that exact inference at scale is not only feasible, but it also brings substantial benefits in terms of low error rates and accurate quantification of uncertainty.

关键词： Regression Matrix Factorization distributed computing

来源：评论

学校读者我要写书评

暂无评论

Editorial message: Special track on dependable, adaptive and trustworthy distributed systems

Proceedings of the ACM Symposium on Applied Computing

引用

proceedings of the acm symposium on Applied computing 2020年 230-231页

作者： Goeschka, Karl M. Oliveira, Rui Pietzuch, Peter Russello, Giovanni UAS Technikum Vienna Austria Universidade Do Minho Portugal Imperial College London United Kingdom University of Auckland New Zealand

来源：评论

学校读者我要写书评

暂无评论

Accelerating distributed stochastic gradient descent with Adaptive Periodic Parameter Averaging 19

Accelerating distributed stochastic gradient descent with Ad...

引用

24th acm SIGPLAN symposium on principles and Practice of Parallel Programming, PPoPP 2019

作者： Jiang, Peng Agrawal, Gagan Department of Computer Science and Engineering Ohio State University ColumbusOH United States

ISBN: (纸本)9781450362252

Communication overhead is a well-known performance bottleneck in distributed Stochastic Gradient Descent (SGD), which is a popular algorithm to perform optimization in large-scale machine learning tasks. In this work, we propose a practical and effective technique, named Adaptive Periodic Parameter Averaging, to reduce the communication overhead of distributed SGD, without impairing its convergence property. © 2019 Copyright held by the owner/author(s).

关键词： Stochastic systems

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：