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

27th annual ACM symposium on principles of distributed computing

作者： Barenboim, Leonid Elkin, Michael Ben Gurion Univ Negev Dept Comp Sci IL-84105 Beer Sheva Israel

ISBN: (纸本)9781595939890

We study the distributed maximal independent set (henceforth, MIS) problem on sparse graphs. Currently, there are known algorithms with a sublogarithmic running time for this problem on oriented trees and graphs of bounded degrees. We devise the first sublogarithmic algorithm for computing an MIS on graphs of bounded arboricity. This is a large family of graphs that includes graphs of bounded degree, planar graphs, graphs of bounded genus, graphs of bounded treewidth, graphs that exclude a fixed minor, and many other graphs. We also devise efficient algorithms for coloring graphs from these families. These results are achieved by the following technique that may be of independent interest. Our algorithm starts with computing a certain graph-theoretic structure, called Nash-Williams forests-decomposition. Then this structure is used to compute the MIS or coloring. Our results demonstrate that this methodology is very powerful. Finally, we show nearly-tight lower bounds on the running time of any distributed algorithm for computing a forests-decomposition.

关键词： MIS Coloring Arboricity Forests-decomposition

来源：评论

学校读者我要写书评

暂无评论

Optimal Gossip-Based Aggregate Computation 10

Optimal Gossip-Based Aggregate Computation

引用

22nd ACM symposium on Parallelism in Algorithms and Architectures

作者： Chen, Jen-Yeu Pandurangan, Gopal Natl Dong Hwa Univ Dept Elect Engn Shoufeng 97401 Hualien Taiwan

ISBN: (纸本)9781450300797

Motivated by applications to modern networking technologies, there has been interest in designing efficient gossip-based protocols for computing aggregate functions While gossip-based protocols provide robustness due to their randomized nature, reducing the message and time complexity of these protocols is also of paramount importance in the context of resource-constrained networks such as sensor and peer-to-peer networks We present the first provably almost-optimal gossip-based algorithms for aggregate computation that are both time optimal and message-optimal. Given a n-node network, our algorithms guarantee that all the nodes can compute the common aggregates (such as Min, Max, Count. Sum, Average, Rank etc) of their values in optimal O(log n) time and using O(n log log n) messages Our result improves on the algorithm of Kempe et al [II] that is time-optimal, but uses O(n log n) messages as well as on the algorithm of Kashyap et al [10] that uses O(n Jog log n) messages, but is not time-optimal (takes O(log n log log n) time). Furthermore, we show that our algorithms can be used to improve gossip-based aggregate computation in sparse communication networks, such as in peer-to-peer networks The main technical ingredient of our algorithm is a technique called distributed random ranking (DRR) that can be useful in other applications as well DRR gives an efficient distributed procedure to partition the network into a forest of (disjoint) trees of small size. Since the size of each tree is small, aggregates within each tree can be efficiently obtained at their respective roots All the roots then perform a uniform gossip algorithm on their local aggregates to reach a distributed consensus on the global aggregates Our algorithms are non-address oblivious In contrast, we show a lower bound of Omega(n log n) on the message complexity of any address-oblivious algorithm for computing aggregates. This shows that non-address oblivious algorithms are needed to obtain significa

关键词： Gossip-based protocols aggregate computation distributed randomized protocols probabilistic analysis lower bounds

来源：评论

学校读者我要写书评

暂无评论

Multi-Sided Shared Coins and Randomized Set-Agreement 10

Multi-Sided Shared Coins and Randomized Set-Agreement

引用

22nd ACM symposium on Parallelism in Algorithms and Architectures

作者： Hillel, Keren Censor Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel

ISBN: (纸本)9781450300797

This paper presents wait-free randomized algorithms for solving set-agreement in asynchronous shared-memory systems under a strong adversary first, the definition of a shared-coin algorithm is generalized to a multi-sided shared-coin algorithm, and it is shown how to use any multi-sided shared coin in order to obtain a randomized set-agreement algorithm for agreeing on k values out of k + 1 Then, an implementation is given for a (k + 1)-sided shared coin for n processes with a constant agreement parameter, O(n(2)/k) total step complexity. and O(n/k) individual step complexity This implementation yields a randomized set-agreement algorithm for agreeing on k values out of k + 1 with a total step complexity of O(n(2)/k + nk) and an individual step complexity of O(n/k + k) Next, other set-agreement algorithms for agreeing on E values out of k + 1, where e is smaller than k, are presented This includes the case of multi-valued consensus in which l = 1, k > 1 To the best of our knowledge, these are the first wait-free algorithms for set-agreement in the asynchronous shared-memory model under a strong adversary that are not for the specific case of binary consensus, where l = k = 1 Finally, an application of asynchronous wait-free multi-valued consensus is presented, in implementing at-most-once semantics with optimal effectiveness.

关键词： distributed computing shared memory randomized algorithms set-agreement multi-valued shared coins

来源：评论

学校读者我要写书评

暂无评论

