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

OPTIMAL distributed algorithms FOR SORTING AND RANKING

IEEE TRANSACTIONS ON COMPUTERS 1985年第4期34卷 376-379页

作者： ZAKS, S MIT COMP SCI LABCAMBRIDGEMA 02139

We study the problems of sorting and ranking n processors that have initial values (not necessarily distinct) in a distributed system. Sorting means that the initial values have to move around in the network and be assigned to the processors according to their distinct identities, while ranking means that the numbers 1, 2,..., n have to be assigned to the processors according to their initial values; ties between initial values can be broken in any chosen way. Assuming a tree network, and assuming that a message can contain an initial value, an identity, or a rank, we present an algorithm for the ranking problem that uses, in the worst case, at most n2/2+O(n) such messages. The algorithm is then extended to perform sorting, using in the worst case at most 3n2/4+O(n) messages. Both algorithms are using a total of O(n) space. The algorithms are extended to general networks. The expected behavior of these algorithms for three classes of trees is discussed. Assuming that the initial values, identities, and ranks can be compared only within themselves, lower bounds of n2/2 and 3n2/4 messages are proved for a worst case execution of any algorithm to solve the ranking and sorting problems, respectively.

关键词： distributed algorithms message complexity ranking sorting

来源：评论

学校读者我要写书评

暂无评论

Joint Sensing and Power Allocation in Nonconvex Cognitive Radio Games: Nash Equilibria and distributed algorithms

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2013年第7期59卷 4626-4661页

作者： Scutari, Gesualdo Pang, Jong-Shi SUNY Buffalo Dept Elect Engn Buffalo NY 14051 USA Univ Illinois Dept Ind & Enterprise Syst Engn Urbana IL 61801 USA

In this paper, we propose a novel class of Nash problems for cognitive radio (CR) networks, modeled as Gaussian frequency-selective interference channels, wherein each secondary user (SU) competes against the others to maximize his own opportunistic throughput by choosing jointly the sensing duration, the detection thresholds, and the vector power allocation. The proposed general formulation allows us to accommodate several (transmit) power and (deterministic/probabilistic) interference constraints, such as constraints on the maximum individual and/or aggregate (probabilistic) interference tolerable at the primary receivers. To keep the optimization as decentralized as possible, global (coupling) interference constraints are imposed by penalizing each SU with a set of time-varying prices based upon his contribution to the total interference;the prices are thus additional variable to optimize. The resulting players' optimization problems are nonconvex;moreover, there are possibly price clearing conditions associated with the global constraints to be satisfied by the solution. All this makes the analysis of the proposed games a challenging task;none of classical results in the game theory literature can be successfully applied. The main contribution of this paper is to develop a novel optimization-based theory for studying the proposed nonconvex games;we provide a comprehensive analysis of the existence and uniqueness of a standard Nash equilibrium, devise alternative best-response based algorithms, and establish their convergence. Some of the proposed algorithms are totally distributed and asynchronous, whereas some others require limited signaling among the SUs (in the form of consensus algorithms) in favor of better performance;overall, they are thus applicable to a variety of CR scenarios, either cooperative or noncooperative, which allows the SUs to explore the existing tradeoff between signaling and performance.

关键词： Cognitive radio distributed algorithms game theory quasi-Nash equilibrium spectrum sensing variational inequalities

来源：评论

学校读者我要写书评

暂无评论

Algon: From Interchangeable distributed algorithms to Interchangeable Middleware

引用

ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE 2005年第SPEC. ISS.期114卷 65-85页

作者： Renaud, Karen Bishop, Judith Lo, Johnny Worrall, Basil Univ Glasgow Dept Comp Sci Glasgow Lanark Scotland Univ Pretoria Dept Comp Sci Pretoria South Africa

We present the design and implementation of a framework for interchangeable distributed algorithms. The algorithms are drawn from the set which includes mutual exclusion, deadlock detection and agreement protocols, and we have implemented several examples of the first tonsiswo of these. Algon cts of a library of algorithms, a framework for incorporating them into a new or existing system, and a tool for evaluating comparative performance. In this way, much of the complexity related to distributed systems can be isolated in its own component level and the programmer can choose from among different algorithms in the same class based on performance in a given application. Incorporating many algorithms in a single framework was made possible by the observation that algorithms in a given class, e.g. mutual exclusion, almost always expose the same methods. These methods interface with an Algon scheduler which maintains state and provides convenient hooks for the application to invoke the services of the algorithm. In this paper we describe the structure of Algon in detail, with a distributed deadlock detection algorithm as the case study. We then extend the notion of separation of concerns by creating an addition layer in Algon, underneath which the middleware that runs on each node can be interchanged, for example from Java-RMI to CORBA. Challenges in the re-tooling of the system, related to multiple inheritance, exceptions and the automatic generation of stubs and skeletons in our implementation language, Java, were overcome in novel ways. Algon has the potential to be a framework with a long life, as it can adapt to new middleware, such as. NET.

