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

Tight analyses of two local load balancing algorithms

SIAM JOURNAL ON COMPUTING 1999年第1期29卷 29-64页

作者： Ghosh, B Leighton, FT Maggs, BM Muthukrishnan, S Plaxton, CG Rajaraman, R Richa, AW Tarjan, RE Zuckerman, D Informix Software Menlo Park CA 94025 USA Yale Univ Dept Comp Sci New Haven CT 06520 USA MIT Comp Sci Lab Cambridge MA 02139 USA Carnegie Mellon Univ Sch Comp Sci Pittsburgh PA 15213 USA AT&T Bell Labs Murray Hill NJ 07974 USA Rutgers State Univ DIMACS Piscataway NJ 08855 USA Univ Texas Dept Comp Sci Austin TX 78712 USA Princeton Univ Dept Comp Sci Princeton NJ 08544 USA

This paper presents an analysis of the following load balancing algorithm. At each step, each node in a network examines the number of tokens at each of its neighbors and sends a token to each neighbor with at least 2d + 1 fewer tokens, where d is the maximum degree of any node in the network. We show that within O(Delta/alpha) steps, the algorithm reduces the maximum difference in tokens between any two nodes to at most O((d(2) log n)/alpha), where Delta is the global imbalance in tokens (i.e., the maximum difference between the number of tokens at any node initially and the average number of tokens), n is the number of nodes in the network, and alpha is the edge expansion of the network. The time bound is tight in the sense that for any graph with edge expansion alpha, and for any value Delta, there exists an initial distribution of tokens with imbalance Delta for which the time to reduce the imbalance to even Delta/2 is at least Omega(Delta/alpha). The bound on the final imbalance is tight in the sense that there exists a class of networks that can be locally balanced everywhere (i.e., the maximum difference in tokens between any two neighbors is at most 2d), while the global imbalance remains Omega((d(2) log n)/alpha). Furthermore, we show that upon reaching a state with a global imbalance of O((d(2) log n)/alpha), the time for this algorithm to locally balance the network can be as large as Omega(n(1/2)). We extend our analysis to a variant of this algorithm for dynamic and asynchronous networks. We also present tight bounds for a randomized algorithm in which each node sends at most one token in each step.

关键词： load balancing distributed network algorithms

来源：评论

学校读者我要写书评

暂无评论

Fast and compact self-stabilizing verification, computation, and fault detection of an MST

引用

distributed COMPUTING 2015年第4期28卷 253-295页

作者： Korman, Amos Kutten, Shay Masuzawa, Toshimitsu CNRS F-75013 Paris France Univ Paris Diderot F-75013 Paris France Technion Israel Inst Technol Fac IE&M Informat Syst Grp IL-32000 Haifa Israel Osaka Univ Grad Sch Informat Sci & Technol Suita Osaka 5650871 Japan

