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

42nd ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC)

作者： Ghaffari, Mohsen Trygub, Anton MIT Cambridge MA 02139 USA

ISBN: (纸本)9798400701214

We provide the first deterministic distributed synchronizer with near-optimal time complexity and message complexity overheads. Concretely, given any distributed algorithm A that has time complexity.. and message complexity.. in the synchronous message-passing model (subject to some care in defining the model), the synchronizer provides a distributed algorithm A' that runs in the asynchronous message-passing model with time complexity T . poly(log n) and message complexity (M + m) . poly(log n). Here, n and m denote the number of nodes and edges in the network, respectively. The synchronizer is deterministic in the sense that if algorithm A is deterministic, then so is algorithm A'. Previously, only a randomized synchronizer with near-optimal overheads was known by seminal results of Awerbuch, Patt-Shamir, Peleg, and Saks [STOC 1992] and Awerbuch and Peleg [FOCS 1990]. We also point out and fix some inaccuracies in these prior works. As concrete applications of our synchronizer, we resolve some longstanding and fundamental open problems in distributed algorithms: we get the first asynchronous deterministic distributed algorithms with near-optimal time and message complexities for leader election, breadth-first search tree, and minimum spanning tree computations: these all have message complexity (O) over tilde (m) message complexity. The former two have (O) over tilde (D) time complexity, where D denotes the network diameter, and the latter has (O) over tilde (D + root n) time complexity. All these bounds are optimal up to logarithmic factors. Previously all such near-optimal algorithms were either restricted to the synchronous setting or required randomization.

关键词： synchronizer asynchronous algorithms distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

Distributed Iterative Solution of Numerical Simulation Problems on Infiniband and Ethernet Clusters via the P2PSAP Self-Adaptive Protocol

Distributed Iterative Solution of Numerical Simulation Probl...

引用

21st Euromicro International Conference on Parallel, Distributed, and Network-Based Processing (PDP)

作者： Tembo, Serge Romaric The Tung Nguyen El-Baz, Didier CNRS LAAS 7 Ave Colonel Roche F-31400 Toulouse France Univ Toulouse 1 LAAS F-31400 Toulouse France

ISBN: (纸本)9780769549392;9781467353212

The distributed iterative solution of numerical simulation problems on Infiniband or Ethernet Clusters via the P2PDC environment is studied. The P2PDC decentralized environment is dedicated to task parallel applications. It has been designed for the solution of large scale numerical simulation problems via distributed iterative algorithms. The P2PDC environment is based on the P2PSAP self-adaptive communication protocol. New functionalities of the P2PSAP communication protocol aimed at using Infiniband clusters are presented. A series of computational results is presented and analyzed.

关键词： distributed computing cluster computing Infiniband micro-protocols task parallel model asynchronous algorithms

来源：评论

学校读者我要写书评

暂无评论

Real-Time PageRank on Dynamic Graphs 23

Real-Time PageRank on Dynamic Graphs

引用

32nd International Symposium on High-Performance Parallel and Distributed Computing (HPDC) part of the ACM Federated Computing Research Conference (FCRC)

作者： Sallinen, Scott Luo, Juntong Ripeanu, Matei Univ British Columbia Vancouver BC Canada

ISBN: (纸本)9798400701559

Modern data generation has grown to enormous proportions, with events occurring at increasingly higher rates. Yet for graph analytics, this growth in scale and velocity has not been matched by improved algorithm or infrastructure techniques: most systems still focus on post-mortem or static analysis. This paper builds on an efficient graph processing abstraction that enables online analysis of dynamically evolving graphs at scale. Integral to this abstraction is that events tied to both graph topology changes as well as algorithmic maintenance occur and are processed asynchronously, concurrently, and autonomously (i.e., without shared state). We offer a case study for online analytics of an evolving graph and make two key contributions: on the one side, we develop an online solution for PageRank. This solution tracks vertices' Page-Rank scores as a graph evolves over time, and quickly converges identically to the result offered by the well-known power iteration method when requested by the user. On the other side, we show that fine-grained temporal analysis of evolving PageRank scores in real-time is feasible. Our approach offers generic applicability, as it: (i) works for directed or undirected graphs, on generic or personalized PageRank, (ii) handles sink vertices correctly, (iii) handles topology changes and complex temporal sliding-window graphs, and (iv) scales to billion edge graphs even on commodity hardware.

关键词： graph processing asynchronous algorithms dynamic graphs

来源：评论

学校读者我要写书评

暂无评论

PRIVACY-PRESERVING DISTRIBUTED OPTIMISATION USING STOCHASTIC PDMM 49

PRIVACY-PRESERVING DISTRIBUTED OPTIMISATION USING STOCHASTIC...

引用

49th IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP)

作者： Jordan, Sebastian O. Li, Qiongxiu Heusdens, Richard Delft Univ Technol Delft Netherlands Tsinghua Univ Beijing Peoples R China Netherlands Def Acad Breda Netherlands

