An efficient distributed algorithm for maximum matching in general graphs

We present a distributed algorithm for maximum cardinality matching in general graphs. On a general graph withn vertices, our algorithm requiresO(n ^5/2) messages in the worst case. On trees, our algorithm computes a maximum matching usingO(n) messages after the election of a leader.Work on this paper has been supported by the Office of Naval Research under Contract N00014-85-K-0570.     

Distributed approximation of cellular coverage

We consider the following model of cellular networks. Each base station has a given finite capacity, and each client has some demand and profit. A client can be covered by a specific subset of the base stations, and its profit is obtained only if its demand is provided in full. The goal is to assign clients to base stations, so that the overall profit is maximized subject to base station capacity constraints.     

Linear election in pancake graphs

Pancake graphs have been proposed as an attractive alternative to hypercube networks. They have a smaller diameter and a lower degree. They also have a hierarchical structure which can be exploited in designing algorithms.In this paper, we propose a leader election algorithm for oriented pancake graphs. The algorithm has a message complexity that is linear in the order of the graph.     

Distributed election in complete networks

An improved version of Afek and Gafni's synchronous algorithm for distributed election in complete networks is given and anO(n) expected message complexity is shown. M.Y. Chan received her Ph.D. in 1988 from the University of Hong Kong, and her M.S. and B.A. degrees in computer science from the University of California, San Diego in 1980 and 1981, respectively. She is currently an Assistant Professor at the University of Texas at Dallas. Francis Y.L. Chin (S71-M76-SM85) received the B.Sc. degree in engineering science from the University of Toronto, Toronto, Canada, in 1972, and the M.S., M.A., and Ph.D. degrees in electrical engineering and computer science from Princeton University, New Jersey, in 1974, 1975, and 1976, respectively. Since 1975, he has taught at the University of Maryland, Baltimore Country, University of California, San Diego, University of Alberta, and Chinese University of Hong Kong. He is currently Head of the Department of Computer Science, University of Hong Kong. He has served as a program co-chairman of the 1988 International Conference on Computer Processing of Chinese and Oriental Languages (Toronto) and the International Computer Science Conference '88 (Hong Kong). His current research interests include algorithm design and analysis, parallel and distributed computing.     

A note on maximum independent sets in rectangle intersection graphs

Finding the maximum independent set in the intersection graph of n axis-parallel rectangles is NP-hard. We re-examine two known approximation results for this problem. For the case of rectangles of unit height, Agarwal, van Kreveld and Suri [Comput. Geom. Theory Appl. 11 (1998) 209-218] gave a (1+1/k)-factor algorithm with an O(nlogn+n^2k−1) time bound for any integer constant k?1; we describe a similar algorithm running in only O(nlogn+nΔ^k−1) time, where Δ?n denotes the maximum number of rectangles a point can be in. For the general case, Berman, DasGupta, Muthukrishnan and Ramaswami [J. Algorithms 41 (2001) 443-470] gave a ⌈log_kn⌉-factor algorithm with an O(n^k+1) time bound for any integer constant k?2; we describe similar algorithms running in O(nlogn+nΔ^k−2) and n^O(k/logk) time.     

A note on maximum independent set and related problems on box graphs

A box graph is the intersection graph of orthogonal rectangles in the plane. We show that maximum independent set and minimum vertex cover on box graphs can be solved in subexponential time, more precisely, in time , by applying Miller's simple cycle planar separator theorem [J. Comput. System Sci. 32 (1986) 265-279] (in spite of the fact that the input box graph might be strongly non-planar).     

贝叶斯推断在MCDB分布式平台上的实现

提出了应用贝叶斯统计方法在分布式数据库MCDB上处理超大规模数据的实现方法,并以贝叶斯线性回归、话题模型的LDA和狄利克雷过程的聚类算法为例进行了论证.用户可以通过SQL语言定义变量之间的关系进行模拟.探索了一种使用简洁的SQL设计大规模统计学习系统的方法,其利用MCDB能够自动解决并行化和资源优化问题,以获得高性能的并行处理能力.     

Distributed wireless power transfer in sensor networks with multiple Mobile Chargers

We investigate the problem of efficient wireless power transfer in wireless sensor networks. In our approach, special mobile entities (called the Mobile Chargers) traverse the network and wirelessly replenish the energy of sensor nodes. In contrast to most current approaches, we envision methods that are distributed and use limited network information. We propose four new protocols for efficient charging, addressing key issues which we identify, most notably (i) what are good coordination procedures for the Mobile Chargers and (ii) what are good trajectories for the Mobile Chargers. Two of our protocols (DC, DCLK) perform distributed, limited network knowledge coordination and charging, while two others (CC, CCGK) perform centralized, global network knowledge coordination and charging. As detailed simulations demonstrate, one of our distributed protocols outperforms a known state of the art method, while its performance gets quite close to the performance of the powerful centralized global knowledge method.     

Distributed match-making

In many distributed computing environments, processes are concurrently executed by nodes in a store- and-forward communication network. Distributed control issues as diverse as name server, mutual exclusion, and replicated data management involve making matches between such processes. We propose a formal problem called distributed match-making as the generic paradigm. Algorithms for distributed match-making are developed and the complexity is investigated in terms of messages and in terms of storage needed. Lower bounds on the complexity of distributed match-making are established. Optimal algorithms, or nearly optimal algorithms, are given for particular network topologies.The work of the second author was supported in part by the Office of Naval Research under Contract N00014-85-K-0168, by the Office of Army Research under Contract DAAG29-84-K-0058, by the National Science Foundation under Grant DCR-83-02391, and by the Defence Advanced Research Projects Agency (DARPA) under Contract N00014-83-K-0125. Current address of both authors: CWI, Kruislaan 413, 1098 SJ Amsterdam, The Netherlands.     