This paper demonstrates the usefulness of distributed local verification of proofs, as a tool for the design of self-stabilizing algorithms. In particular, it introduces a somewhat generalized notion of distributed local proofs, and utilizes it for improving the time complexity significantly, while maintaining space optimality. As a result, we show that optimizing the memory size carries at most a small cost in terms of time, in the context of minimum spanning tree (MST). That is, we present algorithms that are both time and space efficient for both constructing an MST and for verifying it. This involves several parts that may be considered contributions in themselves. First, we generalize the notion of local proofs, trading off the time complexity for memory efficiency. This adds a dimension to the study of distributed local proofs, which has been gaining attention recently. Specifically, we design a (self-stabilizing) proof labeling scheme which is memory optimal (i.e., bits per node), and whose time complexity is in synchronous networks, or time in asynchronous ones, where is the maximum degree of nodes. This answers an open problem posed by Awerbuch et al. (1991). We also show that time is necessary, even in synchronous networks. Another property is that if faults occurred, then, within the required detection time above, they are detected by some node in the locality of each of the faults. Second, we show how to enhance a known transformer that makes input/output algorithms self-stabilizing. It now takes as input an efficient construction algorithm and an efficient self-stabilizing proof labeling scheme, and produces an efficient self-stabilizing algorithm. When used for MST, the transformer produces a memory optimal self-stabilizing algorithm, whose time complexity, namely, , is significantly better even than that of previous algorithms (the time complexity of previous MST algorithms that used memory bits per node was , and the time for optimal space algorithms

关键词： distributed network algorithms Locality Proof labels Minimum spanning tree distributed property verification Self-stabilization Fast fault detection Local fault detection

来源：评论

学校读者我要写书评

暂无评论

Modular neural networks for multi-service connection admission control

引用

COMPUTER networkS 2001年第2-3期36卷 181-202页

作者： Soh, WS Tham, CK Carnegie Mellon Univ Dept Elect & Comp Engn Pittsburgh PA 15213 USA Natl Univ Singapore Dept Elect & Comp Engn Singapore 119260 Singapore

Although neural networks (NNs) have been applied for traffic and congestion control in ATM networks, many implementations only consider a single service class with identical traffic characteristics and requirements. In addition, the most commonly used NN is the multi-layer perceptron (MLP) networks which are known to converge slowly. We present a multi-service connection admission control (CAC) scheme that harness the fast learning capability of modular neural networks for cell-loss-ratio (CLR) prediction at each switch. The proposed scheme does not require precise models of network processes and detailed knowledge of higher-order moments of the traffic. Simulations were carried out to compare the performance of the proposed scheme with an equivalent bandwidth (EBW) method. (C) 2001 Elsevier Science B.V. All rights reserved.

关键词： congestion and admission control B-ISDN and ATM traffic management distributed network algorithms HME

来源：评论

学校读者我要写书评

暂无评论

Broadcasting in unstructured peer-to-peer overlay networks

引用

THEORETICAL COMPUTER SCIENCE 2006年第1期355卷 25-36页

作者： Annexstein, FS Berman, KA Jovanovic, MA Univ Cincinnati Dept ECECS Cincinnati OH 45221 USA

Peer-to-peer overlay networks present new opportunities and challenges for achieving enhanced network functionality at the application level. In this paper we study the impact of point-to-point network latency on flooding broadcast operations in peer-to-peer overlay networks. We show that two standard protocol mechanisms, used to control the amount of network resources used during flooding, can in combination, significantly reduce the reach of broadcast messages. We prove that these standard mechanisms, known as "time-to-live bounds" and "unique message identification", can result in broadcast operations that only reach a vanishing fraction of the nodes. In addition, we provide empirical evidence that the trend suggested by our formal results are found in data obtained from the Gnutella network and through network simulations. (c) 2006 Elsevier B.V. All rights reserved.

关键词： peer-to-peer overlay networks network broadcasting and flooding distributed network algorithms network reliability and reachability network simulation

来源：评论

学校读者我要写书评

暂无评论

A Study Of Broadcasting Over Structured Overlay 7

A Study Of Broadcasting Over Structured Overlay

引用

7th International Conference on Communication Systems and networks

作者： Khan, Saiful Gani, Abdullah Raviraja, S. Shashikantha Univ Malaya Fac Comp Sci & Informat Technol Kuala Lumpur Malaysia Natl Inst Engn Mysore 560008 Karnataka India

ISBN: (纸本)9781479984398

An efficient and scalable broadcast are two essential features of structured overlay networks which used in large scale distributed computing systems and in peer-to-peer networks. The existing broadcast based algorithms over the structured overlays experience certain issues due to a decentralised nature of such networks in which nodes join and leave the network dynamically. This causes poor routing efficiency and high maintenance bandwidth overhead. In this paper, we study routing efficiency and maintenance bandwidth overhead while broadcasting messages over the structured overlay networks in dynamic environment. We also propose an improved message broadcasting algorithm over the structured overlay networks. The simulation results show that although there is a trade off between routing efficiency and maintenance bandwidth, with optimisation we can improve one without severely effecting the other parameter.

关键词： Structured Overlay distributed network algorithms network simulation Peer-to-Peer P2P Broadcast

来源：评论

学校读者我要写书评

暂无评论

Run for Cover: Dominating Set via Mobile Agents 1

引用

19th International Symposium on Algorithmics of Wireless networks (ALGOWIN) as part of ALGO Conference

作者： Chand, Prabhat Kumar Molla, Anisur Rahaman Sivasubramaniam, Sumathi Indian Stat Inst Kolkata India

ISBN: (数字)9783031488825

ISBN: (纸本)9783031488818;9783031488825

Research involving computing with mobile agents is a fast-growing field, given the advancement of technology in automated systems, e.g., robots, drones, self-driving cars, etc. Therefore, it is pressing to focus on solving classical network problems using mobile agents. In this paper, we study one such problem-finding small dominating sets of a graph G using mobile agents. Dominating set is interesting in the field of mobile agents as it opens up a way for solving various robotic problems, e.g., guarding, covering, facility location, transport routing, etc. In this paper, we first present two algorithms for computing a minimal dominating set: (i) an O(m) time algorithm if the robots start from a single node (i.e., gathered initially), (ii) an O(l Delta log(lambda) + nl + m) time algorithm, if the robots start from multiple nodes (i.e., positioned arbitrarily), where m is the number of edges and. is the maximum degree of G, l is the number of clusters of the robots initially and lambda is the maximum ID-length of the robots. Then we present a ln(Delta) approximation algorithm for the minimum dominating set which takes O(n Delta log(lambda)) rounds.

关键词： Dominating Set Mobile Agents distributed network algorithms Approximation algorithms Time Complexity Memory Complexity Maximal Independent Set

来源：评论

学校读者我要写书评

暂无评论

Agent-Driven BFS Tree in Anonymous Graphs with Applications 1

引用

12th International Conference on networked Systems (NETYS)

作者： Chand, Prabhat Kumar Kumar, Manish Molla, Anisur Rahaman Indian Stat Inst Kolkata Baranagar India Indian Inst Technol Chennai India

ISBN: (数字)9783031673214

ISBN: (纸本)9783031673207;9783031673214

Breadth-First-Search (BFS) trees serve a pivotal role in designing efficient graph algorithms due to their efficacy in traversing and exploring graph structures with a systematic layer-by-layer approach. This paper introduces an agent-based novel approach for constructing a BFS tree on an arbitrary anonymous graph G with n nodes and m edges using k >= n autonomous mobile agents. In this paper, we provide algorithms for BFS tree construction for different starting configurations and demonstrate their applications. Our main result considers the dispersed starting configuration (i.e., each node is occupied by a single agent at the start) and takes O(D Delta) rounds to execute, where D is the diameter and Delta is the highest degree of G. The algorithm assumes the knowledge of a root node for the BFS tree. We further continue our investigation for BFS tree construction with two other classical configurations, namely, rooted configuration and arbitrary configuration (with and without the knowledge of root) of the agents with some other follow-up configurations for k > n. In addition, the paper demonstrates the application of the BFS tree construction methodology in tasks like - checking a graph for bipartiteness and gathering agents into a single node, a fundamental task in distributed robotics.

关键词： Breadth First Search Tree Mobile Agents distributed network algorithms Time Complexity Memory Complexity Bipartite Graph Gathering distributed Graph algorithms

来源：评论

学校读者我要写书评

暂无评论

distributed Computing: A Locality-Sensitive Approach

引用

丛书名： Discrete Mathematics and Applications

2000年

作者： David Peleg

ISBN: (数字)9780898719772

ISBN: (纸本)9780898714647

This volume presents the locality-sensitive approach to distributed network algorithms-the utilization of locality to simplify control structures and algorithms and reduce their costs. The author begins with an introductory exposition of distributed network algorithms focusing on topics that illustrate the role of locality in distributed algorithmic techniques. He then introduces locality-preserving network representations and describes sequential and distributed techniques for their construction. Finally, the applicability of the locality-sensitive approach is demonstrated through several applications.

distributed Computing: A Locality-Sensitive Approach is the only book that gives a thorough exposition of network spanners and other locality-preserving network representations such as sparse covers and partitions. The book is useful for computer scientists interested in distributed computing, electrical engineers interested in network architectures and protocols, and for discrete mathematicians and graph theorists.

关键词： electronic data processing distributed processing distributed network algorithms

来源：评论

学校读者我要写书评

暂无评论

Scenario-based stability anlysis of the distributed mobility-adaptive clustering (DMAC) algorithm 01

Scenario-based stability anlysis of the distributed mobility...

引用

Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing

作者： Christian Bettstetter Roland Krausser Technische Universität München (TUM) Institute of Communication Networks D-80290 Munich Germany

ISBN: (纸本)9781581134285

Adaptive distributed clustering algorithms and respective protocols are used in wireless ad hoc networks to dynamically organize all nodes into groups and hierarchites. In this paper, we investigate the distributed Mobility-Adaptive Clustering (DMAC) algorithm proposed in [6]. In particular, we evaluate how the cluster stability (i.e., the number of clusterhead elections, cluster changes per time step, and cluster lifetime) is influenced by the speed, the choice of the weight, and the failure rate of nodes. We performed simulations in a scenario with an enhanced random mobility model and in a realistic campus scenario that includes hot spots and streets

关键词： modeling clustering simulation and performance evaluation distributed network algorithms mobile wireless ad hoc networks self-organization and self-configuration

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：