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

local Construction of Near-Optimal Power Spanners for Wireless Ad Hoc Networks

IEEE TRANSACTIONS ON MOBILE COMPUTING 2009年第4期8卷 460-474页

作者： Kanj, Iyad A. Perkovic, Ljubomir Xia, Ge DePaul Univ CTI Chicago IL 60604 USA Lafayette Coll Dept Comp Sci Easton PA 18042 USA

We present a local distributed algorithm that, given a wireless ad hoc network modeled as a unit disk graph U in the plane, constructs a planar power spanner of U whose degree is bounded by k and whose stretch factor is bounded by 1 + (2 sin pi/k)(p), where k >= 10 is an integer parameter and p is an element of [2, 5] is the power exponent constant. For the same degree bound k, the stretch factor of our algorithm significantly improves the previous best bounds by Song et al. We show that this bound is near-optimal by proving that the slightly smaller stretch factor of 1 + (2 sin pi/k+1)(p) is unattainable for the same degree bound k. In contrast to previous algorithms for the problem, the presented algorithm is local. As a consequence, the algorithm is highly scalable and robust. Finally, while the algorithm is efficient and easy to implement in practice, it relies on deep insights on the geometry of unit disk graphs and novel techniques that are of independent interest.

关键词： Spanners unit disk graphs Gabriel graphs Yao graphs local distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

local Construction of Spanners in the 3D Space

引用

IEEE TRANSACTIONS ON MOBILE COMPUTING 2012年第7期11卷 1140-1150页

作者： Jenkins, Jonathan P. Kanj, Iyad A. Xia, Ge Zhang, Fenghui N Carolina State Univ Dept Comp Sci Raleigh NC 27695 USA DePaul Univ Sch Comp Chicago IL 60604 USA Lafayette Coll Dept Comp Sci Easton PA 18042 USA Google Kirkland Kirkland WA 98033 USA

In this paper, we present local distributed algorithms for constructing spanners in wireless sensor networks modeled as unit ball graphs (shortly UBGs) and quasi-unit ball graphs (shortly quasi-UBGs), in the 3D euclidean space. Our first contribution is a local distributed algorithm that, given a UBGU and a parameter alpha < pi/3, constructs a sparse spanner of U with stretch factor 1/(1-2sin(alpha/2)), improving the previous upper bound of 1/(1-alpha) by Althofer et al. which is applicable only when alpha<1/(1+2 root 2 < pi/3). The second contribution of this paper is in presenting the first local distributed algorithm for the construction of bounded-degree lightweight spanners of UBGs and quasi-UBGs. The simulation results we obtained show that, empirically, the weight and the stretch factor of the spanners, and the locality of the algorithms, are much better than the theoretical upper bounds proved in this paper.

关键词： 3D spanners sparse spanners lightweight spanners local distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

Linear-in-Δ Lower Bounds in the local Model 14

Linear-in-Δ Lower Bounds in the LOCAL Model

引用

ACM Symposium on Principles of distributed Computing (PODC)

作者： Goos, Mika Hirvonen, Juho Suomela, Jukka Univ Toronto Dept Comp Sci Toronto ON Canada Aalto Univ Helsinki Inst Informat Technol HIIT Dept Informat & Comp Sci Espoo Finland

ISBN: (纸本)9781450329446

By prior work, there is a distributed graph algorithm that finds a maximal fractional matching (maximal edge packing) in O(Delta) rounds, independently of n;here Delta is the maximum degree of the graph and n is the number of nodes in the graph. We show that this is optimal: there is no distributed algorithm that finds a maximal fractional matching in o(Delta) rounds, independently of n. Our work gives the first linear-in-Delta lower bound for a natural graph problem in the standard local model of distributed computing|prior lower bounds for a wide range of graph problems have been at best logarithmic in Delta.

关键词： local distributed algorithms lower bounds maximal edge packing maximal fractional matching

来源：评论

学校读者我要写书评

暂无评论

local distributed Decision

Local Distributed Decision

引用

52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS)

作者： Fraigniaud, Pierre Korman, Amos Peleg, David CNRS Paris France

ISBN: (纸本)9780769545714

A central theme in distributed network algorithms concerns understanding and coping with the issue of locality. 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 non-determinism on local decision, and establish some structural results inspired by classical computational complexity theory. Specifically, we show that non-determinism does help, but that this help is limited, as there exist languages that cannot be decided non-deterministically. Perhaps su

关键词： local distributed algorithms local decision nondeterminism randomized algorithms oracles

来源：评论

学校读者我要写书评

暂无评论

ON SPANNERS AND LIGHTWEIGHT SPANNERS OF GEOMETRIC GRAPHS

