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

Statistical properties of a class of randomized binary search algorithms

PERFORMANCE EVALUATION 2025年 168卷

作者： Xia, Ye Univ Florida Dept Comp & Informat Sci & Engn Gainesville FL 32611 USA

In this paper, we analyze the statistical properties of a randomized binary search algorithm and its variants. These algorithms have applications in caching and load balancing in distributed environments such as peer-to-peer networks, cloud storage, data centers, and content distribution networks. The basic discrete version of the problem is as follows. Suppose there are m servers, numbered 1, 2, ... , m, out of which the first k servers are marked as special, where k is unknown. These k servers may contain a particular file or service that clients want. The objective is to select one of the marked servers uniformly at random. Considering the intended applications, we impose the constraint that there is no central controller to facilitate the selection process. We start with a basic algorithm: In each step, the client requesting the service chooses a number y uniformly at random from 1, 2, ... , x, where x is the number chosen in the previous step, initially set to m in the first step. A query is then sent to server y asking whether y is marked. If the answer is yes, the algorithm returns y;otherwise, the process is repeated with x <- y. In this paper, we primarily consider two batch versions of this algorithm in which multiple numbers are chosen in each step and multiple queries are made in parallel. We derive the mean and variance (exact and/or asymptotic) for the number of search steps in each version of the algorithm, and when possible, we give its distribution. Additionally, we analyze the access pattern of queries across the entire search space.

关键词： Analysis of algorithms parallel and distributed algorithms Randomized binary search algorithm distributed search Load balancing

来源：评论

学校读者我要写书评

暂无评论

Novel Control Approaches for Demand Response With Real-Time Pricing Using parallel and distributed Consensus-Based ADMM

引用

IEEE TRANSACTIONS ON INDUSTRIAL ELECTRONICS 2019年第10期66卷 7935-7945页

作者： Dinh Hoa Nguyen Azuma, Shun-Ichi Sugie, Toshiharu Kyushu Univ Int Inst Carbon Neutral Energy Res Fukuoka Fukuoka 8190395 Japan Kyushu Univ Inst Math Ind Fukuoka Fukuoka 8190395 Japan Nagoya Univ Grad Sch Engn Dept Mech Syst Engn Nagoya Aichi 4648603 Japan Kyoto Univ Grad Sch Informat Dept Syst Sci Kyoto 6068501 Japan

This paper studies the automated demand response (DR) problem in smart grids equipped with information and communication technology networks, where power generating and consuming units can exchange information as a multiagent system (MAS), and a real-time pricing (RTP) scheme is proposed. When the communication graph among agents is connected, a novel parallel and distributed consensus-based algorithm is proposed to derive an RTP scheme to facilitate DR, and when communication uncertainties exist, a robust consensus algorithm is proposed to cease the effect of uncertainties. Next, this paper proposes a novel control mechanism to tackle the problem of disconnected communication among agents, e.g., under cyber-attacks, by employing the so-called mixed communication-broadcast control architecture where the underlying ideas are twofold. First, each area in the grid associated with a connected subgraph is controlled by a MAS to guarantee the power balance and to reach consensus on the local electric price for that area. Second, a supervisory unit observes those local electric prices to calculate the global electric price for the whole grid and then broadcasts to all units so that they can properly adjust their output powers. Simulations are carried out on the IEEE 39-bus system to validate the proposed control mechanisms.

关键词： Alternating direction method of multipliers (ADMM) communication failure demand response (DR) mixed communication-broadcast multiagent system (MAS) parallel and distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

A Comparative Study of Four parallel and distributed PSO Methods

引用

NEW GENERATION COMPUTING 2011年第2期29卷 129-161页

作者： Vanneschi, Leonardo Godecasa, Daniele Mauri, Giancarlo Univ Milano Bicocca Dept Informat Syst & Commun DISCo I-20126 Milan Italy