ISBN: (纸本)9798350344868;9798350344851

Privacy-preserving distributed processing has received considerable attention recently. The main purpose of these algorithms is to solve certain signal processing tasks over a network in a decentralised fashion without revealing private/secret data to the outside world. Because of the iterative nature of these distributed algorithms, computationally complex approaches such as (homomorphic) encryption are undesired. Recently, an information theoretic method called subspace perturbation has been introduced for synchronous update schemes. The main idea is to exploit a certain structure in the update equations for noise insertion such that the private data is protected without compromising the algorithm's accuracy. This structure, however, is absent in asynchronous update schemes. In this paper we will investigate such asynchronous schemes and derive a lower bound on the noise variance after random initialisation of the algorithm. This bound shows that the privacy level of asynchronous schemes is always better than or at least equal to that of synchronous schemes. Computer simulations are conducted to consolidate our theoretical results.

关键词： Privacy distributed optimisation convex optimisation PDMM asynchronous algorithms

来源：评论

学校读者我要写书评

暂无评论

Secure clock synchronization under collusion attacks

Secure clock synchronization under collusion attacks

引用

54th Annual Allerton Conference on Communication, Control, and Computing (Allerton)

作者： Duan, Xiaoming Freris, Nikolaos M. Cheng, Peng Zhejiang Univ State Key Lab Ind Control Technol Hangzhou Zhejiang Peoples R China New York Univ Abu Dhabi POB 129188 Abu Dhabi U Arab Emirates

ISBN: (纸本)9781509045501

Recently, the Secure Average Time Synchronization (SATS) protocol has been proposed and analyzed;this distributed clock synchronization protocol is capable of successfully tackling several attacks such as denial-of-service (DoS), message-delay, message duplication/repetition, and even a generic message manipulation. However, the collusion attack, in which neighboring malicious nodes may cooperate so as to strike stealthier attacks that are more difficult to handle, remains by and large an open problem. In the setup of SATS, we derive the fundamental asymptotic bounds in the number of malicious agents-as function of the benign ones-that can be efficiently handled without tampering accurate network-wide synchronization. Going a step further, we develop a risk model for collusions and use it to obtain even tighter bounds. In specific, we establish that SATS can handle 'many' malicious nodes with high probability: an order of almost square-root of the benign ones for the case of no risk, and almost linear when the risk of collusion is accounted. Last but not least, we analyze and experimentally assess an interesting phenomenon: the presence of attackers may lead to a convergence speedup of SATS, since malicious nodes can be effectively constrained from the network, thus affecting the algebraic connectivity of the graph corresponding to the network topology. Numerical simulations verify the theoretical results, i.e., collusions are avoided when the number of malicious nodes is bounded by the asymptotic bounds and the algebraic connectivity increases due to incorporating 'well behaved' malicious nodes.

关键词： Cybersecurity Clock synchronization Collusion attacks Cyberphysical systems Wireless sensor networks Distributed systems asynchronous algorithms Asymptotic analysis Fundamental limits

来源：评论

学校读者我要写书评

暂无评论

The Impact of Asynchrony on Parallel Model-Based EAs 23

The Impact of Asynchrony on Parallel Model-Based EAs

引用

Genetic and Evolutionary Computation Conference (GECCO)

作者： Guijt, Arthur Thierens, Dirk Alderliesten, Tanja Bosman, Peter A. N. Ctr Wiskunde & Informat Amsterdam Netherlands Univ Utrecht Utrecht Netherlands Leiden Univ Med Ctr Leiden Netherlands Delft Univ Technol Delft Netherlands

ISBN: (纸本)9798400701191

In a parallel EA one can strictly adhere to the generational clock, and wait for all evaluations in a generation to be done. However, this idle time limits the throughput of the algorithm and wastes computational resources. Alternatively, an EA can be made asynchronous parallel. However, EAs using classic recombination and selection operators (GAs) are known to suffer from an evaluation time bias, which also influences the performance of the approach. Model-Based Evolutionary algorithms (MBEAs) are more scalable than classic GAs by virtue of capturing the structure of a problem in a model. If this model is learned through linkage learning based on the population, the learned model may also capture biases. Thus, if an asynchronous parallel MBEA is also affected by an evaluation time bias, this could result in learned models to be less suited to solving the problem, reducing performance. Therefore, in this work, we study the impact and presence of evaluation time biases on MBEAs in an asynchronous parallelization setting, and compare this to the biases in GAs. We find that a modern MBEA, GOMEA, is unaffected by evaluation time biases, while the more classical MBEA, ECGA, is affected, much like GAs are.

关键词： Genetic algorithms Model-Based Evolutionary algorithms Linkage Learning Parallel algorithms asynchronous algorithms

来源：评论

学校读者我要写书评

