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

RANDOM-WALKS, HEAT-EQUATION AND distributed algorithms

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS 1994年第2期53卷 243-274页

作者： LOUCHARD, G SCHOTT, R TOLLEY, M ZIMMERMANN, P UNIV LIBRE BRUXELLES DEPT INFORMAT B-1050 BRUSSELS BELGIUM UNIV NANCY 1 INRIA LORRAINE CRIN F-54506 VANDOEUVRE LES NANCY FRANCE INST NATL RECH INFORMAT & AUTOMAT LORRAINE F-54600 VILLERS LES NANCY FRANCE

New results are obtained concerning the analysis of the storage allocation algorithm which permits one to maintain two stacks inside a shared (continuous) memory area of fixed size m and of the banker's algorithm (a deadlock avoidance policy). The formulation of these problems is in terms of random walks inside polygonal domains in a two-dimensional lattice space with several reflecting barriers and one absorbing barrier. For the two-stacks problem, the return time to the origin, the time to absorption, the last leaving time from the origin and the number of returns to the origin before absorption are investigated. For the banker's algorithm, the trend-free absorbed random walk is analysed with numerical methods. We finally analyse the average excursion along one axis for the classical random walk: an analytic method enables us to deduce asymptotic results for this average excursion.

关键词： RANDOM WALK HEAT EQUATION DIFFUSION PROCESSES distributed algorithms STACKS SHARING BANKER ALGORITHM

来源：评论

学校读者我要写书评

暂无评论

On the power of randomization in distributed algorithms in dynamic networks with adaptive adversaries

引用

JOURNAL OF PARALLEL AND distributed COMPUTING 2022年 159卷 35-50页

作者： Jahja, Irvan Yu, Haifeng Hou, Ruomu Natl Univ Singapore COM113 Comp Dr Singapore 117417 Singapore

This paper investigates the power of randomization in general distributed algorithms in dynamic networks where the network's topology may evolve over time, as determined by some adaptive adversary. In such a context, randomization may help algorithms to better deal with i) "bad" inputs to the algorithm, and ii) evolving topologies generated by "bad" adaptive adversaries. We prove that randomness offers limited power to better deal with "bad" adaptive adversary. We define a simple notion of prophetic adversary for determining the evolving topologies. Such an adversary accurately predicts all randomness in the algorithm beforehand, and hence the randomness will be useless against "bad" prophetic adversaries. Given a randomized algorithm P whose time complexity satisfies some mild conditions, we prove that P can always be converted to a new algorithm Q with comparable time complexity, even when Q runs against prophetic adversaries. This implies that the benefit of P using randomness for dealing with the adaptive adversaries is limited. (c) 2021 Elsevier Inc. All rights reserved.

关键词： Derandomization distributed algorithms Adversary Dynamic networks

来源：评论

学校读者我要写书评

暂无评论

Optimization-Based distributed algorithms for Mobile Data Gathering in Wireless Sensor Networks

引用

IEEE TRANSACTIONS ON MOBILE COMPUTING 2012年第10期11卷 1464-1477页

作者： Zhao, Miao Yang, Yuanyuan SUNY Stony Brook Dept Elect & Comp Engn Stony Brook NY 11794 USA

Recent advances have shown a great potential of mobile data gathering in wireless sensor networks, where one or more mobile collectors are employed to collect data from sensors via short-range communications. Among a variety of data gathering approaches, one typical scheme is called anchor-based mobile data gathering. In such a scheme, during each periodic data gathering tour, the mobile collector stays at each anchor point for a period of sojourn time, and in the meanwhile the nearby sensors transmit data to the collector in a multihop fashion. In this paper, we focus on such a data gathering scheme and provide distributed algorithms to achieve its optimal performance. We consider two different cases depending on whether the mobile collector has fixed or variable sojourn time at each anchor point. We adopt network utility, which is a properly defined function, to characterize the data gathering performance, and formalize the problems as network utility maximization problems under the constraints of guaranteed network lifetime and data gathering latency. To efficiently solve these problems, we decompose each of them into several subproblems and solve them in a distributed manner, which facilitates the scalable implementation of the optimization algorithms. Finally, we provide extensive numerical results to demonstrate the usage and efficiency of the proposed algorithms and complement our theoretical analysis.

关键词： Wireless sensor networks mobile data gathering distributed algorithms network utility convex optimization

来源：评论

学校读者我要写书评

暂无评论

Evolving distributed algorithms With Genetic Programming

引用

IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION 2012年第2期16卷 242-265页