We present four new parallel and distributed particle swarm optimization methods consisting in a genetic algorithm whose individuals are co-evolving swarms, an "island model"-based multi-swarm system, where swarms are independent and interact by means of particle migrations at regular time steps, and their respective variants enriched by adding a repulsive component to the particles. We study the proposed methods on a wide set of problems including theoretically hand-tailored benchmarks and complex real-life applications from the field of drug discovery, with a particular focus on the generalization ability of the obtained solutions. We show that the proposed repulsive multi-swarm system has a better optimization ability than all the other presented methods on all the studied problems. Interestingly, the proposed repulsive multi-swarm system is also the one that returns the most general solutions.

关键词： Optimization Swarm Intelligence parallel and distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

parallel and distributed Invariant Checking of Microcontroller Software

引用

ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE 2009年 254卷 45-63页

作者： Brauer, Joerg Schlich, Bastian Kowalewski, Stefan Rhein Westfal TH Aachen Embedded Software Lab Aachen Germany

Formal verification techniques are recognized as promising tools for the development of embedded systems. One such technique is invariant checking, which can be applied intuitively by developers as it does not require knowledge of temporal logics. State spaces for invariant checking are built using the same methods as used for model checking. They can become large due to the stateexplosion problem. In [mc] square, which is a model checker for microcontroller programs, most of the time is spent building state spaces when checking programs. To improve the performance of [mc] square, we have implemented four parallel and one distributed algorithm for invariant checking. parallel algorithms are especially helpful as they allow to fully utilize multi-core CPUs. This paper describes several parallel and distributed algorithms and presents a case study that compares these algorithms and shows the performance improvements achieved.

关键词： Embedded Software Verification Assembly Code Invariant Checking parallel and distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

Robust Federated Learning With Noisy Labeled Data Through Loss Function Correction

引用

IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING 2023年第3期10卷 1501-1511页

作者： Chen, Li Ang, Fan Chen, Yunfei Wang, Weidong Univ Sci & Technol China Dept Elect Engn & Informat Sci Hefei 230027 Anhui Peoples R China Univ Warwick Sch Engn Coventry CV4 7AL England

Federated learning (FL) is a communication efficient machine learning paradigm to leverage distributed data at the network edge. Nevertheless, FL usually fails to train a high-quality model from the networks, where the edge nodes collect noisy labeled data. To tackle this challenge, this paper focuses on developing an innovative robust FL. We consider two kinds of networks with different data distribution. Firstly, we design a reweighted FL under a full-data network, where all edge nodes are equipped with both numerous noisy labeled dataset and small clean dataset. The key idea is that edge devices learn to assign the local weights of loss functions in noisy labeled dataset, and cooperate with central server to update global weights. Secondly, we consider a part-data network where some edge nodes exclude clean dataset, and can not compute the weights locally. The broadcasting of the global weights is added to help those edge nodes without clean dataset to reweight their noisy loss functions. Both designs have a convergence rate of O(1=T-2). Simulation results illustrate that the both proposed training processes improve the prediction accuracy due to the proper weights assignments of noisy loss function.

关键词： Noise measurement Training Servers Data models Federated learning Loss measurement Convergence distributed networks federated learning label noise machine learning non-convex optimization parallel and distributed algorithms robust design

来源：评论

学校读者我要写书评

暂无评论

Locating and computing in parallel all the simple roots of special functions using PVM

引用

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS 2001年第1-2期133卷 545-554页

作者： Plagianakos, VP Nousis, NK Vrahatis, MN Univ Patras Dept Math UPAIRC GR-26500 Patras Greece