关键词： distributed algorithms interchangeability components middleware independence separation of concerns programming framework

来源：评论

学校读者我要写书评

暂无评论

ILF and DAWN for verifying distributed algorithms - an idea for a tool

引用

Fundamenta Informaticae 1999年第3期37卷 201-211页

作者： Baar, Thomas Kindler, Ekkart Institut für Informatik Humboldt-Universität zu Berlin D-10099 Berlin Germany. Institut für Informatik Humboldt-Universität zu Berlin D-10099 Berlin Germany.

The distributed algorithms Working Notation (DAWN) was designed for modelling and verifying algorithms in an intuitive way. Nevertheless, DAWN proofs are formal. In this paper, we show that it is possible to check correctness of a DAWN proof fully automatically: For each step in a DAWN proof, we can generate a set of proof obligations which can automatically be checked by help of automated theorem provers. The verification tool ILF provides a uniform interface to many theorem provers - which makes it an ideal partner for DAWN and a basis for building a DAWN-tool.

关键词： Automated Theorem Provers distributed algorithms Verification Z

来源：评论

学校读者我要写书评

暂无评论

distributed algorithms for Peak Ramp Minimization Problem in Smart Grid

Distributed Algorithms for Peak Ramp Minimization Problem in...

引用

IEEE International Conference on Smart Grid Communications (SmartGridComm)

作者： Hung Khanh Nguyen Khodaei, Amin Han, Zhu Univ Houston Dept Elect & Comp Engn Houston TX 77004 USA Univ Denver Dept Elect & Comp Engn Denver CO 80210 USA

ISBN: (纸本)9781509040759

The arrival of smaIl-scale distributed energy generation in the future smart grid has led to the emergence of so-called prosumers, who can both consume as weIl as produce energy. By using local generation from renewable energy resources, the stress on power generation and supply system can be significantly reduced during high demand periods. However, this also creates a significant challenge for conventional power plants that suddenly need to ramp up quickly when the renewable energy drops off. In this paper, we propose an energy consumption scheduling problem tor prosumers to minimize the peak ramp of the system. The optimal schedule of prosumers can be obtained by solving the centralized optimization problem. However, due to the privacy concerns and the distributed topology of the power system, the centralized design is difficult to implement in practice. Therefore, we propose the distributed algorithms to efficiently solve the centralized problem using the alternating direction method of multiplier (ADMM), in which each prosumer independently schedules its energy consumption profile. The simulation results demonstrate the convergence performance of the proposed algorithms as weIl as the capability of our model in reducing the peak ramp of the system.

关键词： Smart grids Energy consumption Optimization distributed algorithms Energy storage Renewable energy sources distributed power generation Smart grids distributed algorithms Renewable energy distributed power generation energy consumption renewable energy sources energy storage RAMP Ramps conventional power plant Power production

来源：评论

学校读者我要写书评

暂无评论

Towards better understanding of the behaviour of Bluetooth networks distributed algorithms

引用

INTERNATIONAL JOURNAL OF PARALLEL EMERGENT AND distributed SYSTEMS 2012年第6期27卷 563-586页

作者： Jedda, Ahmed Jourdan, Guy-Vincent Zaguia, Nejib Univ Ottawa Sch Elect Engn & Comp Sci 800 King Edward Ottawa ON K1N 6N5 Canada

The use of frequency hopping spread spectrum in Bluetooth significantly differentiates its networks from classical radio networks. In order to observe such differences, we studied basic algorithms, in particular neighbour discovery and message exchange algorithms. Some of the major differences are found in the procedures of device discovery and link establishment, which are studied in this paper. We focus on their impact on Bluetooth networks' distributed algorithms. We show through detailed simulation experiments that minor modifications to the Bluetooth specifications or their implementation may significantly affect the performance of well-known neighbour discovery algorithms. We then study the impact of the procedures of link establishment with the purpose of finding time-efficient implementations of communication rounds for Bluetooth networks. We study OrderedExchange and RandomExchange as both algorithms implement communication rounds in Bluetooth, but use the PAGE and PAGE SCAN states differently. Theoretical analysis shows that RandomExchange has a better time complexity, while simulation experiments show that OrderedExchange significantly outperforms RandomExchange in networks with a practical size (110 nodes and less). We use the previous results to improve the time efficiency of Bluetooth scatternet formation algorithms through the introduction of the time-efficient algorithm OrderedExchangeCMIS. We believe that the study of some other basic algorithms (such as broadcasting, spanningtree and election) will lead to a better understanding of Bluetooth networks, and as a consequence, to more efficient algorithms that fully leverage the strength of this type of network.

关键词： Bluetooth frequency hopping Bluetooth scatternet formation distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

PowerModelsADA: A Framework for Solving Optimal Power Flow Using distributed algorithms

引用

