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

An efficient message passing election algorithm based on Mazurkiewicz's algorithm

FUNDAMENTA INFORMATICAE 2007年第1-3期80卷 221-246页

作者： Chalopin, Jeremie Metivier, Yves Univ Bordeaux LaBRI F-33405 Talence France

We study the election and the naming problems in the asynchronous message passing model. We present a necessary condition based on Angluin's lifting lemma [1] that must be satisfied by any network that admits a naming (or an election) algorithm. We then show that this necessary condition is also sufficient: we present an election and naming algorithm based on Mazurkiewicz's algorithm [17]. The algorithm we obtained is totally asynchronous and it needs a polynomial number of messages of polynomial size, whereas previous election algorithms in this model are pseudo-synchronous and use messages of exponential size.

关键词： distributed algorithm asynchronous message passing model anonymous network local computation election naming covering

来源：评论

学校读者我要写书评

暂无评论

Self-stabilizing local routing in ad hoc networks

引用

COMPUTER JOURNAL 2007年第2期50卷 197-203页

作者： Bein, Doina Datta, Ajoy K. Villain, Vincent Univ Nevada Sch Comp Sci Las Vegas NV 89154 USA Univ Picardie LaRIA F-80025 Amiens France

We present a self-stabilizing optimal (in terms of the distance) local routing algorithm (SOLR) for a wireless mobile ad hoc network. The distance may represent various metrics, including the real distance and the number of hops. The optimal routing for any node is computed for t closest nodes (called t-set) where t is an application-dependent parameter and is decided in advance. The locality is defined with respect to the t-set, not with respect to the direct neighbours. Our protocol is a particular case of distance vector routing protocol, where the number of entries in the routing table is limited to t. A self-stabilizing system has the ability to automatically recover to normal behaviour in case of transient faults without a centralized control. Each node can start in some arbitrary state and with no knowledge of the network architecture, but still eventually computes a correct routing table for the nodes in its t-set. If we assume that the t-set represents the set of destinations for which the shortest path needs to be computed, SOLR becomes an optimal on-demand routing protocol. It can be extended to a global routing protocol by using features specific to other protocols (e.g. hierarchical routing, cluster routing, interval routing, etc.).

关键词： ad hoc network distributed algorithm local routing minimal distance mobile network optimal routing self-stabilization

来源：评论

学校读者我要写书评

暂无评论

An optimal share transfer problem on secret sharing storage systems

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2007年第11期E90A卷 2458-2464页

作者： Miyamoto, Toshiyuki Kumagai, Sadatoshi Osaka Univ Grad Sch Engn Suita Osaka 5650871 Japan

We have been developing a secure and reliable distributed storage system, which uses a secret sharing scheme. In order to efficiently store data in the system, this paper introduces an optimal share transfer problem, and proves it to be, generally, NP-hard. It is also shown that the problem can be resolved into a Steiner tree problem. Finally, through computational experiments we perform the comparison of heuristic algorithms for the Steiner tree problem.

关键词： distributed storage system secret sharing scheme Steiner tree NP-complete distributed algorithm

来源：评论

学校读者我要写书评

暂无评论

Adaptive timeliness of consensus in presence of crash and timing faults

引用

JOURNAL OF PARALLEL AND distributed COMPUTING 2007年第6期67卷 648-658页

作者： Izumi, Taisuke Saitoh, Akinori Masuzawa, Toshimitsu Nagoya Inst Technol Grad Sch Engn Nagoya Aichi 4668555 Japan Tottori Univ Environm Studies Fac Environm & Informat Studies Tottori 6891111 Japan

The Delta-timed uniform consensus is a stronger variant of the traditional consensus and it satisfies the following additional property: every correct process terminates its execution within a constant time Delta (Delta-timeliness), and no two processes decide differently (uniformity). In this paper, we consider the Delta-timed uniform consensus problem in presence of f(c) crash processes and f(t) timing-faulty processes, and propose a Delta-timed uniform consensus algorithm. The proposed algorithm is adaptive in the following sense: it solves the Delta-timed uniform consensus when at least f(t) + 1 correct processes exist in the system. If the system has less than f(t) + 1 correct processes, the algorithm cannot solve the Delta-timed uniform consensus. However, as long as f(t) + 1 processes are non-crashed, the algorithm solves (non-timed) uniform consensus. We also investigate the maximum number of faulty processes that can be tolerated. We show that any Delta-timed uniform consensus algorithm tolerating up to f(t) timing-faulty processes requires that the system has at least f(t) + 1 correct processes. This impossibility result implies that the proposed algorithm attains the maximum resilience about the number of faulty processes. We also show that any A-timed uniform consensus algorithm tolerating up to f(t) timing-faulty processes cannot solve the (non-timed) uniform consensus when the system has less than f(t) + 1 non-crashed processes. This impossibility result implies that our algorithm attains the maximum adaptiveness. (c) 2007 Elsevier Inc. All rights reserved.

