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

arXiv 2017年

作者： Angel, Omer Mehrabian, Abbas Peres, Yuval Department of Mathematics University of British Columbia Department of Computer Science University of British Columbia Microsoft Research

For a rumour spreading protocol, the spread time is defined as the first time that everyone learns the rumour. We compare the synchronous push and pull ru-mour spreading protocol with its asynchronous variant, and show that for any n-vertex graph and any starting vertex, the ratio between their expected spread times is bounded by O n1/3log2/3 n . This improves the O(n) upper bound of Giakkoupis, Nazari, and Woelfel (in proceedings of acm symposium on principles of distributed computing, 2016). Our bound is tight up to a factor of O(log n), as illustrated by the string of diamonds graph. We also show that if for a pair , of real numbers, there exists infinitely many graphs for which the two spread times are n and n in expectation, then 0 1 and 1 3 + 2 3;and we show each such pair , is achievable. Copyright © 2017, The Authors. All rights reserved.

关键词： distributed computer systems

来源：评论

学校读者我要写书评

暂无评论

Are Shared Objects Composable under an Oblivious Adversary? 16

Are Shared Objects Composable under an Oblivious Adversary?

引用

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

作者： Denysyuk, Oksana Woelfel, Philipp Univ Calgary Dept Comp Sci Calgary AB T2N 1N4 Canada

ISBN: (纸本)9781450339643

Linearizability [5] of a concurrent object ensures that operations on that object appear to execute atomically. It is well known that linearizable implementations are composable: in an algorithm designed to work with atomic objects, replacing any atomic object with a linearizable implementation preserves the correctness of the original algorithm. However, replacing atomic objects with linearizable ones in a randomized algorithm can break the original probabilistic guarantees [3]. With an adaptive adversary, this problem is solved by using strongly linearizable [3] objects in the composition. How about with an oblivious adversary? In this paper, we ask the fundamental question of what property makes implementations composable under an oblivious adversary. It turns out that the property depends on the entire collection of objects used in the algorithm. We show that the composition of every randomized algorithm with a collection of linearizable objects OL is sound if and only if CMG satisfies a property called library homogeneity. Roughly, this property says that, for each process, every operation on OL has the same length and linearization point. This result has several important implications. First, for an oblivious adversary, there is nothing analogous to "strong linearizability" to ensure that the atomic objects of an algorithm can be replaced with their implementations. Second, in general, algorithms cannot use implemented objects alongside atomic objects provided by the system, such as registers. These results show that, with an oblivious adversary, it is much harder to implement reusable object types than previously believed.

关键词： distributed algorithms randomized algorithms shared memory linearizability

来源：评论

学校读者我要写书评

暂无评论

Fault-Tolerant Multi-Agent Optimization: Optimal Iterative distributed Algorithms 16

Fault-Tolerant Multi-Agent Optimization: Optimal Iterative D...

引用

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

作者： Su, Lili Vaidya, Nitin H. Univ Illinois Coordinated Sci Lab Elect & Comp Engn Champaign IL 61820 USA

ISBN: (纸本)9781450339643

