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

distributed resource allocation for stream data processing

2nd International Conference on High Performance Computing and Communications (HPCC 2006)

作者： Tang, Ao Liu, Zhen Xia, Cathy Zhang, Li CALTECH Dept Elect Engn Pasadena CA 91125 USA IBM Corp TJ Watson Res Ctr Hawthorne NY 10532 USA

ISBN: (纸本)3540393684

Data streaming applications are becoming more and more common due to the rapid development in the areas such as sensor networks, multimedia streaming, and on-line data mining, etc. These applications are often running in a decentralized, distributed environment. The requirements for processing large volumes of streaming data at real time have posed many great design challenges. It is critical to optimize the ongoing resource consumption of multiple, distributed, cooperating, processing units. In this paper, we consider a generic model for the general stream data processing systems. We address the resource allocation problem for a collection of processing units so as to maximize the weighted sum of the throughput of different streams. Each processing unit may require multiple input data streams simultaneously and produce one or many valuable output streams. Data streams flow through such a system after processing at multiple processing units. Based on this framework, we develop distributed algorithms for finding the best resource allocation schemes in such data stream processing networks. Performance analysis on the optimality and complexity of these algorithms are also provided.

关键词： stream processing distributed algorithm resource allocation

来源：评论

学校读者我要写书评

暂无评论

A tutorial on decomposition methods for network utility maximization

引用

IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS 2006年第8期24卷 1439-1451页

作者： Palomar, Daniel P. Chiang, Mung Princeton Univ Dept Elect Engn Princeton NJ 08544 USA Princeton Univ Appl & Computat Math Princeton NJ 08544 USA

A systematic understanding of the decomposability structures in network utility maximization is key to both resource allocation and functionality allocation. It helps us obtain the most appropriate distributed algorithm for a given network resource allocation problem, and quantifies the comparison across architectural alternatives of modularized network design. Decomposition theory naturally provides the mathematical language to build an analytic foundation for the design of modularized and distributed control of networks. In this tutorial paper, we first review the basics of convexity, Lagrange duality, distributed subgradient method, Jacobi and Gauss-Seidel iterations, and implication of different time scales of variable updates. Then, we introduce primal, dual, indirect, partial, and hierarchical decompositions, focusing on network utility maximization problem formulations and the meanings of primal and dual decompositions in terms of network architectures. Finally, we present recent examples on: systematic search for alternative decompositions;decoupling techniques for coupled objective functions;and decoupling techniques for coupled constraint sets that are not readily decomposable.

关键词： congestion control cross-layer design decomposition distributed algorithm network architecture network control by pricing network utility maximization optimization power control resource allocation

来源：评论

学校读者我要写书评

暂无评论

A micropower centroiding vision processor

引用

IEEE JOURNAL OF SOLID-STATE CIRCUITS 2006年第6期41卷 1430-1443页

作者： Constandinou, Timothy G. Toumazou, Christofer Univ London Imperial Coll Sci Technol & Med Inst Biomed Engn London SW7 2AZ England

A biologically-inspired hybrid vision chip is presented for real-time object-based processing for tasks such as centroiding, sizing and counting of enclosed objects. This system presents the first silicon retina capable of centroiding and sizing multiple objects in true parallel fashion. Based on a novel distributed algorithm, this approach uses the input image to enclose a feedback loop to realize a data-driven pulsating action. The sensor provides a resolution of 48 x 48 pixels with a 85 mu m X 85 mu m pixel footprint and has been measured to consume 243 mu W at 1.8-V supply, achieving an equivalent computational efficiency of 724.64 MIPS/mW with a 500-mu s process time.

关键词： centroiding CMOS image sensor distributed algorithm focal plane processing micropower object detection parallel processing silicon retina target tracking vision chip

来源：评论

学校读者我要写书评

暂无评论

distributed data structures: A survey on informative labeling schemes

引用

31st International Symposium on Mathematical Foundations of Computer Science

作者： Gavoille, Cyril Univ Bordeaux 1 LaBRI F-33405 Talence France

ISBN: (纸本)3540377913

In this talk, we will survey the role of data structures for compactly storing and representing various types of information in a localized and distributed fashion. Traditional approaches to data representation are based on global data structures, which require access to the entire structure even if the sought information involves only a small and local set of entities. In contrast, localized data representation schemes are based on breaking the information into small local pieces, or labels, selected in a way that allows one to infer information regarding a small set of entities directly from their labels, without using any additional (global) information. © Springer-Verlag Berlin Heidelberg 2006.