关键词： distributed algorithm timeliness property consensus problem crash fault timing fault

来源：评论

学校读者我要写书评

暂无评论

Layering as optimization decomposition: A mathematical theory of network architectures

引用

PROCEEDINGS OF THE IEEE 2007年第1期95卷 255-312页

作者： Chiang, Mung Low, Steven H. Calderbank, A. Robert Doyle, John C. Princeton Univ Dept Elect Engn Princeton NJ 08544 USA CALTECH Dept Comp Sci Pasadena CA 91125 USA CALTECH Dept Elect Engn Pasadena CA 91125 USA Princeton Univ Dept Math Princeton NJ 08544 USA CALTECH Control & Dynam Syst Pasadena CA 91125 USA

Network protocols in layered architectures have historically been obtained on an ad hoc basis, and many of the recent cross-layer designs are also conducted through piecemeal approaches. Network protocol stacks may instead be holistically analyzed and systematically designed as distributed solutions to some global optimization problems. This paper presents a survey of the recent efforts towards a systematic understanding of "layering" as "optimization decomposition," where the overall communication network is modeled by a generalized network utility maximization problem, each layer corresponds to a decomposed subproblem, and the interfaces among layers are quantified as functions of the optimization variables coordinating the subproblems. There can be many alternative decompositions, leading to a choice of different layering architectures. This paper surveys the current status of horizontal decomposition into distributed computation, and vertical decomposition into functional modules such as congestion control, routing, scheduling, random access, power control, and channel coding. Key messages and methods arising from many recent works are summarized, and open issues discussed. Through case studies, it is illustrated how "Layering as optimization Decomposition" provides a common language to think about modularization in the face of complex, networked interactions, a unifying, top-down approach to design protocol stacks, and a mathematical theory of network architectures.

关键词： ad hoc network channel coding computer network congestion control cross-layer design distributed algorithm feedback control game theory internet Lagrange duality medium access control (MAC) network utility maximization (NUM) optimization power control reverse-engineering routing scheduling stochastic networks transmission control protocol (TCP)/Internet protocol (IP) wireless communications

来源：评论

学校读者我要写书评

暂无评论

From ◊W to Ω:: A simple bounded quiescent reliable broadcast-based transformation

引用

JOURNAL OF PARALLEL AND distributed COMPUTING 2007年第1期67卷 125-129页

作者： Mostefaoui, Achour Rajsbaum, Sergio Raynal, Michel Travers, Corentin Inst Rech Informat & Syst Aleatoires F-35042 Rennes France Natl Autonomous Univ Mexico Inst Matemat Mexico City 04510 DF Mexico

Failure detectors in the class oW ensure that every crashed process is eventually suspected by a correct process, and eventually there is a correct process that is never suspected. Failure detectors in the class Omega ensure that eventually all the processes trust the same correct process. This paper presents a very simple and efficient algorithm that transforms any failure detector of the class oW into a failure detector of the class Omega. The simplicity of the transformation is due to its modular design-it is based on an underlying reliable broadcast facility. It is quiescent and requires each message to carry only one process identity, in addition to the control information appended to a message by the reliable broadcast mechanism (namely, a sequence number and the identity of its sender). (C) 2006 Elsevier Inc. All rights reserved.

关键词： asynchronous system distributed algorithm eventual leader failure detector fault-tolerance layer abstraction process crash reliable broadcast

来源：评论

学校读者我要写书评

暂无评论

Eventual leader service in unreliable asynchronous systems: Why? How?

Eventual leader service in unreliable asynchronous systems: ...

引用

6th IEEE International Symposium on Network Computing and Applications

作者： Raynal, Michel Univ Rennes 1 IRISA F-35042 Rennes France

ISBN: (纸本)9780769529226

