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

29th IEEE International Conference on Data Engineering (ICDE)

作者： Rastogi, Vibhor Machanavajjhala, Ashwin Chitnis, Laukik Das Sarma, Anish Google 1600 Amphitheatre Pkwy Mountain View CA 94041 USA Duke Univ Dept Comp Sci Durham NC 27708 USA

ISBN: (纸本)9781467349093;9781467349086

Given a large graph G = (V, E) with millions of nodes and edges, how do we compute its connected components efficiently? Recent work addresses this problem in map-reduce, where a fundamental trade-off exists between the number of map-reduce rounds and the communication of each round. Denoting d the diameter of the graph, and n the number of nodes in the largest component, all prior techniques for map-reduce either require a linear, Theta(d), number of rounds, or a quadratic, Theta(n vertical bar V vertical bar + vertical bar E vertical bar), communication per round. We propose here two efficient map-reduce algorithms: (i) Hash-Greater-to-Min, which is a randomized algorithm based on PRAM techniques, requiring O(log n) rounds and O(vertical bar V vertical bar + vertical bar E vertical bar) communication per round, and (ii) Hash-to-Min, which is a novel algorithm, provably finishing in O(log n) iterations for path graphs. The proof technique used for Hash-to-Min is novel, but not tight, and it is actually faster than Hash-Greater-to-Min in practice. We conjecture that it requires 2 log d rounds and 3(vertical bar V vertical bar + vertical bar E vertical bar) communication per round, as demonstrated in our experiments. Using secondary sorting, a standard map-reduce feature, we scale Hash-to-Min to graphs with very large connected components. Our techniques for connected components can be applied to clustering as well. We propose a novel algorithm for agglomerative single linkage clustering in map-reduce. This is the first map-reduce algorithm for clustering in at most O(log n) rounds, where n is the size of the largest cluster. We show the effectiveness of all our algorithms through detailed experiments on large synthetic as well as real-world datasets.

关键词： connected component Rounding off Communication Research Ganglia randomized algorithms Cluster Analysis algorithms

来源：评论

学校读者我要写书评

暂无评论

Byzantine Agreement in Polynomial Expected Time

Byzantine Agreement in Polynomial Expected Time

引用

45th Annual ACM Symposium on the Theory of Computing (STOC)

作者： King, Valerie Saia, Jared Univ Victoria Dept Comp Sci POB 3055 Victoria BC V8W 3P6 Canada Univ New Mexico Dept Comp Sci Albuquerque NM 87131 USA

ISBN: (纸本)9781450320290

In the classic asynchronous Byzantine agreement problem, communication is via asynchronous message-passing and the adversary is adaptive with full information. In particular, the adversary can adaptively determine which processors to corrupt and what strategy these processors should use as the algorithm proceeds;the scheduling of the delivery of messages is set by the adversary, so that the delays are unpredictable to the algorithm;and the adversary knows the states of all processors at any time, and is assumed to be computationally unbounded. Such an adversary is also known as "strong". We present a polynomial expected time algorithm to solve asynchronous Byzantine Agreement with a strong adversary that controls up to a constant fraction of the processors. This is the first improvement in running time for this problem since Ben-Or's exponential expected time solution in 1983. Our algorithm tolerates an adversary that controls up to a 1/500 fraction of the processors.

关键词： Byzantine Agreement Distributed Computing randomized algorithms Consensus

来源：评论

学校读者我要写书评

暂无评论

Gossip Protocols for Renaming and Sorting 1

引用

27th International Symposium on Distributed Computing (DISC)

作者： Giakkoupis, George Kermarrec, Anne-Marie Woelfel, Philipp INRIA Rennes Bretagne Atlantic Rennes France Univ Calgary Dept Comp Sci Calgary AB Canada

ISBN: (数字)9783642415272

ISBN: (纸本)9783642415272;9783642415265

We devise efficient gossip-based protocols for some fundamental distributed tasks. The protocols assume an n-node network supporting point-to-point communication, and in every round, each node exchanges information of size O(log n) bits with (at most) one other node. We first consider the renaming problem, that is, to assign distinct IDs from a small ID space to all nodes of the network. We propose a renaming protocol that divides the ID space among nodes using a natural push or pull approach, achieving logarithmic round complexity with ID space {1, ... , (1 + epsilon)n}, for any fixed epsilon > 0. A variant of this protocol solves the tight renaming problem, where each node obtains a unique ID in {1,..., n}, in O(log(2) n) rounds. Next we study the following sorting problem. Nodes have consecutive IDs 1 up to n, and they receive numerical values as inputs. They then have to exchange those inputs so that in the end the input of rank k is located at the node with ID k. Jelasity and Kermarrec [20] suggested a simple and natural protocol, where nodes exchange values with peers chosen uniformly at random, but it is not hard to see that this protocol requires Omega(n) rounds. We prove that the same protocol works in O(log(2) n) rounds if peers are chosen according to a non-uniform power law distribution.

关键词： renaming sorting gossip protocols epidemic protocols distributed algorithms randomized algorithms network algorithms

来源：评论

