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

An optimal distributed algorithm for finding a set of fundamental cycles in a graph

COMPUTER SYSTEMS SCIENCE AND ENGINEERING 2002年第1期17卷 41-47页

作者： Chaudhuri, P Univ W Indies Dept Comp Sci Math & Phys Bridgetown Barbados

A distributed algorithm for finding a set of fundamental cycles is presented in this paper. The output of the algorithm is available in a distributed manner, i.e. when the algorithm terminates each node knows the list of all the fundamental cycles passing through itself. The algorithm requires O(n) messages and O(n) units of time, where n is the number of nodes of the graph. It is shown that the algorithm is optimal in communication complexity to within a constant factor.

关键词： distributed algorithm undirected graph fundamental cycles message complexity

来源：评论

学校读者我要写书评

暂无评论

Brief announcement: improved asynchronous group mutual exclusion in token-passing networks 05

Brief announcement: improved asynchronous group mutual exclu...

引用

Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing

作者： David Lin Teng-Sheng Moh Melody Moh San Jose State University San Jose CA

ISBN: (纸本)9781581139945

Group mutual exclusion (GME) was first introduced by Joung in 1998 as a generalization of the n-process mutual exclusion problem, and subsequently modeled as the Congenial Talking Philosophers problem. GME allows processes requesting for the same resource to concurrently access the shared resource. However, a process requesting a resource that is different from the one currently being used will not be able to access the requested resource at the same time. At any time, only one resource may be in *** have been two solutions to the GME problem for a ring network. The first solution proposed by Wu and Joung [2] had an unbounded message size problem, while the second solution proposed by Cantarell et. al. [1] attempted to provide an upper-bound for the message size. However, in doing so, the second solution generated an unbounded number of messages. Hence, in this work we present a GME algorithm for a token-passing network that solves both of the problems found in the two previous solutions by providing an upper bound both to the number of messages and to message size.

关键词： message-passing distributed algorithm group mutual exclusion mutual exclusion token-passing

来源：评论

学校读者我要写书评

暂无评论

distributed construction of connected dominating set in wireless ad hoc networks

引用

MOBILE NETWORKS & APPLICATIONS 2004年第2期9卷 141-149页

作者： Wan, PJ Alzoubi, KM Frieder, O IIT Dept Comp Sci Chicago IL 60616 USA St Xavier Univ Dept Comp Sci Chicago IL 60655 USA

Connected dominating set (CDS) has been proposed as virtual backbone or spine of wireless ad hoc networks. Three distributed approximation algorithms have been proposed in the literature for minimum CDS. In this paper, we first reinvestigate their performances. None of these algorithms have constant approximation factors. Thus these algorithms cannot guarantee to generate a CDS of small size. Their message complexities can be as high as O(n(2)), and their time complexities may also be as large as O(n(2)) and O(n(3)). We then present our own distributed algorithm that outperforms the existing algorithms. This algorithm has an approximation factor of at most 8, O(n) time complexity and O(n log n) message complexity. By establishing the Omega(n log n) lower bound on the message complexity of any distributed algorithm for nontrivial CDS, our algorithm is thus message-optimal.

关键词： wireless ad hoc networks distributed algorithm connected dominating set independent set leader election spanning tree

来源：评论

学校读者我要写书评

暂无评论

Multi-policy iteration with a distributed voting

引用

MATHEMATICAL METHODS OF OPERATIONS RESEARCH 2004年第2期60卷 299-310页

作者： Chang, HS Sogang Univ Dept Comp Sci & Engn Seoul South Korea

We present a novel simulation-based algorithm, as an extension of the well-known policy iteration algorithm, by combining multi-policy improvement with a distributed simulation-based voting policy evaluation, for approximately solving Markov Decision Processes (MDPs) with infinite horizon discounted reward criterion, and analyze its performance relative to the optimal value.

关键词： policy iteration distributed algorithm voting Markov decision processes

来源：评论

学校读者我要写书评

暂无评论

distributed dynamic resource allocation with power shaping for multicell SDMA packet access networks.

Distributed dynamic resource allocation with power shaping f...

引用

IEEE Wireless Communications and Networking Conference

作者： Veronesi, R Tralli, V Zander, J Zorzi, M Univ Ferrara Dipartimento Ingn I-44100 Ferrara Italy