Providing processes with an eventual leader service is an important issue when one has to design and implement a middleware layer on top of a failure-prone asynchronous distributed system. This invited lecture investigates this problem. It first shows that such a service cannot be built if the underlying system is fully asynchronous. Then, the paper visits several additional behavioral assumptions that have been proposed in the literature to cope with this impossibility and presents corresponding eventual leader election protocols. This lecture can be seen as a guided tour of the eventual leader service problem, whose aim is to benefit researchers and system engineers working in distributed middleware built on top of asynchronous networks.

关键词： assumption coverage asynchronous system behavioral assumption distributed algorithm eventual t-source eventual leader failure detector fault-tolerance message pattern omega oracle partial synchrony process crash system model eventual timely link

来源：评论

学校读者我要写书评

暂无评论

Energy-efficient distance based clustering routing scheme for wireless sensor networks

Energy-efficient distance based clustering routing scheme fo...

引用

International Conference on Computational Science and Its Applications (ICCSA 2007)

作者： Han, Young-Ju Park, Seon-Ho Eom, Jung-Ho Chung, Tai-Myoung Sungkyunkwan Univ Sch Informat & Commun Engn Dept Comp Engn Internet Management Tech Lab 300 Cheoncheon Dong Suwon 440746 Gyeonggi Do South Korea

ISBN: (纸本)9783540744757

Clustering scheme enabling the efficient utilization of the limited energy resources of the deployed sensor nodes can effectively prolong the lifetime of wireless sensor networks. The most common technique in famous clustering schemes is a probabilistic clustering scheme based on a randomized cluster-head rotation for distributing the energy consumption among nodes in each cluster. Because most of those schemes utilize mainly the residual energy of each node as the criterion of clusterhead election, those schemes have demerit which the unbalanced energy consumption among cluster-heads is occurred. To overcome this demerit, we consider a distance from the base station to cluster-heads as well as the residual energy as the criterion of cluster-head election for balanced energy consumption among cluster-heads. Our scheme provides fully distributed manner by utilizing local information and good energy-efficiency by load balanced clustering scheme. Through simulation experiments, we showed that the proposed scheme is more effective than LEACH and EECS in prolonging the lifespan of wireless sensor networks.

关键词： wireless sensor network routing protocol clustering algorithm distributed algorithm

来源：评论

学校读者我要写书评

暂无评论

Energy and utility optimization in wireless networks with random access

Energy and utility optimization in wireless networks with ra...

引用

IEEE International Conference on Communications (ICC 2007)

作者： Khodaian, Amirmahdi Khalaj, Babak H. Sharif Univ Technol Dept Elect Engn Tehran Iran

ISBN: (纸本)9781424403523

Energy consumption is a main issue of concern in wireless networks. Energy minimization increases the time that networks' nodes work properly without recharging or substituting batteries. Another criterion for network performance is data transmission rate which is usually quantified by a network utility function. There exists an inherent tradeoff between these criteria and enhancing one of them can deteriorate the other one. In this paper, we consider both Network Utility Maximization (NUM) and energy minimization in a bi-criterion optimization problem. The problem is formulated for Random Access (RA) Medium Access Control (MAC) for ad-hoc networks. First, we optimize performance of the MAC and define utility as a monotonically increasing function of link throughputs. We investigate the optimal tradeoff between energy and utility in this part. In the second part, we define utility as a function of end to end rates and optimize MAC and transport layers simultaneously. We calculate optimal persistence probabilities and end-to-end rates. Finally, by means of duality theorem, we decompose the problem into smaller subproblems, which are solved at node and network layers separately. This decomposition avoids need for a central unit while sustaining benefits of layering.

关键词： energy-utility tradeoff persistence probability random access convex optimization distributed algorithm

来源：评论

学校读者我要写书评

暂无评论

Non-searchability of random power-law graphs

Non-searchability of random power-law graphs

引用

11th International Conference on Principles of distributed Systems

作者： Duchon, Philippe Eggemann, Nicole Hanusse, Nicolas Univ Bordeaux CNRS LaBRI 351 Cours Liberat F-33405 Talence France Brunel Univ Dept Math Uxbridge UB8 3PH Middx England

ISBN: (纸本)9783540770954

We investigate the complexity of searching for a given vertex in a scale-free graph, using only locally gathered information. In such graphs, the number of nodes of degree x is proportional to x(-beta) for some constant beta > 0. We consider two random scale-free graph models: the Chung-Lu model and the Mori model (a generalization of the Barabasi-Albert model) proving two lower bounds of Omega(n/log theta(beta) n) and Omega(n1/2) on the expected time to find the worst-case target, under a restrictive model of local information.

关键词： distributed algorithm routing random graphs

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：