An algorithm is proposed for locating and computing in parallel and with certainty all the simple roots of any twice continuously differentiable function in any specific interval. To compute with certainty all the roots, the proposed method is heavily based on the knowledge of the total number of roots within the given interval. To obtain this information we use results from topological degree theory and, in particular, the Kronecker-Picard approach. This theory gives a formula for the computation of the total number of roots of a system of equations within a given region, which can be computed in parallel, With this tool in hand, we construct a parallel procedure for the localization and isolation of all the roots by dividing the given region successively and applying the above formula to these subregions until the final domains contain at the most one root. The subregions with no roots are discarded, while for the rest a modification of the well-known bisection method is employed for the computation of the contained root. The new aspect of the present contribution is that the computation of the total number of zeros using the Kronecker-Picard integral as well as the localization and computation of all the roots is performed in parallel using the parallel virtual machine (PVM). PVM is an integrated set of software tools and libraries that emulates a general-purpose, flexible, heterogeneous concurrent computing framework on interconnected computers of varied architectures. The proposed algorithm has large granularity and low synchronization, and is robust. It has been implemented and tested and our experience is that it can massively compute with certainty all the roots in a certain interval. Performance information from massive computations related to a recently proposed conjecture due to Elbert (this issue, J. Comput. Appl. Math. 133 (2001) 65-83) is reported. (C) 2001 Elsevier Science B.V. All rights reserved.

关键词： Elbert's conjecture special functions Bessel functions computation of special functions construction of tables of special functions parallel and distributed algorithms parallel virtual machine zero isolation Kronecker-Picard theory topological degree theory computing simple roots bisection method

来源：评论

学校读者我要写书评

暂无评论

CoCoA: A General Framework for Communication-Efficient distributed Optimization

引用

JOURNAL OF MACHINE LEARNING RESEARCH 2018年第154期18卷 1-49页

作者： Smith, Virginia Forte, Simone Ma, Chenxin Takac, Martin Jordan, Michael I. Jaggi, Martin Stanford Univ Dept Comp Sci Stanford CA 94305 USA Swiss Fed Inst Technol Dept Comp Sci CH-8006 Zurich Switzerland Lehigh Univ Ind & Syst Engn Dept Bethlehem PA 18015 USA Univ Calif Berkeley Div Comp Sci Berkeley CA 94720 USA Univ Calif Berkeley Dept Stat Berkeley CA 94720 USA Ecole Polytech Fed Lausanne Sch Comp & Commun Sci CH-1015 Lausanne Switzerland

The scale of modern datasets necessitates the development of efficient distributed optimization methods for machine learning. We present a general-purpose framework for distributed computing environments, CoCoA, that has an efficient communication scheme and is applicable to a wide variety of problems in machine learning and signal processing. We extend the framework to cover general non-strongly-convex regularizers, including L1-regularized problems like lasso, sparse logistic regression, and elastic net regularization, and show how earlier work can be derived as a special case. We provide convergence guarantees for the class of convex regularized loss minimization objectives, leveraging a novel approach in handling non-strongly-convex regularizers and non-smooth loss functions. The resulting framework has markedly improved performance over state-of-the-art methods, as we illustrate with an extensive set of experiments on real distributed datasets.

关键词： Convex optimization distributed systems large-scale machine learning parallel and distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

Scheduling Policies for Federated Learning in Wireless Networks

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2020年第1期68卷 317-333页

作者： Yang, Howard H. Liu, Zuozhu Quek, Tony Q. S. Poor, H. Vincent Singapore Univ Technol & Design Informat Syst Technol & Design Pillar Singapore 487372 Singapore Natl Univ Singapore Dept Stat & Appl Probabil Singapore 119077 Singapore Princeton Univ Dept Elect Engn Princeton NJ 08544 USA