IEEE TRANSACTIONS ON POWER SYSTEMS 2024年第1期39卷 2357-2360页

作者： Alkhraijah, Mohannad Harris, Rachel Coffrin, Carleton Molzahn, Daniel K. Georgia Inst Technol Sch Elect & Comp Engn Atlanta GA 30332 USA Los Alamos Natl Lab Adv Network Sci Initiat Los Alamos NM 87545 USA

This letter presents PowerModelsADA, an open-source framework for solving Optimal Power Flow (OPF) problems using Alternating distributed algorithms (ADA). PowerModelsADA provides a framework to test, verify, and benchmark both existing and new ADAs. This letter demonstrates use cases for PowerModelsADA and validates its implementation with multiple OPF formulations.

关键词： Load flow Generators Optimization Data structures Benchmark testing Loading distributed algorithms distributed optimization optimal power flow

来源：评论

学校读者我要写书评

暂无评论

Stochastic analysis of average-based distributed algorithms

引用

JOURNAL OF APPLIED PROBABILITY 2021年第2期58卷 394-410页

作者： Mocquard, Yves Robin, Frederique Sericola, Bruno Anceaume, Emmanuelle Univ Rennes Inria CNRS IRISA Campus Beaulieu F-35042 Rennes France

We analyze average-based distributed algorithms relying on simple and pairwise random interactions among a large and unknown number of anonymous agents. This allows the characterization of global properties emerging from these local interactions. Agents start with an initial integer value, and at each interaction keep the average integer part of both values as their new value. The convergence occurs when, with high probability, all the agents possess the same value, which means that they all know a property of the global system. Using a well-chosen stochastic coupling, we improve upon existing results by providing explicit and tight bounds on the convergence time. We apply these general results to both the proportion problem and the system size problem.

关键词： Averaging stochastic process interacting particle systems Markov chain coupling distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

distributed algorithms for Tasking Large Sensor Networks

Distributed Algorithms for Tasking Large Sensor Networks

引用

作者： Mehrotra, Shashank Virginia Tech | University

Recent advances in wireless communications along with developments in low-power circuit design and micro-electro mechanical systems (MEMS) have heralded the advent of compact and inexpensive wireless micro-sensor devices. A large network of such sensor nodes capable of communicating with each other provides significant new capabilities for automatically collecting and analyzing data from physical environments. A notable feature of these networks is that more nodes than are strictly necessary may be deployed to cover a given region. This permits the system to provide reliable information, tolerate many types of faults, and prolong the effective service time. Like most wireless systems, achieving low power consumption is a key consideration in the design of these networks. This thesis presents algorithms for managing power at the distributed system level, rather than just at the individual node level. These distributed algorithms allocate work based on user requests to the individual sensor nodes that comprise the network. The primary goal of the algorithms is to provide a robust and scalable approach for tasking nodes that prolongs the effective life of the network. Theoretical analysis and simulation results are presented to characterize the behavior of these algorithms. Results obtained from simulation experiments indicate that the algorithms can achieve a significant increase in the life of the network. In some cases this may be by an order of magnitude. The algorithms are also shown to ensure a good quality of sensor coverage while improving the network life. Finally, they are shown to be robust to faults and scale to large numbers of nodes.

关键词： Wireless Micro-Sensors Energy Efficient Protocols distributed Sensor Networks distributed algorithms Thesis

来源：评论

学校读者我要写书评

暂无评论

Input-Dynamic distributed algorithms for Communication Networks

引用

PROCEEDINGS OF THE ACM ON MEASUREMENT AND ANALYSIS OF COMPUTING SYSTEMS 2021年第1期5卷 1–33页

作者： Foerster, Klaus-Tycho Korhonen, Janne H. Paz, Ami Rybicki, Joel Schmid, Stefan Univ Vienna Fac Comp Sci Vienna Austria IST Austria Klosterneuburg Austria

Consider a distributed task where the communication network is fixed but the local inputs given to the nodes of the distributed system may change over time. In this work, we explore the following question: if some of the local inputs change, can an existing solution be updated efficiently, in a dynamic and distributed manner? To address this question, we define the batch dynamic CONGEST model in which we are given a bandwidth-limited communication network and a dynamic edge labelling defines the problem input. The task is to maintain a solution to a graph problem on the labeled graph under batch changes. We investigate, when a batch of alpha edge label changes arrive, - how much time as a function of.. we need to update an existing solution, and - how much information the nodes have to keep in local memory between batches in order to update the solution quickly. Our work lays the foundations for the theory of input-dynamic distributed network algorithms. We give a general picture of the complexity landscape in this model, design both universal algorithms and algorithms for concrete problems, and present a general framework for lower bounds. In particular, we derive non-trivial upper bounds for two selected, contrasting problems: maintaining a minimum spanning tree and detecting cliques.

关键词： dynamic graph algorithms congest model distributed algorithms communication networks network management

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：