基于分布式时间反转法的水声组网通信

研究水下信息获取系统,在非均匀介质中实现声束的自适应聚焦,应用于水声组网通信时,可以很好地利用海洋信道中的多径特性,提高节点间的通信速率,为消除码间干扰和改善误码率,提出了一种基于分布式时间反转法的水卢组网通信方案,充分利用网络中多个独立节点的自身资源,组成分布式时反组网通信系统,组网节点不需要再设置传统时间反转法所必需的垂直线列阵,易于工程实现.利用海洋环境实测数据得到的仿真结果表明提出的分布式时反组网通信与传统时间反转法组网通信性能相当,联合判决反馈均衡器可进一步提高系统件能.     

基于半环仲裁集的环网分布式互斥算法

分布式互斥是环网分布式系统的重要问题.根据此类系统的特点,提出了新型的分布式互斥算法.该算法以请求者自身为中心,基于半环生成分布式互斥仲裁集;采用Lamport逻辑时戳保证消息的时序性;算法采用"探测"消息进行系统的容错处理.分析与仿真证明,该算法具有较低的消息复杂度、较短的响应延迟以及较好的容错性能.     

基于分布式范围树的结构化P2P多维范围查询

基于分布式哈希表（DHT）的结构化P2P网络具有扩展性好、健壮和自组织等优点,但只支持精确匹配的查询.本文提出一种基于分布式范围树的结构化P2P范围查询方法（DRT-RQ）,该方法将多维索引的分布式范围树分发到已有的结构化DHT覆盖网络中,利用DHT系统提供的数据查找接口,有效实现数据对象的范围查询.实验结果表明,基于分布式范围树的范围查询（DRT-RQ）比基于前缀哈希树的范围查询（PHT-RQ）需要更短的查询延时.     

一种基于环形结构的新型分布式入侵检测模型

分析了目前的分布式入侵检测系统的特点和协作方式,提出了基于逻辑环形分布式协作控制技术的分布式入侵检测模型,解决了目前分布式入侵检测系统中各系统闭协作效率低、配置复杂、检测响应慢等缺陷。详细论述了环形结构的分布式入侵检测系统的体系结构和系统框架,提出了一套基于环形结构的分布式入侵检测协作算法。     

Distributed measurement and control system based on microcontrollers with automatic program generation

The paper describes an open architecture microcontroller based distributed measurement and control system with automatic generation of application program. Interpretation of functions and generation of program for control of the newly added distributed unit or distributed unit of a new type connected to the system performs automatically, without user assistance. The elements of the system are interconnected by means of a serial common bus according to the reduced OSI protocol. The proposed concept was tested in a system developed by using 8-bit Atmel microcontrollers of 89S and 89C series. Apart from the central unit, intelligent distributed units were developed for the control of a stepper motor, programmable linear movement, control of halogen lamps, acquisition and generation of analogue, digital and timing pulses and a real time clock (RTC).     

Distributed algorithms for reaching consensus on general functions

This paper presents analysis and design results for distributed consensus algorithms in multi-agent networks. We consider continuous consensus functions of the initial state of the network agents. Under mild smoothness assumptions, we obtain necessary and sufficient conditions characterizing any algorithm that asymptotically achieves consensus. This characterization is the building block to obtain various design results for networks with weighted, directed interconnection topologies. We first identify a class of smooth functions for which one can synthesize in a systematic way distributed algorithms that achieve consensus. We apply this result to the family of weighted power mean functions, and characterize the exponential convergence properties of the resulting algorithms. We establish the validity of these results for scenarios with switching interconnection topologies. Finally, we conclude with two discontinuous distributed algorithms that achieve, respectively, max and min consensus in finite time.     

1.5-Approximation algorithm for weighted maximum routing and wavelength assignment on rings

We give a 1.5-approximation algorithm for the weighted maximum routing and wavelength assignment problem on undirected ring networks. This improves the previous 1.58-approximation result.     

Distributed algorithms for finding and maintaining a k-tree core in a dynamic network

A k-core C_k of a tree T is subtree with exactly k leaves for k?n_l, where n_l the number of leaves in T, and minimizes the sum of the distances of all nodes from C_k. In this paper first we propose a distributed algorithm for constructing a rooted spanning tree of a dynamic graph such that root of the tree is located near the center of the graph. Then we provide a distributed algorithm for finding k-core of that spanning tree. The spanning tree is constructed in two stages. In the first stage, a forest of trees is generated. In the next stage these trees are connected to form a single rooted tree. An interesting aspect of the first stage of proposed spanning algorithm is that it implicitly constructs the (convex) hull of those nodes which are not already included in the spanning forest. The process is repeated till all non root nodes of the graph have chosen a unique parent. We implemented the algorithms for finding spanning tree and its k-core. A core can be quite useful for routing messages in a dynamic network consisting of a set of mobile devices.     

无线传感器网络中一种基于多跳导标的分布式节点定位算法

针对无线传感器网络内在特点及经典Beacon-based定位方法的局限性,提出了一种新的基于多跳导标节点的分布式节点定位策略。其主要原理在于应用距离矢量路由法获得邻近导标节点的同时,在选择参与定位的导标节点集时考虑了导标节点共线度及未知节点与导标节点的位置关系,并在此基础上提出了不依赖于复杂优化计算的基于权值的位置估算策略。仿真研究表明,提出的算法具有很好的自适应性、分布性、可扩展性和鲁棒性,特别是算法在计算复杂度及定位结果鲁棒性等方面表现出了很好的性能,适合应用于大规模无线传感器网络。