学校读者我要写书评

暂无评论

The Sensitivity of the Number of Clusters in a Gaussian Mixture Model to Prior Distributions

引用

MATHEMATICS IN COMPUTER SCIENCE 2013年第4期7卷 401-420页

作者： Cruz, Cristian Leao, William Lima Rohde, David Univ Fed Rio de Janeiro Inst Matemat Rio De Janeiro Brazil Univ Queensland Dept Geog Planning & Environm Management Brisbane Qld Australia

One of the main advantages of Bayesian approaches is that they offer principled methods of inference in models of varying dimensionality and of models of infinite dimensionality. What is less widely appreciated is how the model inference is sensitive to prior distributions and therefore how priors should be set for real problems. In this paper prior sensitivity is considered with respect to the problem of inference in Gaussian mixture models. Two distinct Bayesian approaches have been proposed. The first is to use Bayesian model selection based upon the marginal likelihood;the second is to use an infinite mixture model which 'side steps' model selection. Explanations for the prior sensitivity are given in order to give practitioners guidance in setting prior distributions. In particular the use of conditionally conjugate prior distributions instead of purely conjugate prior distributions are advocated as a method for investigating prior sensitivity of the mean and variance individually.

关键词： Density estimation Learning and adaptive systems randomized algorithms Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

An Investigation on Wide-Area Networks Based on randomized algorithms

An Investigation on Wide-Area Networks Based on Randomized A...

引用

2009 Asia-Pacific Conference on Information Processing

作者： Xuejun Yang Library Changsha University of Science and Technology Changsha 410004,China Hong Wang School of Civil Engineering Hunan University Changsha 410082,China

Many scholars would agree that,had it not been for the evaluation of gigabit switches,the analysis of massive multiplayer online role-playing games might never have *** fact,few experts would disagree with the intuitive unification of superblocks and the location-identity split,which embodies the confirmed principles of *** construct new heterogeneous communication(BACK),which we use to verify that red-black trees and the location-identity split are rarely incompatible.

关键词： wide-area networks randomized algorithms heterogeneous communication

来源：评论

学校读者我要写书评

暂无评论

An Algorithm of Decentralized Encircling Coverage and Termination of a Moving Deformable Region by Mobile Robotic Sensor/Actuator Networks

An Algorithm of Decentralized Encircling Coverage and Termin...

引用

9th Asian Control Conference (ASCC)

作者： Savkin, Andrey V. Xi, Zhiyu Nguyen, Hung T. Univ New South Wales Sch Elect Engn & Telecommun Sydney NSW 2052 Australia Univ Technol Sydney Fac Engn Sydney NSW 2007 Australia

ISBN: (纸本)9781467357692;9781467357678

The paper introduces the problems of encircling coverage and termination of a moving a deformable planar region by a mobile sensor/actuator network. We propose a decentralized randomized algorithm for self-deployment of a network of mobile robotic sensors/actuators for these problems. In the encircling coverage problem, the aim is to deploy sensors around a bounded connected region so that any point of a certain neighbourhood of the region is sensed by at least one mobile robotic sensor. In the termination problem, the aim is to terminate a moving region that may represent an oil spill or a hazardous chemical field. In this case, the moving robots are equipped with not only sensors but with actuators releasing neutralizing chemical so that the shape of the polluted region is controlled. The proposed algorithm is based only on information about the closest neighbours of each sensor. The moving region is of an arbitrary shape and not known to the sensors a priori. We give mathematically rigorous proofs of asymptotic optimality and convergence with probability 1 of the proposed randomized algorithm.

关键词： Robotic networks encircling coverage mobile sensor networks sensor/actuator networks sensor deployment decentralized control distributed algorithms blanket coverage randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

An O(√n) Space Bound for Obstruction-Free Leader Election

An <i>O</i>(√<i>n</i>) Space Bound for Obstruction-Free Lea...

引用

27th International Symposium on Distributed Computing (DISC)

作者： Giakkoupis, George Helmi, Maryam Higham, Lisa Woelfel, Philipp INRIA Rennes Bretagne Atlantic Rennes France Univ Calgary Dept Comp Sci Calgary AB Canada

ISBN: (纸本)9783642415272;9783642415265

We present a deterministic obstruction-free implementation of leader election from O(root n) atomic O(log n)-bit registers in the standard asynchronous shared memory system with n processes. We provide also a technique to transform any deterministic obstruction-free algorithm, in which any process can finish if it runs for b steps without interference, into a randomized wait-free algorithm for the oblivious adversary, in which the expected step complexity is polynomial in n and b. This transformation allows us to combine our obstruction-free algorithm with the leader election algorithm by Giakkoupis and Woelfel [21], to obtain a fast randomized leader election (and thus test-and-set) implementation from O(v n) O(log n)-bit registers, that has expected step complexity O(log* n) against the oblivious adversary. Our algorithm provides the first sub-linear space upper bound for obstruction-free leader election. A lower bound of Omega(log n) has been known since 1989 [29]. Our research is also motivated by the long-standing open problem whether there is an obstruction-free consensus algorithm which uses fewer than n registers.