暂无评论

Convergence of Stochastic PDMM 48

Convergence of Stochastic PDMM

引用

48th IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2023

作者： Jordan, Sebastian O. Sherson, Thomas W. Heusdens, Richard Delft University of Technology Netherlands Netherlands Defence Academy Netherlands

ISBN: (纸本)9781728163277

In recent years, the large increase in connected devices and the data that are collected by these devices have caused a heightened interest in distributed processing. Many practical distributed networks are of heterogeneous nature, because different devices in the network can have different specifications. Because of this, it is highly desirable that algorithms operating within these networks can operate asynchronously, since in that case there is no need for clock synchronisation between the nodes, and the algorithm is not slowed down by the slowest device in the network. In this paper, we focus on the primal-dual method of multipliers (PDMM), which is a promising distributed optimisation algorithm that is suitable for distributed optimisation in heterogeneous networks. Most theoretical work that can be found in existing literature focuses on synchronous versions of PDMM. In this work, we prove the convergence of stochastic PDMM, which is a general framework that can model variations such as asynchronous PDMM and PDMM with transmission losses. © 2023 IEEE.

关键词： asynchronous algorithms convex optimisation distributed optimisation PDMM transmission loss

来源：评论

学校读者我要写书评

暂无评论

asynchronous parallel nonconvex large-scale optimization

Asynchronous parallel nonconvex large-scale optimization

引用

IEEE International Conference on Acoustics, Speech and Signal Processing

作者： L. Cannelli F. Facchinei V. Kungurtsev G. Scutari School of Industrial Engineering Purdue University USA Dept. of Computer Control and Management Engineering University of Rome "La Sapienza" Italy Agent Technology Center Czech Technical University in Prague Czech Republic

ISBN: (纸本)9781509041183

We propose a novel parallel asynchronous algorithmic framework for the minimization of the sum of a smooth (nonconvex) function and a convex (nonsmooth) regularizer. The framework hinges on Successive Convex Approximation (SCA) techniques and on a novel probabilistic model which describes in a unified way a variety of asynchronous settings in a more faithful and exhaustive way with respect to state-of-the-art models. Key features of our framework are: i) it accommodates inconsistent read, meaning that components of the variables may be written by some cores while being simultaneously read by others;ii) it covers in a unified way several existing methods;and iii) it accommodates a variety of parallel computing architectures. Almost sure convergence to stationary solutions is proved for the general case, and iteration complexity analysis is given for a specific version of our model. Numerical results show that our scheme outperforms existing asynchronous ones.

关键词： asynchronous algorithms big-data inconsistent read nonconvex constrained optimization asynchronous Constrained optimization Probabilistic Model Frameworks PARALLEL PROCESSING (COMPUTERS) Parallel Lines Road Convexity core

来源：评论

学校读者我要写书评

暂无评论

Fast Decentralized Data Analytics in IoT Wireless Networks

引用

IEEE ACCESS 2019年 7卷 181531-181545页

作者： Zhao, Liang Univ South Carolina Upstate Div Math & Comp Sci Spartanburg SC 29303 USA

This paper presents an innovative mechanism for decentralized data analytics in the Internet of Things (IoT) networks. In contrast to traditional centralized (eg. Cloud) based solution, our proposed decentralized framework can avoid the problems raised in data collection such as the constraint in high latency, and the associated data breach and privacy issues. The invented mechanism enables each IoT node in the network to independently obtain the global optimal analytics with local computation and communication. The proposed framework has been tested in seismic imaging and machine learning applications. The evaluation results validate its fast convergence to the optimal model, and demonstrates that it allows (near) real-time data analytics in IoT networks under bandwidth and energy limitation, particularly in uncertain and dynamic environments.

关键词： asynchronous algorithms decentralized data analytics Internet of Things

来源：评论

学校读者我要写书评

暂无评论

Parallel Block-iterative Methods: Application to the Load Flow Problem

引用

IFAC Proceedings Volumes 1989年第10期22卷 339-344页

作者： A. Bhaya D.M. Falcāo E. Kaszkurewicz N. Roqueiro COPPE/UFRJ. Rio de Janeiro Federal University. Electrical Engineering Department. P.O. Box 68504. 21945 Rio de Janeiro. RJ. Brazil

This paper describes the use of asynchronous parallel block-iterative methods for the solution of large systems of linear algebraic equations arising in the analysis of the load-flow problem of clectrical power networks. The emphasis is on studying the effect of the number of partitions and asynchronism on total computational time. Results are presented on the speedup of the asynchronous parallel algorithms with respect to the best, serial algorithm of the same type run on one node The computer used is a 2 crate ACP multiprocessor (Advanced Computer Program. Fermilab) with ten processors (68020 μPs) per crate.

关键词： asynchronous algorithms convergence of numerical methods iterative methods load flow problem nonlinear equations parallel processing

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：