关键词： Data-structures distributed algorithm Graphs Labeling scheme

来源：评论

学校读者我要写书评

暂无评论

Coverage by directional sensors in randomly deployed wireless sensor networks

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2006年第1期11卷 21-41页

作者： Ai, J Abouzeid, AA Rensselaer Polytech Inst Dept Elect Comp & Syst Engn Troy NY 12180 USA

We study a novel "coverage by directional sensors" problem with tunable orientations on a set of discrete targets. We propose a Maximum Coverage with Minimum Sensors (MCMS) problem in which coverage in terms of the number of targets to be covered is maximized whereas the number of sensors to be activated is minimized. We present its exact Integer Linear Programming (ILP) formulation and an approximate (but computationally efficient) centralized greedy algorithm (CGA) solution. These centralized solutions are used as baselines for comparison. Then we provide a distributed greedy algorithm (DGA) solution. By incorporating a measure of the sensors residual energy into DGA, we further develop a Sensing Neighborhood Cooperative Sleeping (SNCS) protocol which performs adaptive scheduling on a larger time scale. Finally, we evaluate the properties of the proposed solutions and protocols in terms of providing coverage and maximizing network lifetime through extensive simulations. Moreover, for the case of circular coverage, we compare against the best known existing coverage algorithm.

关键词： directional sensors mathematical programming optimization distributed algorithm scheduling network lifetime

来源：评论

学校读者我要写书评

暂无评论

Movement-assisted sensor deployment

引用

IEEE TRANSACTIONS ON MOBILE COMPUTING 2006年第6期5卷 640-652页

作者： Wang, GL Cao, GH La Porta, TF Penn State Univ Dept Comp Sci & Engn University Pk PA 16802 USA

Adequate coverage is very important for sensor networks to fulfill the issued sensing tasks. In many working environments, it is necessary to make use of mobile sensors, which can move to the correct places to provide the required coverage. In this paper, we study the problem of placing mobile sensors to get high coverage. Based on Voronoi diagrams, we design two sets of distributed protocols for controlling the movement of sensors, one favoring communication and one favoring movement. In each set of protocols, we use Voronoi diagrams to detect coverage holes and use one of three algorithms to calculate the target locations of sensors if holes exist. Simulation results show the effectiveness of our protocols and give insight on choosing protocols and calculation algorithms under different application requirements and working conditions.

关键词： mobile sensor networks sensor coverage distributed algorithm

来源：评论

学校读者我要写书评

暂无评论

Asymptotic analysis of a leader election algorithm

引用

THEORETICAL COMPUTER SCIENCE 2006年第1-3期359卷 239-254页

作者： Lavault, Christian Louchard, Guy Univ Paris 13 LIPN UMR CNRS 7030 F-93430 Villetaneuse France Free Univ Brussels Dept Informat B-1050 Brussels Belgium

Itai and Rodeh showed that, on the average, the communication of a leader election algorithm takes no more than LN bits, where L similar or equal to 2.441716 and N denotes the size of the ring. We give a precise asymptotic analysis of the average number of rounds M(n) required by the algorithm, proving for example that M(infinity) := lim(n-->infinity) M(n)=2.441715879..., where n is the number of starting candidates in the election. Accurate asymptotic expressions of the second moment M(2) (n) of the discrete random variable at hand, its probability distribution, and the generalization to all moments are given. Corresponding asymptotic expansions (n --> 00) are provided for sufficiently large j, where j counts the number of rounds. Our numerical results show that all computations perfectly fit the observed values. Finally, we investigate the generalization to probability t/n, where t is a non-negative real parameter. The real function M(infinity, t) := lim(n-->infinity) M(n, t) is shown to admit one unique minimum M(infinity, t*) on the real segment (0, 2). Furthermore, the variations of M(infinity, t) on the whole real line are also studied in detail. (C) 2006 Elsevier B.V. All rights reserved.

关键词： complexity analysis asymptotic approximation distributed algorithm probability distribution

来源：评论

学校读者我要写书评

暂无评论

Concurrent maintenance of rings

引用

distributed COMPUTING 2006年第2期19卷 126-148页

作者： Li, Xiaozhou Misra, Jayadev Plaxton, C. Greg Univ Texas Dept Comp Sci Austin TX 78712 USA