ISBN: (纸本)0780383443

We consider distributed dynamic slot and power allocation for the downlink of a TD/SDMA broadband wireless packet network with multiple access ports and adaptive antennas. The still open issue for packet multicell SDMA is how to manage the intercell interference, which is very difficult to predict in an uncoordinated environment, due to packet access and downlink beamforming. For this reason, doing distributed allocation efficiently as well as improving the performance by means of power control results in a very hard task. We propose a greedy SDMA algorithm exploiting the power shaping technique, which is based on a static preallocation of the transmit power to each slot of the frame. This permits to obtain a partial predictability of intercell interference, allowing different levels of estimated intercell interference and available power for each slot. We show that our greedy SDMA algorithm with power shaping increases system capacity with respect to the same algorithm without power shaping and reduces the performance gap with respect to a greedy centralized strategy thus limiting the need of coordination among cells. Both centralized and distributed algorithms are compared, as reference, to the baseline case of random allocation, previously proposed for packet access.

关键词： space division multiple access cellular radio channel allocation resource allocation packet radio networks radio access networks radio links radiofrequency interference broadband networks adaptive antenna arrays array signal processing time division multiple access algorithm theory distributed algorithms power control distributed dynamic resource allocation power shaping multicell SDMA packet access network distributed dynamic slot power allocation downlink TD-SDMA broadband wireless packet network multiple access port multiple adaptive antenna intercell interference downlink beamforming packet frame greedy algorithm distributed algorithm

来源：评论

学校读者我要写书评

暂无评论

Cooperative multihop broadcast for wireless networks

引用

IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS 2004年第6期22卷 1080-1088页

作者： Maric, I Yates, RD Rutgers State Univ Dept Elect & Comp Engn Wireless Network Informat Lab Piscataway NJ 08854 USA

We address the minimum-energy broadcast problem under the assumption that nodes beyond the nominal range of a transmitter can collect the energy of unreliably received overheard signals. As a message is forwarded through the network, a node will have multiple opportunities to reliably receive the message by collecting energy during each retransmission. We refer to this cooperative strategy as accumulative broadcast. We,seek to employ accumulative broadcast in a large scale loosely synchronized, low-power network. Therefore,, we focus on distributed network layer approaches for accumulative broadcast in which loosely synchronized nodes use only local information. To further simplify the system architecture, we assume that nodes forward only reliably decoded messages. Under these assumptions, we formulate the minimum-energy accumulative broadcast problem. We present a solution employing two subproblems. First, we identify the ordering in which nodes should transmit. Second, we determine the optimum power levels for that ordering. While the second subproblem can be solved by means of linear programming, the ordering subproblem is found to be NP-complete. We devise a heuristic algorithm to find a good ordering. Simulation results show the performance of the algorithm to be close to optimum and a significant improvement over the well known BIP algorithm for constructing energy-efficient broadcast trees. We then formulate a distributed version of the accumulative broadcast algorithm that uses only local information at the nodes and has performance close to, its centralized counterpart.

关键词： distributed algorithm minimum-energy broadcast reliable forwarding wideband regime

来源：评论

学校读者我要写书评

暂无评论

Asynchronous backup and initialization of a database server for replicated database systems

引用

JOURNAL OF SUPERCOMPUTING 2004年第1期27卷 69-89页

作者： Bhalla, S Madnick, SE Univ Aizu Database Syst Lab Aizu Wakamatsu Fukushima 9658580 Japan MIT Alfred P Sloan Sch Management Cambridge MA 02139 USA

A possibility of a temporary disconnection of database service exists in many computing environments. It is a common need to permit a participating site to lag behind and re-initialize to full recovery. It is also necessary that active transactions view a globally consistent system state for ongoing operations. We present an algorithm for on-the-fly backup and site-initialization. The technique is non-blocking in the sense that failure and recovery procedures do not interfere with ordinary transactions. As a result the system can tolerate disconnection of services and reconnection of disconnected services, without incurring high overheads.

关键词： concurrency control distributed algorithm non-blocking protocols parallel algorithms synchronization and recovery

来源：评论

学校读者我要写书评

暂无评论

(h, k)-arbiters for h-out-of-k mutual exclusion problem

引用