Datalog Redux: Experience and Conjecture 10

Datalog Redux: Experience and Conjecture

引用

29th ACM SIGMOD-SIGACT-SIGART symposium on principles of Database Systems

作者： Hellerstein, Joseph M. UC Berkeley EECS Comp Sci Div Berkeley CA 94720 USA

ISBN: (纸本)9781450300339

There is growing urgency in computer science circles regarding an impending crisis in parallel programming. Emerging computing platforms, from multicore processors to cloud computing, predicate their performance growth on the development of software to harness parallelism. For the first time in the history of computing, the progress of Moore's Law depends on the productivity of software engineers. Unfortunately, parallel and distributed programming today is challenging even for the best programmers, and simply unworkable for the majority. There has never been a more urgent need for breakthroughs in programming models and languages. While parallel programming in general is considered very difficult, data parallelism has been very successful. The relational algebra parallelizes easily over large datasets, and SQL programmers have long reaped the benefits of parallelism without modifications to their code. This point has been rediscovered and amplified via recent enthusiasm for Map Reduce programming and "Big Data", which have turned data parallelism into common culture across computing. As a result, it is increasingly attractive to tackle the challenge of parallel programming on the firm common ground of data parallelism: start with an easy-to-parallelize - kernel relational algebra and extend it to general-purpose computation. This approach has clear precedents in database theory, where it has long been known that classical relational languages have natural Turing-complete extensions. At the same time that this crisis has been evolving, variants of Datalog have been seen cropping up in a wide range of practical settings, from security to robotics to compiler analysis. Over the past seven years, we have been exploring the use of Datalog-inspired languages in a variety of systems projects, with a focus on inherently parallel tasks in networking and distributed systems. The experience has been largely positive: we have demonstrated full-featured Datalog-based system imp

关键词： Datalog distributed Systems Cloud computing Parallelism Overlog BOOM Dedalus Bloom

来源：评论

学校读者我要写书评

暂无评论

computing the Throughput of Probabilistic and Replicated Streaming Applications 10

Computing the Throughput of Probabilistic and Replicated Str...

引用

22nd ACM symposium on Parallelism in Algorithms and Architectures

作者： Benoit, Anne Dufosse, Fanny Gallet, Matthieu Robert, Yves Gaujal, Bruno ENS Lyon Lyon France

ISBN: (纸本)9781450300797

In this paper. we investigate how to compute the throughput of probabilistic and replicated streaming applications. We are given (i) a streaming application whose dependence graph is a linear chain, (ii) a one-to-many mapping of the application onto a fully heterogeneous target. where a processor is assigned at most one application stage, but where a stage can be replicated onto a set of processors;and (iii) a set of I.I D (independent and Identically-distributed) variables to model each computation and communication time in the mapping How can we compute the throughput of the application, i e the rate at which data sets can be processed? We consider two execution models, the Strict model where the actions of each processor are sequentializecl, and the Overlap model where a processor can compute and communicate in parallel The problem is easy when application stages are not replicated, i e, assigned to a single processor: in that case the throughput is dictated by the critical hardware resource However, when stages are replicated, i e, assigned to several processors, the problem becomes surprisingly complicated: even in the deterministic case, the optimal throughput may be lower than the smallest internal resource throughput To the best of our knowledge, the problem has never been considered in the probabilistic case The first main contribution of the paper is to provide a general method (although of exponential cost) to compute the throughput when mapping parameters follow I.I.D exponential laws. This general method is based upon the analysis of timed Petri nets deduced from the application mapping, it turns out that these Petri nets exhibit a regular structure in the Overlap model, thereby enabling to reduce the cost and provide a polynomial algorithm The second main contribution of the paper is to provide bounds for the throughput when stage parameters are arbitrary I I.D and N.B.U E (New Better than Used in Expectation) variables the throughput is bounded from b

关键词： scheduling probabilistic streaming applications replication throughput timed Petri nets

来源：评论

学校读者我要写书评

暂无评论

How to meet asynchronously (almost) everywhere 10

How to meet asynchronously (almost) everywhere

引用

annual ACM-Society for Industrial and Applied Mathmatics symposium on Discrete Algorithms

作者： Jurek Czyzowicz Arnaud Labourel Andrzej Pelc Departement d'informatique Universite du Quebecen Partially supported by NSERC Departement d'informatique Universite du Quebecen Supported by the ANR-project "ALADDIN" Departement d'informatique Universite du Quebecen Partially supported by NSERC discovery grant and by the Research Chair in Distributed Computing at the Universite du Quebec en Outaouais

ISBN: (纸本)9780898717013