A central problem for structured peer-to-peer networks is topology maintenance, that is, how to properly update neighbor variables when nodes join or leave the network, possibly concurrently. In this paper, we consider the maintenance of the ring topology, the basisof several peer-to-peer networks, in the fault-free environment. We design, and prove the correctness of, protocols that maintain a bidirectional ring under both joins and leaves. Our protocols update neighbor variables once a membership change occurs. We prove the correctness of our protocols using an assertional proof method, that is, we first identify a global invariant for a protocol and then show that every action of the protocol preserves the invariant. Our protocols are simple and our proofs are rigorous and explicit.

关键词： concurrency distributed algorithm distributed data structures network protocols correctness

来源：评论

学校读者我要写书评

暂无评论

Performing work in broadcast networks

引用

distributed COMPUTING 2006年第6期18卷 435-451页

作者： Chlebus, Bogdan S. Kowalski, Dariusz R. Lingas, Andrzej Univ Colorado Dept Comp Sci & Engn Denver CO 80217 USA Hlth Sci Ctr Denver CO USA Univ Liverpool Dept Comp Sci Liverpool L69 3ZF Merseyside England Lund Univ Dept Comp Sci S-22100 Lund Sweden

We consider the problem of how to schedule t similar and independent tasks to be performed in a synchronous distributed system of p stations communicating via multiple-access channels. Stations are prone to crashes whose patterns of occurrence are specified by adversarial models. Work, defined as the number of the available processor steps, is the complexity measure. We consider only reliable algorithms that perform all the tasks as long as at least one station remains operational. It is shown that every reliable algorithm has to perform work Omega(t + p root t) even when no failures occur. An optimal deterministic algorithm for the channel with collision detection is developed, which performs work O(t + p root t). Another algorithm, for the channel without collision detection, performs work O(t + p root t + p min {f, t}), where f < p is the number of failures. This algorithm is proved to be optimal, provided that the adversary is restricted in failing no more than f stations. Finally, we consider the question if randomization helps against weaker adversaries for the channel without collision detection. A randomized algorithm is developed which performs the expected minimum amount O(t + p root t) of work, provided that the adversary may fail a constant fraction of stations and it has to select failure-prone stations prior to the start of an execution of the algorithm.

关键词： distributed algorithm multiple-access channel fail-stop failure adversary independent tasks

来源：评论

学校读者我要写书评

暂无评论

Time-free and timer-based assumptions can be combined to obtain eventual leadership

引用

IEEE TRANSACTIONS ON PARALLEL AND distributed SYSTEMS 2006年第7期17卷 656-666页

作者： Mostefaoui, Achour Raynal, Michel Travers, Corentin Univ Rennes 1 IRISA F-35042 Rennes France

Leader-based protocols rest on a primitive able to provide the processes with the same unique leader. Such protocols are very common in distributed computing to solve synchronization or coordination problems. Unfortunately, providing such a primitive is far from being trivial in asynchronous distributed systems prone to process crashes. (It is even impossible in fault-prone purely asynchronous systems.) To circumvent this difficulty, several protocols have been proposed that build a leader facility on top of an asynchronous distributed system enriched with additional assumptions. The protocols proposed so far consider either additional assumptions based on synchrony or additional assumptions on the pattern of the messages that are exchanged. Considering systems with n processes and up to f process crashes, 1 <= f < n, this paper investigates the combination of a time-free assumption on the message pattern with a synchrony assumption on process speed and message delay. It shows that both types of assumptions can be combined to obtain a hybrid eventual leader protocol benefiting from the best of both worlds. This combined assumption considers a star communication structure involving f + 1 processes. Its noteworthy feature lies in the level of combination of both types of assumption that is "as fine as possible" in the sense that each of the f channels of the star has to satisfy a property independently of the property satisfied by each of the f - 1 other channels (the f channels do not have to satisfy the same assumption). More precisely, this combined assumption is the following: There is a correct process p (center of the star) and a set Q of f processes q ( p is not an element of Q) such that, eventually, either 1) each time it broadcasts a query, q receives a response from p among the (n - f) first responses to that query, or 2) the channel from p to q is timely. (The processes in the set Q can crash.) A surprisingly simple eventual leader protocol based on this f

关键词： asynchronous system distributed algorithm fault tolerance hybrid protocol leader election process crash time-free assumption timer-based assumption

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：