关键词： leader election test-and-set shared memory model randomized algorithms obstruction-free algorithms

来源：评论

学校读者我要写书评

暂无评论

Almost sure convergence of a randomized algorithm for relative localization in sensor networks

Almost sure convergence of a randomized algorithm for relati...

引用

IEEE Annual Conference on Decision and Control

作者： Chiara Ravazzi Paolo Frasca Roberto Tempo Hideaki Ishii Department of Electronics and Telecommunications (DET) Politecnico di Torino Italy Department of Applied Mathematics University of Twente Enschede The Netherlands CNR-IEIIT Politecnico di Torino Italy Department of Computational Intelligence and Systems Science Tokyo Institute of Technology Japan

ISBN: (纸本)9781467357159

This paper regards the relative localization problem in sensor networks. We study a randomized algorithm, which is based on input-driven consensus dynamics and involves pairwise "gossip" communications and updates. Due to the randomness of the updates, the state of this algorithm ergodically oscillates around a limit value. Exploiting the ergodicity of the dynamics, we show that the time-average of the state almost surely converges to the least-squares solution of the localization problem. Remarkably, the computation of the time-average does not require the sensors to share any common clock. Hence, the proposed algorithm is fully distributed and asynchronous.

关键词： randomized algorithms average time Sensor networks limits (mathematics) computational time Pairwise Random Number Generators Asynchronous Communication Research

来源：评论

学校读者我要写书评

暂无评论

Towards a Complexity Theory for Local Distributed Computing

引用

JOURNAL OF THE ACM 2013年第5期60卷 35-35页

作者： Fraigniaud, Pierre Korman, Amos Peleg, David Univ Paris Diderot F-75205 Paris 13 France Weizmann Inst Sci Fac Math & Comp Sci IL-76100 Rehovot Israel CNRS F-75700 Paris France

A central theme in distributed network algorithms concerns understanding and coping with the issue of locality. Yet despite considerable progress, research efforts in this direction have not yet resulted in a solid basis in the form of a fundamental computational complexity theory for locality. Inspired by sequential complexity theory, we focus on a complexity theory for distributed decision problems. In the context of locality, solving a decision problem requires the processors to independently inspect their local neighborhoods and then collectively decide whether a given global input instance belongs to some specified language. We consider the standard LOCAL model of computation and define LD(t) (for local decision) as the class of decision problems that can be solved in t communication rounds. We first study the intriguing question of whether randomization helps in local distributed computing, and to what extent. Specifically, we define the corresponding randomized class BPLD(t, p, q), containing all languages for which there exists a randomized algorithm that runs in t rounds, accepts correct instances with probability at least p, and rejects incorrect ones with probability at least q. We show that p(2) + q = 1 is a threshold for the containment of LD(t) in BPLD(t, p, q). More precisely, we show that there exists a language that does not belong to LD(t) for any t = o(n) but does belong to BPLD(0, p, q) for any p, q is an element of (0, 1] such that p(2) + q <= 1. On the other hand, we show that, restricted to hereditary languages, BPLD(t, p, q) = LD(O(t)), for any function t, and any p, q is an element of (0, 1] such that p(2) + q > 1. In addition, we investigate the impact of nondeterminism on local decision, and establish several structural results inspired by classical computational complexity theory. Specifically, we show that nondeterminism does help, but that this help is limited, as there exist languages that cannot be decided locally nondeterministically

关键词： algorithms Theory Reliability Local distributed algorithms local decision nondeterminism randomized algorithms oracle

来源：评论

学校读者我要写书评

暂无评论

In-network estimation of frequency moments

引用

INTERNATIONAL JOURNAL OF ADVANCES IN ENGINEERING SCIENCES AND APPLIED MATHEMATICS 2013年第1期5卷 76-84页

作者： Vyavahare, Pooja Limaye, Nutan Manjunath, D. Indian Inst Technol Dept Elect Engn Powai India Indian Inst Technol Dept Comp Sci & Engn Powai India

We consider the problem of estimating functions of distributed data using a distributed algorithm over a network. The extant literature on computing functions in distributed networks such as wired and wireless sensor networks and peer-to-peer networks deals with computing linear functions of the distributed data when the alphabet size of the data values is small, O(1). We describe a distributed randomized algorithm to estimate a class of nonlinear functions of the distributed data which is over a large alphabet. We consider three types of networks: point-to-point networks with gossip based communication, random planar networks in the connectivity regime and random planar networks in the percolating regime both of which use the slotted Aloha communication protocol. For each network type, we estimate the scaled kth frequency moments, for k >= 2. Specifically, for every k >= 2, we give a distributed randomized algorithm that computes, with probability (1 - delta), an epsilon-approximation of the scaled kth frequency moment, F-k/N-k, using time O(M-1-1/k-1T) and O(M-1-1/k-1 log N log (delta(-1))/epsilon(2) bits of transmission per communication step. Here, N is the number of nodes in the network, T is the information spreading time and M = o(N) is the alphabet size.

关键词： In-network computing Frequency moments randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：