作者： Weise, Thomas Tang, Ke Univ Sci & Technol China Sch Comp Sci & Technol Nat Inspired Computat & Applicat Lab Hefei 230027 Anhui Peoples R China

In this paper, we evaluate the applicability of genetic programming (GP) for the evolution of distributed algorithms. We carry out a large-scale experimental study in which we tackle three well-known problems from distributed computing with six different program representations. For this purpose, we first define a simulation environment in which phenomena such as asynchronous computation at changing speed and messages taking over each other, i.e., out-of-order message delivery, occur with high probability. Second, we define extensions and adaptations of established GP approaches (such as tree-based and linear GP) in order to make them suitable for representing distributed algorithms. Third, we introduce novel rule-based GP methods designed especially with the characteristic difficulties of evolving algorithms (such as epistasis) in mind. Based on our extensive experimental study of these approaches, we conclude that GP is indeed a viable method for evolving non-trivial, deterministic, non-approximative distributed algorithms. Furthermore, one of the two rule-based approaches is shown to exhibit superior performance in most of the tasks and thus can be considered as an interesting idea also for other problem domains.

关键词： Critical section distributed algorithms election fraglets GCD genetic programming LGP mutual exclusion rule-based genetic programming SGP

来源：评论

学校读者我要写书评

暂无评论

Scalable, distributed algorithms for Solving Linear Equations via Double-Layered Networks

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2020年第3期65卷 1132-1143页

作者： Wang, Xuan Mou, Shaoshuai Anderson, Brian D. O. Purdue Univ Sch Aeronaut & Astronaut W Lafayette IN 47906 USA Hangzhou Dianzi Univ Hangzhou 310018 Peoples R China Data 61 CSIRO Canberra ACT 2601 Australia Australian Natl Univ Sch Informat Sci & Engn Canberra ACT 2600 Australia

This paper proposes scalable, distributed algorithms for solving linear equations by integrating two mechanisms, termed consensus and conservation, in double-layered multiagent networks. The multiagent network considered in this paper is composed of clusters and each cluster consists of an aggregator and a subnetwork of agents. By achieving consensus and conservation through agent-agent communications in the same cluster and aggregator-ggregator communications among different clusters, respectively, distributed algorithms are devised for agents to cooperatively achieve a solution to the overall linear equation. These algorithms outperform existing algorithms, including but not limited to the following aspects-first, each agent does not have to know as much as a complete row or column of the overall equation;second, each agent only needs to control as few as two scalar states when the number of clusters and the number of agents are sufficiently large;third, the dimensions of agents' states in the proposed algorithms do not have to be the same (while in contrast, algorithms based on the idea of standard consensus inherently require all agents' states to be of the same dimension). Both analytical proof and simulation results are provided to validate exponential convergence of the proposed distributed algorithms in solving linear equations.

关键词： Mathematical model distributed algorithms Clustering algorithms Nickel Standards Optimization Information exchange distributed algorithms double-layered framework linear equations multiagent networks

来源：评论

学校读者我要写书评

暂无评论

AN APPLICATION OF NAME BASED ADDRESSING TO LOW-LEVEL distributed algorithms

引用

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING 1985年第1期11卷 59-67页

作者： AHAMAD, M BERNSTEIN, AJ Department of Computer Science State University of New York at Stony Brook

An interprocess communication structure for a distributed language is described which provides message level communication, multicast, and a generalized naming facility. The design is oriented to the needs of low level algorithms which, for example, might be used in a distributed operating system to support resource allocation or enhance reliability. The proposal is illustrated by programming several distributed algorithms from the literature. An implementation is described that takes advantage of physical multicast technology, and reduces to more conventional schemes for common communication paradigms.

关键词： Multicast distributed algorithms distributed Languages

来源：评论

学校读者我要写书评

暂无评论

Revisiting Finite-Time distributed algorithms via Successive Nulling of Eigenvalues

引用

IEEE SIGNAL PROCESSING LETTERS 2015年第1期22卷 54-57页

作者： Safavi, Sam Khan, Usman A. Tufts Univ Dept Elect & Comp Engn Medford MA 02155 USA

In this letter, we characterize the finite-time behavior on arbitrary undirected graphs. In particular, we derive distributed iterations that are a function of a linear operator on the underlying graph and show that any arbitrary initial condition can be forced to lie on a particular subspace in a finite time. This subspace can be chosen to have the same dimension as the algebraic multiplicity of any (arbitrarily chosen) eigenvalue of the underlying linear operator and is spanned by the eigenvectors corresponding to the chosen eigenvalue. In other words, finite-time behavior is completely characterized by the algebraic multiplicity of the eigenvalues and the corresponding eigenvectors of the underlying linear operator. We show that finite-time average-consensus can be cast naturally in this setup for which we further develop the necessary and sufficient conditions.