Motivated by the increasing computational capacity of wireless user equipments (UEs), e.g., smart phones, tablets, or vehicles, as well as the increasing concerns about sharing private data, a new machine learning model has emerged, namely federated learning (FL), that allows a decoupling of data acquisition and computation at the central unit. Unlike centralized learning taking place in a data center, FL usually operates in a wireless edge network where the communication medium is resource-constrained and unreliable. Due to limited bandwidth, only a portion of UEs can be scheduled for updates at each iteration. Due to the shared nature of the wireless medium, transmissions are subjected to interference and are not guaranteed. The performance of FL system in such a setting is not well understood. In this paper, an analytical model is developed to characterize the performance of FL in wireless networks. Particularly, tractable expressions are derived for the convergence rate of FL in a wireless setting, accounting for effects from both scheduling schemes and inter-cell interference. Using the developed analysis, the effectiveness of three different scheduling policies, i.e., random scheduling (RS), round robin (RR), and proportional fair (PF), are compared in terms of FL convergence rate. It is shown that running FL with PF outperforms RS and RR if the network is operating under a high signal-to-interference-plus-noise ratio (SINR) threshold, while RR is more preferable when the SINR threshold is low. Moreover, the FL convergence rate decreases rapidly as the SINR threshold increases, thus confirming the importance of compression and quantization of the update parameters. The analysis also reveals a trade-off between the number of scheduled UEs and subchannel bandwidth under a fixed amount of available spectrum.

关键词： Convergence Data models Signal to noise ratio Interference Computational modeling Training Wireless networks Federated learning scheduling policies parallel and distributed algorithms stochastic geometry convergence analysis

来源：评论

学校读者我要写书评

暂无评论

Training efficiency optimization algorithm of wireless federated learning based on processor performance and network condition awareness

引用

EURASIP JOURNAL ON ADVANCES IN SIGNAL PROCESSING 2024年第1期2024卷 98页

作者： Pang, Guohao Zhu, Xiaorong Nanjing Univ Posts & Telecommun Coll Portland Nanjing 210003 Peoples R China Nanjing Univ Posts & Telecommun Coll Telecommun & Informat Engn Nanjing 210003 Peoples R China

With the explosive growth of smart mobile devices in wireless networks, the increasing computational power of mobile chips and the growing concern for personal privacy, a decentralized deep learning framework at the mobile terminal layer has emerged called federated learning (FL) to enhance user experience. This paper studies the training efficiency optimization problem of wireless FL that jointly considers processor performance, channel conditions and terminals' power in a non-independent identically distribution (non-IID) scenario. And, the training efficiency optimization problem is mathematically modeled and then decomposed into several sub-problems based on the independence and decoupling of the variables involved. To enhance the training efficiency of wireless FL, a comprehensive scheduling strategy encompassing computational and communication aspects is proposed. Simulation results show that the proposed scheduling strategy for wireless FL achieves superior learning performance with reduced training latency.

关键词： Federated learning Wireless communication Scheduling policies parallel and distributed algorithms Resource allocation

来源：评论

学校读者我要写书评

暂无评论

distributed Strategies for Mining Outliers in Large Data Sets

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2013年第7期25卷 1520-1532页

作者： Angiulli, Fabrizio Basta, Stefano Lodi, Stefano Sartori, Claudio Univ Calabria DIMES Dept I-87036 Arcavacata Di Rende CS Italy Italian Natl Res Council Inst High Performance Comp & Networking I-87036 Arcavacata Di Rende CS Italy Univ Bologna Dept Comp Sci & Engn I-40136 Bologna Italy

We introduce a distributed method for detecting distance-based outliers in very large data sets. Our approach is based on the concept of outlier detection solving set [2], which is a small subset of the data set that can be also employed for predicting novel outliers. The method exploits parallel computation in order to obtain vast time savings. Indeed, beyond preserving the correctness of the result, the proposed schema exhibits excellent performances. From the theoretical point of view, for common settings, the temporal cost of our algorithm is expected to be at least three orders of magnitude faster than the classical nested-loop like approach to detect outliers. Experimental results show that the algorithm is efficient and that its running time scales quite well for an increasing number of nodes. We discuss also a variant of the basic strategy which reduces the amount of data to be transferred in order to improve both the communication cost and the overall runtime. Importantly, the solving set computed by our approach in a distributed environment has the same quality as that produced by the corresponding centralized method.

关键词： Distance-based outliers outlier detection parallel and distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：