This paper addresses the problem of distributed multi-agent optimization in which each agent i has a local cost function h(i)(x), and the goal is to optimize a global cost function consisting of an average of the local cost functions. Such optimization problems are of interest in many contexts, including distributed machine learning and distributed robotics. We consider the distributed optimization problem in the presence of faulty agents. We focus primarily on Byzantine failures, but also briefly discuss some results for crash failures. For the Byzantine fault-tolerant optimization problem, the ideal goal is to optimize the average of local cost functions of the non-faulty agents. However, this goal also cannot be achieved. Therefore, we consider a relaxed version of the fault-tolerant optimization problem. The goal for the relaxed problem is to generate an output that is an optimum of a global cost function formed as a convex combination of local cost functions of the non-faulty agents. More precisely, if N denotes the set of non-faulty agents in a given execution, then there must exist weights alpha(i) for i is an element of N such that alpha(i) >= 0 and Sigma(i is an element of N) alpha(i) = 1, such that the output is an optimum of the cost function Sigma(i is an element of N) alpha(i)h(i)(x). Ideally, we would like alpha(i) = 1/vertical bar N vertical bar for all i is an element of N, however, the maximum number of nonzero weights (alpha(i)'s) that can be guaranteed is vertical bar N vertical bar - f, where f is the maximum number of Byzantine faulty agents. The contribution of this paper is to present an iterative distributed optimization algorithm that achieves optimal fault-tolerance. Specifically, it ensures that at least vertical bar N vertical bar - f agents have weights that are bounded away from 0 (in particular, lower bounded by 1/2 (vertical bar N vertical bar - f)). The proposed distributed algorithm has a simple iterative structure, with each agent

关键词： distributed optimization Byzantine faults complete networks fault-tolerant computing

来源：评论

学校读者我要写书评

暂无评论

proceedings of the acm SIGPLAN symposium on principles and Practice of Parallel Programming, PPOPP

Proceedings of the ACM SIGPLAN Symposium on Principles and P...

引用

21st acm SIGPLAN symposium on principles and Practice of Parallel Programming, PPoPP 2016

ISBN: (纸本)9781450340922

The proceedings contain 55 papers. The topics discussed include: coarse grain parallelization of deep neural networks;high performance model based image reconstruction;exploiting accelerators for efficient high dimensional similarity search;declarative coordination of graph-based parallel programs;distributed halide;parallel type-checking with Haskell using saturating LVars and stream generators;articulation points guided redundancy elimination for betweenness centrality;multi-core on-the-fly SCC decomposition;a high-performance parallel algorithm for nonnegative matrix factorization;gunrock: a high-performance graph processing library on the GPU;keep calm and react with foresight: strategies for low-latency and energy-efficient elastic data stream processing;and work stealing for interactive services to meet target latency.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Brief announcement: Using read-κ inequalities to analyze a distributed mis algorithm 35

Brief announcement: Using read-κ inequalities to analyze a ...

引用

35th acm symposium on principles of distributed computing, PODC 2016

作者： Pemmaraju, Sriram V. Riaz, Talal Department of Computer Science University of Iowa Iowa CityIA52242-1419 United States

ISBN: (纸本)9781450339643

Until recently, the fastest distributed MIS algorithm, even for simple graphs, e.g., unoriented trees, has been the sim- ple randomized algorithm discovered in the 80s. This al- gorithm (commonly called Luby's algorithm) computes an MIS in O(log n) rounds (with high probability). This situa- tion changed when Lenzen and Wattenhofer (PODC 2011) presented a randomized O( √ log n · log log n)-round MIS al- gorithm for unoriented trees. This algorithm was improved by Barenboim et al. (FOCS 2012), resulting in an MIS al- gorithm running in O( √ log n · log log n) rounds. The analyses of these tree MIS algorithms depends on "near independence" of probabilistic events, a feature of the tree structure of the network. In their paper, Lenzen and Wattenhofer hope that their algorithm and analysis could be extended to graphs with bounded arboricity. We show how to do this in this note. By using a new tail inequal- ity for read-k families of random variables due to Gavin- sky et al. (Random Struct Algorithms, 2015), we show how to deal with dependencies induced by the recent tree MIS algorithms when they are executed on bounded arboric- ity graphs. Specifically, we analyze a version of the tree MIS algorithm of Barenboim et al. and show that it runs in O(poly() · p log n · log log n) rounds in the CONGEST model for arboricity graphs. © 2016 acm.

关键词： Graphic methods

来源：评论

学校读者我要写书评

暂无评论

TR-Spark: Transient computing for Big Data Analytics 7

TR-Spark: Transient Computing for Big Data Analytics

引用

7th acm symposium on Cloud computing (SoCC)

作者： Yan, Ying Gao, Yanjie Chen, Yang Guo, Zhongxin Chen, Bole Moscibroda, Thomas Microsoft Res Redmond WA 98052 USA

ISBN: (纸本)9781450345255

Large-scale public cloud providers invest billions of dollars into their cloud infrastructure and operate hundreds of thousands of servers across the globe. For various reasons, much of this provisioned server capacity runs at low average utilization, and there is tremendous competitive pressure to increase utilization. Conceptually, the way to increase utilization is clear: Run time-insensitive batch-job workloads as secondary background tasks whenever server capacity is underutilized;and evict these workloads when the server's primary task requires more resources. Big data analytic tasks would seem to be an ideal fit to run opportunistically on such transient resources in the cloud. In reality, however, modern distributed data processing systems such as MapReduce or Spark are designed to run as the primary task on dedicated hardware, and they perform badly on transiently available resources because of the excessive cost of cascading re-computations in case of evictions. In this paper, we propose a new framework for big data analytics on transient resources. Specifically, we design and implement TR-Spark, a version of Spark that can run highly efficiently as a secondary background task on transient (evictable) resources. The design of TR-Spark is based on two principles: resource stability and data size reduction-aware scheduling and lineage-aware checkpointing. The combination of these principles allows TR-Spark to naturally adapt to the stability characteristics of the underlying compute infrastructure. Evaluation results show that while regular Spark effectively fails to finish a job in clusters of even moderate instability, TR-Spark performs nearly as well as Spark running on stable resources.

关键词： Transient computing Spark Checkpointing

来源：评论

学校读者我要写书评

暂无评论

The cat theorem and performance of transactional distributed systems 4

The cat theorem and performance of transactional distributed...

引用

4th Annual acm PODC Workshop on distributed Cloud computing, DCC 2016

作者： Ahsan, Shegufta Bakht Gupta, Indranil Department of Computer Science University of Illinois Urbana Champaign United States Department of Computer Science University of Illinois Urbana Champaign United States

ISBN: (纸本)9781450342209

We argue that transactional distributed database/storage systems need to view the impossibility theorem in terms of the contention, abort rate, and throughput, rather than via the traditional CAP theorem. Motivated by Jim Gray, we state a new impossibility theorem, which we call the CAT theorem (Contention-Abort-Throughput). We present experimental results from the performance of several transactional systems w.r.t. the CAT impossibility spectrum. © 2016 acm.

关键词： Throughput

来源：评论

学校读者我要写书评

暂无评论

2nd International Workshop on Adaptive Resource Management and Scheduling for Cloud computing, ARMS-CC 2015 held in Conjunction with acm symposium on principles of distributed computing, PODC 2015

2nd International Workshop on Adaptive Resource Management a...

引用

2nd International Workshop on Adaptive Resource Management and Scheduling for Cloud computing, ARMS-CC 2015

ISBN: (纸本)9783319284477

The proceedings contain 13 papers. The special focus in this conference is on Adaptive Resource Management and Scheduling for Cloud computing. The topics include: Competitive analysis of task scheduling algorithms on a fault-prone machine and the impact of resource augmentation;using performance forecasting to accelerate elasticity;parametric analysis of mobile cloud computing frameworks using simulation modeling;bandwidth-aware resource optimization for SMT processors;user-guided provisioning in federated clouds for distributed calculations;a case of mobile-cloud collaborative computing under mobility;impact of virtual machines heterogeneity on data center power consumption in data-intensive applications;implementing the cloud software to data approach for openstack environments;cloud services composition through cloud patterns;a performance evaluation of hadoop’s schedulers under failures;partitioning graph databases by using access patterns and challenges and methodologies for acceleration.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Optimal mobile byzantine fault tolerant distributed storage: [Extended Abstract] 16

Optimal mobile byzantine fault tolerant distributed storage:...

引用

35th acm symposium on principles of distributed computing, PODC 2016

作者： Bonomi, Silvia Del Pozzo, Antonella Potop-Butucaru, Maria Tixeuil, Sébastien DIAG University of Rome la Sapienza Rome Italy Sorbonne Universités UPMC LIP6-CNRS 7606 Paris France

ISBN: (纸本)9781450339643

We present an optimal emulation of a server based regular read/write storage in a synchronous round-free messagepassing system that is subject to mobile Byzantine failures and prove that the problem is impossible to solve in asynchronous settings. In a system with n servers implementing a regular register, our construction tolerates faults (or attacks) that can be abstracted by agents that are moved (in an arbitrary and unforeseen manner) by a computationally unbounded adversary from a server to another in order to deviate the server's computation. When a server is infected by an adversarial agent, it behaves arbitrarily until the adversary decides to "move" the agent to another server. We investigate the case where the movements of the mobile Byzantine agents are decided by the adversary and are completely decoupled from the message communication delay. Our emulation spans two awareness models: servers with and without self-diagnosis mechanism. In the first case servers are aware that the mobile Byzantine agent has left and hence they can stop running the protocol until they recover a correct state while in the second case, servers are not aware of their faulty state and continue to run the protocol using an incorrect local state. Our results, proven optimal with respect to the threshold of the tolerated mobile Byzantine faults in the first model, are significantly different from the round-based synchronous models. Another interesting side result of our study is that, contrary to the round-based synchronous consensus implementation for systems prone to mobile Byzantine faults, our storage emulation does not rely on the necessity of a core of correct processes all along the computation. That is, every server in the system can be compromised by the mobile Byzantine agents at some point in the computation. This leads to another interesting conclusion: storage is easier than consensus in synchronous settings, when the system is hit by mobile Byzantine failures. © 2016

关键词： Mobile agents

来源：评论

学校读者我要写书评

暂无评论

distributed strong diameter network decomposition: [Extended Abstract] 16

Distributed strong diameter network decomposition: [Extended...

引用

35th acm symposium on principles of distributed computing, PODC 2016

作者： Elkin, Michael Neiman, Ofer Department of Computer Science Ben-Gurion University of the Negev Beer-Sheva Israel

ISBN: (纸本)9781450339643

For a pair of positive parameters D,x, a partition P of the vertex set V of an n-vertex graph G = (V,E) into disjoint clusters of diameter at most D each is called a (D,x) net- work decomposition, if the supergraph G(P), obtained by contracting each of the clusters of P, can be properly x- colored. The decomposition P is said to be strong (resp., weak) if each of the clusters has strong (resp., weak) diame- ter at most D, i.e., if for every cluster C ϵ P and every two vertices u;v ϵ C, the distance between them in the induced graph G(C) of C (resp., in G) is at most D. Network decomposition is a powerful construct, very use- ful in distributed computing and beyond. It was introduced by Awerbuch et. al. [AGLP89] in the end of the eighties. These authors showed that strong (2O(√log n log log n);2O(√log n log log n)) network decompositions can be computed in 2O(√log n log log n) distributed time. Their result was improved at the beginning of nineties by Pan- conesi and Srinivasan [PS92], who showed that 2O(√log n log log n) in all the three expressions can be replaced by 2O(√log n). Around the same time Linial and Saks [LS93] devised an ingenious randomized algorithm that constructs weak (O(log n);O(log n)) network decompositions in O(log2 n) time. Awerbuch et. al. [ABCP96] devised a randomized al- gorithm that builds a strong (O(log n);O(log n)) network decomposition in O(log4 n) time, using very large messages and heavy local computations. It was however open till now if strong network decompositions with both parame-ters 2O(√log n) can be constructed in distributed 2O(√log n) time using short messages, or if a result of [LS93] can be strengthened to provide a strong (O(log n);O(log n)) net- work decomposition within O(log2 n) time (even using large messages). In this paper we answer these long-standing open ques- tions in the afirmative, and show that strong (O(log n);O(log n)) network decompositions can be computed in O(log2 n) time. We also present a tradeo betwee

关键词： distributed computer systems

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：