关键词： Average-consensus distributed algorithms Eigenvalue multiplicity finite-time convergence subspaces

来源：评论

学校读者我要写书评

暂无评论

THE BENEVOLENT BANDIT LABORATORY - A TESTBED FOR distributed algorithms

引用

IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS 1989年第2期7卷 303-311页

作者： FELDERMAN, RE SCHOOLER, EM KLEINROCK, L INFORMAT SCI INST DIV SYSTMARINA DEL REYCA 90292

The design, implementation, and use of a distributed processing environment on a network of IBM PCs running DOS is described. Temporarily unused PCs can be accessed by other users on the network to perform distributed computations. An owner of a PC need not be aware that the machine is being used during idle times; the machine is immediately returned when the owner begins to work again. Some degree of computation resiliency is provided in this unreliable environment; if a PC is part of a distributed algorithm and is reclaimed by its owner, the system finds a replacement node (if possible), resends the affected code to the processor, and restarts it. Thus, a distributed computation is able to proceed despite a set of transient processors. System performance, distributed applications, and fault tolerance are discussed. Performance improvements are demonstrated by applications like parallel merge sort and a distributed search solution to the eight puzzle.< >

关键词： Laboratories Testing distributed algorithms Microcomputers Time sharing computer systems Computer networks distributed computing Local area networks Computer science System performance

来源：评论

学校读者我要写书评

暂无评论

IMSuite: A benchmark suite for simulating distributed algorithms

引用

JOURNAL OF PARALLEL AND distributed COMPUTING 2015年 75卷 1-19页

作者： Gupta, Suyash Nandivada, V. Krishna Indian Inst Technol Dept Comp Sci & Engn PACE Lab Madras 600036 Tamil Nadu India

Considering the diverse nature of real-world distributed applications that makes it hard to identify a representative subset of distributed benchmarks, we focus on their underlying distributed algorithms. We present and characterize a new kernel benchmark suite (named IMSuite) that simulates some of the classical distributed algorithms in task parallel languages. We present multiple variations of our kernels, broadly categorized under two heads: (a) varying synchronization primitives (with and without fine grain synchronization primitives);and (b) varying forms of parallelization (data parallel and recursive task parallel). Our characterization covers interesting aspects of distributed applications such as distribution of remote communication requests, number of synchronization, task creation, task termination and atomic operations. We study the behavior (execution time) of our kernels by varying the problem size, the number of compute threads, and the input configurations. We also present an involved set of input generators and output validators. (C) 2014 Elsevier Inc. All rights reserved.

关键词： Benchmarks. distributed algorithms Performance evaluation Task parallelism Data parallelism Recursive task parallelism

来源：评论

学校读者我要写书评

暂无评论

Nonsmooth Continuous-Time distributed algorithms for Seeking Generalized Nash Equilibria of Noncooperative Games via Digraphs

引用

IEEE TRANSACTIONS ON CYBERNETICS 2022年第7期52卷 6196-6206页

作者： Lu, Kaihong Zhu, Qixin Jiangsu Univ Sch Elect & Informat Engn Zhenjiang 212013 Jiangsu Peoples R China Suzhou Univ Sci & Technol Sch Mech Engn Suzhou 215009 Peoples R China

In this article, the problem of distributed generalized Nash equilibrium (GNE) seeking in noncooperative games is investigated via multiagent networks, where each player aims to minimize his or her own cost function with a nonsmooth term. Each player's cost function and feasible action set in the noncooperative game are both determined by actions of others who may not be neighbors, as well as his/her own action. Particularly, feasible action sets are constrained by private convex inequalities and shared linear equations. Each player can only have access to his or her own cost function, private constraint, and a local block of shared constraints, and can only communicate with his or her neighbours via a digraph. To address this problem, a novel continuous-time distributed primal-dual algorithm involving Clarke's generalized gradient is proposed based on consensus algorithms and the primal-dual algorithm. Under mild assumptions on cost functions and graph, we prove that players' actions asymptotically converge to a GNE. Finally, a simulation is presented to demonstrate the effectiveness of our theoretical results.

关键词： Games Cost function distributed algorithms Mathematical model Consensus algorithm Topology Nash equilibrium distributed algorithm multiagent networks Nash equilibrium (NE) noncooperative game

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：