THEORETICAL COMPUTER SCIENCE 2004年第1-3期310卷 379-392页

作者： Manabe, Y Tajima, N NTT Corp Commun Sci Lab Kyoto 6190237 Japan Univ Aizu Aizu Wakamatsu Fukushima 9658580 Japan

h-Out-of-k mutual exclusion is a generalization of the I-mutual exclusion problem, where there are k units of shared resources and each process requests h (1 less than or equal to h less than or equal to k) units at the same time. Though k-arbiter has been shown to be a quorum-based solution to this problem, quorums in k-arbiter are much larger than those in the 1-coterie for I-mutual exclusion. Thus, the algorithm based on k-arbiter needs many messages. This paper introduces the new notion that each request uses different quorums depending on the number of units of its request. Based on the notion, this paper defines two (h,k)-arbiters for h-out-of-k mutual exclusion: a uniform (h,k)-arbiter and a (k + 1)-cube (h,k)-arbiter. The quorums in each (h,k)-arbiter are not larger than the ones in the corresponding k-arbiter;consequently, it is more efficient to use (h,k)-arbiters than the k-arbiters. A uniform (h,k)-arbiter is a generalization of the majority coterie for 1-mutual exclusion. A (k + 1)-cube (h,k)-arbiter is a generalization of square grid coterie for 1-mutual exclusion. (C) 2003 Elsevier B.V. All rights reserved.

关键词： distributed algorithm mutual exclusion arbiter quorum

来源：评论

学校读者我要写书评

暂无评论

Extending the lifetime of multicast trees in WANETs

引用

JOURNAL OF INFORMATION SCIENCE AND ENGINEERING 2004年第3期20卷 425-447页

作者： Wang, B Gupta, SKS Arizona State Univ Dept Comp Sci & Engn Tempe AZ 85287 USA

This paper presents a distributed algorithm called L-REMiT for enhancing the lifetime of a source-based multicast tree in wireless ad hoc networks (WANET). The lifetime of a multicast tree is the duration from the formation of the tree to the time when the first node fails due to battery energy exhaustion. L-REMiT assumes that the energy consumed to forward a packet is proportional to the forwarding distance and channel characteristics, and that WANET nodes can dynamically adjust their transmission power. The task of extending the lifetime of a multicast tree is formulated as the task of extending the lifetime of bottleneck nodes in the tree. The number of multicast packets that a bottleneck node can forward, as determined by its residual battery energy and the distance of its farthest child node, is the minimum over all the nodes in the multicast tree. The lifetime of a bottleneck node is improved by reassigning its farthest children to other nodes in the tree with the goal of improving the lifetime of the multicast tree. Nodes only require information from their neighbors for refining the tree in a distributed manner. Simulation results show that L-REMiT has low overhead and performs better than the BIP/MIP and EWMA algorithms.

关键词： ad hoc network wireless network multicast tree broadcast tree distributed algorithm tree lifetime

来源：评论

学校读者我要写书评

暂无评论

Dynamically adapting registration areas to user mobility and call patterns for efficient location management in PCS networks

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2004年第5期12卷 837-850页

作者： Varsamopoulos, G Gupta, SKS Arizona State Univ Ira A Fulton Sch Engn Dept Comp Engn & Sci Tempe AZ 85287 USA

In this paper, we propose an extension to the personal communication services (PCS) location management protocol which uses dynamically overlapped registration areas. The scheme is based on monitoring the aggregate mobility and call pattern of the users during each reconfiguration period and adapting to the mobility and call patterns by either expanding or shrinking registration areas at the end of each reconfiguration period. We analytically characterize the trade-off resulting from the inclusion or exclusion of a cell in a registration area in terms of expected change in aggregate database access cost and signaling overhead. This characterization is used to guide the registration area adaption in a manner in which the signaling and database access load on any given location register (LR) does not exceed a specified limit. Our simulation results show that it is useful to dynamically adapt the registration areas to the aggregate mobility and call patterns of the mobile units when the mobility pattern exhibits locality. For such mobility and call patterns, the proposed scheme can greatly reduce the average signaling and database access load on LRs. Further, the cost of adapting the registration areas is shown to be low in terms of memory and communication requirements.

关键词： adaptive protocol cellular network distributed algorithm distributed load balancing distributed location management dynamic optimization mobile communication network

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：