Two mobile agents (robots) with distinct labels have to meet in an arbitrary, possibly infinite, unknown connected graph or in an unknown connected terrain in the plane. Agents are modeled as points, and the route of each of them only depends on its label and on the unknown environment. The actual walk of each agent also depends on an asynchronous adversary that may arbitrarily vary the speed of the agent, stop it, or even move it back and forth, as long as the walk of the agent in each segment of its route is continuous, does not leave it and covers all of it. Meeting in a graph means that both agents must be at the same time in some node or in some point inside an edge of the graph, while meeting in a terrain means that both agents must be at the same time in some point of the terrain. Does there exist a deterministic algorithm that allows any two agents to meet in any unknown environment in spite of this very powerful adversary? We give deterministic rendezvous algorithms for agents starting at arbitrary nodes of any anonymous connected graph (finite or infinite) and for agents starting at any interior points with rational coordinates in any closed region of the plane with path-connected interior. While our algorithms work in a very general setting-agents can, indeed, meet almost everywhere - we show that none of the above few limitations imposed on the environment can be removed. On the other hand, our algorithm also guarantees the following approximate rendezvous for agents starting at arbitrary interior points of a terrain as above: agents will eventually get at an arbitrarily small positive distance from each other.

关键词： Agents internal point terrains lamb meat landscapes Asynchronous deterministic algorithms Infinite Unknown plane Platanus hybrida rendezvous Connected graph

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement. The Price of Anonymity: Optimal Consensus despite Asynchrony, Crash and Anonymity

Brief Announcement. The Price of Anonymity: Optimal Consensu...

引用

28th annual ACM symposium on principles of distributed computing

作者： Bonnet, Francois Raynal, Michel Univ Rennes 1 IRISA Rennes France

This paper proposes the first study of the consensus problem in the anonymous crash-prone message-passing systems.

ISBN: (纸本)9781605583969

This paper proposes the first study of the consensus problem in the anonymous crash-prone message-passing systems.

关键词： Anonymous systems distributed agreement

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: Self-Assembly as Graph Grammar as distributed System

Brief Announcement: Self-Assembly as Graph Grammar as Distri...

引用

28th annual ACM symposium on principles of distributed computing

作者： Sterling, Aaron Iowa State Univ Dept Comp Sci Lab Nanoscale Self Assembly Ames IA 50011 USA

ISBN: (纸本)9781605583969

In 2004, Klavins et al. introduced the use of graph grammars to describe-and to program-systems of self-assembly. It turns out that these graph grammars can be embedded in a graph rewriting characterization of distributed systems that was proposed by Degano and Montanari over twenty years ago. By applying techniques obtained from this observation, we prove a generalized version of Soloveichik and Winfree's theorem on local determinism. We also obtain a canonical method to simulate asynchronous constant-size-message-passing models of distributed computing with systems of self-assembly.

关键词： Self-Assembly Graph Grammar Graph Assembly System Grammars for distributed Systems

来源：评论

学校读者我要写书评

暂无评论

An algorithm for clock synchronization with the gradient property in sensor networks

引用

JOURNAL OF PARALLEL AND distributed computing 2009年第3期69卷 261-265页

作者： Pussente, Rodolfo M. Barbosa, Valmir C. Univ Fed Rio de Janeiro COPPE Programa Engn Sistemas & Computacao BR-21941972 Rio De Janeiro Brazil

We introduce a distributed algorithm for clock synchronization in sensor networks. Our algorithm assumes that nodes in the network only know their immediate neighborhoods and an upper bound on the network's diameter. Clock-synchronization messages are only sent as part of the communication-assumed to be reasonably frequent-that already takes place among nodes. The algorithm has the gradient property of [R. Fan, N. Lynch, Gradient clock synchronization, distributed computing 18 (2006) 255-266], achieving an O(1) worst-case skew between the logical clocks of neighbors. The algorithm's actions are such that no constant lower bound exists on the rate at which logical clocks progress in time, and for this reason the lower bound of [R. Fan, N. Lynch, Gradient clock synchronization, distributed computing 18 (2006) 255-266;L Meier, L Thiele, Brief announcement: Gradient clock synchronization in sensor networks, in: proceedings of the twenty-Fourth annual ACM symposium on principles of distributed computing, 2005, p. 238] that forbids a constant clock skew between neighbors does not apply. (C) 2008 Elsevier Inc. All rights reserved.

关键词： distributed computing Sensor networks Clock synchronization Gradient property in clock synchronization

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: A Platform for Experimenting with Mobile Algorithms in a Laboratory

Brief Announcement: A Platform for Experimenting with Mobile...

引用

28th annual ACM symposium on principles of distributed computing

作者： Killijian, Marc-Olivier Roy, Matthieu LAAS CNRS F-31077 Toulouse France

ISBN: (纸本)9781605583969

In this work, we present a platform for testing algorithms on mobile systems. We advocate that the interest of the platform lies in many aspects: it shows that simulators are not accurate, especially with regards to wireless communication and delays assumptions. Such a platform can be used to refine simulators assumptions. Moreover, to the best of our knowledge, our platform is the first attempt to implement mobility patterns, that permit to test multiple distributed algorithms in the same movement configuration, allowing for reproducible experiments. Last, but not least, we want to open our platform to test other distributed and mobile algorithms, with the hope that it will open new problems and pose new challenges.

关键词： distributed computer systems

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：