引用

SIAM JOURNAL ON COMPUTING 2010年第6期39卷 2132-2161页

作者： Kanj, Iyad A. Perkovic, Ljubomir Xia, Ge Depaul Univ Chicago IL 60604 USA Lafayette Coll Acopian Engn Ctr Dept Comp Sci Easton PA 18042 USA

We consider the problem of computing spanners of Euclidean and unit disk graphs embedded in the two-dimensional Euclidean plane. We are particularly interested in spanners that possess useful properties such as planarity, bounded degree, and/or light weight. Such spanners have been extensively studied in the area of computational geometry and have been used as the building block for constructing efficient and reliable wireless network communication topologies. We study the above problem under two computational models: the centralized and the distributed model. In the distributed model we focus on algorithms that are local. Such algorithms are suitable for the relevant applications (e.g., wireless computing). Under the centralized model, we present an O(n lg n) time algorithm that computes a bounded-degree plane spanner of a complete Euclidean graph, where n is the number of points in the graph. Both upper bounds on the degree and the stretch factor significantly improve the previous bounds. We extend this algorithm to compute a bounded-degree plane lightweight spanner of a complete Euclidean graph. Under the distributed model, we give the first local algorithm for computing a spanner of a unit disk graph that is of bounded degree and plane. The upper bounds on the degree, stretch factor, and the locality of the algorithm dramatically improve the previous results, as shown in the paper. This algorithm can also be extended to compute a bounded-degree plane lightweight spanner of a unit disk graph. Our algorithms rely on structural and geometric results that we develop in this paper.

关键词： spanners Delaunay triangulations lightweight bounded degree unit disk graphs local distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Linear-in-Δ lower bounds in the local model

引用

distributed COMPUTING 2017年第5期30卷 325-338页

作者： Goos, Mika Hirvonen, Juho Suomela, Jukka Univ Toronto Dept Comp Sci Toronto ON Canada Aalto Univ HIIT Dept Comp Sci Espoo Finland

By prior work, there is a distributed graph algorithm that finds a maximal fractional matching (maximal edge packing) in O(Delta) rounds, independently of n;here Delta is the maximum degree of the graph and n is the number of nodes in the graph. We show that this is optimal: there is no distributed algorithm that finds a maximal fractional matching in o(Delta) rounds, independently of n. Our work gives the first linear-in-Delta lower bound for a natural graph problem in the standard model of distributed computing-prior lower bounds for a wide range of graph problems have been at best logarithmic in Delta.

关键词： local distributed algorithms Lower bounds Maximal edge packing Maximal fractional matching

来源：评论

学校读者我要写书评

暂无评论

Randomized distributed Decision

Randomized Distributed Decision

引用

26th International Symposium on distributed Computing (DISC)

作者： Fraigniaud, Pierre Korman, Amos Parter, Merav Peleg, David CNRS F-75700 Paris France Weizmann Inst Sci Rehovot Israel

ISBN: (纸本)9783642336515

The paper tackles the power of randomization in the context of locality by analyzing the ability to "boost" the success probability of deciding a distributed language. The main outcome of this analysis is that the distributed computing setting contrasts significantly with the sequential one as far as randomization is concerned. Indeed, we prove that in some cases, the ability to increase the success probability for deciding distributed languages is rather limited. We focus on the notion of a (p q)-decider for a language r, which is a distributed randomized algorithm that accepts instances in L with probability at least p and rejects instances outside of L with probability at least q. It is known that every hereditary language that can be decided in t rounds by a (p, q)-decider, where p(2) + q > 1, can be decided deterministically in O(t) rounds. One of our results gives evidence supporting the conjecture that the above statement holds for all distributed languages and not only for hereditary ones, by proving the conjecture for the restricted case of path topologies. For the range below the aforementioned threshold, namely, p(2)+ q < 1, we study the class Bk(t) (for k E N* U {cc}) of all languages decidable in at most t rounds by a (p,q)-decider, where pl+i + q > 1. Since every language is decidable (in zero rounds) by a (p q)-decider satisfying p + q = 1, the hierarchy Bk provides a spectrum of complexity classes between determinism (k = 1, under the above conjecture) and complete randomization (k = co). We prove that all these classes are separated, in a strong sense: for every integer k > 1, there exists a language L satisfying L E Bk+i (0) but L Bk(t) for any t = o(n). In addition, we show that B(t) does not contain all languages, for any t = o(n). In other words, we obtain the hierarchy B1 (t) c B2 (t) C C B,o(t) C All. Finally, we show that if the inputs can be restricted in certain ways, then the ability to boost the success probability becomes almost null, an

关键词： local distributed algorithms local decision randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：