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

38th ACM Symposium on Principles of distributed Computing (PODC)

作者： Parter, Merav Yogev, Eylon Weizmann Inst Sci Rehovot Israel Technion Haifa Israel

ISBN: (纸本)9781450362177

In this paper, we study secure distributed algorithms that are nearly optimal, with respect to running time, for the given input graph G. Roughly speaking, an algorithm is secure if the nodes learn only their final output while gaining no information on the input (or output) of other nodes. A graph theoretic framework for secure distributed computation was recently introduced by the authors (SODA 2019). This framework is quite general and it is based on a new combinatorial structure called private neighborhood trees: a collection of n trees T (u(1)), ... , T (u(n)) such that each tree T (u(i)) spans the neighbors of ui without going through ui. Intuitively, each tree T (u(i)) allows all neighbors of ui to exchange a secret that is hidden from ui. The efficiency of the framework depends on two key parameters of these trees: their depth and the amount of overlap. In a (d, c)-private neighborhood trees each tree T (u(i)) has depth O(d) and each edge e is an element of G appears in at most O(c) different trees. An existentially optimal construction of private neighborhood trees with d = O(Delta center dot D) and c = (O) over tilde (D) was1 presented therein. We make two key contributions: Universally Optimal Private Trees: We show a combinatorial construction of nearly (universally) optimal (d, c)-private neighborhood trees with d + c = (O) over tilde (OPT(G)) for any input graph G. Perhaps surprisingly, we show that OPT(G) is equal to the best depth possible for these trees even without the congestion constraint. We also present efficient distributed constructions of these private trees. Optimal Secure Computation: Using the optimal constructions above, we get a secure compiler for distributed algorithms where the overhead for each round is (O) over tilde (poly(Delta) center dot OPT(G)). As our second key contribution, we design an optimal compiler with an overhead of merely (O) over tilde (OPT(G)) per round for a class of "simple" algorithms. This class includes many

关键词： distributed algorithms multi-party computation private neighborhood trees secure computation

来源：评论

学校读者我要写书评

暂无评论

Locality of distributed Graph Problems

Locality of Distributed Graph Problems

引用

作者： Chang, Yi-Jun University of Michigan

学位级别：Ph.D.

Locality is one of the central themes in distributed computing. Suppose in a network each node only has direct communication with its local neighbors, how efficiently can a global task be solved? We aim to investigate the locality of fundamental distributed graph problems. Toward this goal, we consider the following three basic abstract models of distributed computing. • LOCAL: each device has direct communication links with its neighbors, there is no message size constraint. • CONGEST: each device has direct communication links with its neighbors, the size of each message is at most O(log n) bits. • CONGESTED-CLIQUE: each device has direct communication links with all other devices, the size of each message is at most O(log n) bits. A brief summary of our results is as follows. 1. Complexity Theory for the LOCAL Model: We study the spectrum of natural problem complexities that can exist in the LOCAL model. We provide answers to the following fundamental questions regarding the nature of the LOCAL model: (i) How to classify the distributed problems according to their complexities? (ii) How much does randomness help? (iii) Can we solve more problems given more time? 2. Complexity of distributed Coloring: The coloring problem is a classical and well-studied problem in distributed computing. We devise distributed algorithms for the edge-coloring problem and the vertex-coloring problem in the LOCAL model that improve upon the previous state of the art. 3. Bandwidth Constraint: We develop a new framework for algorithm design based on expander decompositions that allows us to apply CONGESTED-CLIQUE techniques to the CONGEST model. Using this approach, we provide improved algorithms for the triangle detection and enumeration problem in CONGEST.

关键词： distributed algorithms local model locally checkable labeling coloring Thesis

来源：评论

学校读者我要写书评

暂无评论

Probabilistic Joint State Estimation for Operational Planning

引用

IEEE TRANSACTIONS ON SMART GRID 2019年第1期10卷 601-612页

作者： Weng, Yang Negi, Rohit Ilic, Marija D. Arizona State Univ Sch Elect Comp & Energy Engn Tempe AZ 85281 USA Carnegie Mellon Univ Dept Elect & Comp Engn Pittsburgh PA 15213 USA

Due to a high penetration of renewable energy, power systems operational planning today needs to capture unprecedented uncertainties in a short period. Fast probabilistic state estimation (SE), which creates probabilistic load flow estimates, represents one such planning tool. This paper describes a graphical model for probabilistic SE modeling that captures both the uncertainties and the power grid via embedding physical laws, i.e., KCL and KVL. With such a modeling, the resulting maximum a posteriori (MAP) SE problem is formulated by measuring state variables and their interactions. To resolve the computational difficulty in calculating the marginal distribution for interested quantities, a distributed message passing method is proposed to compute MAP estimates using increasingly available cyber resources, i.e., computational and communication intelligence. A modified message passing algorithm is then introduced to improve the convergence and optimality. Simulation results illustrate the probabilistic SE and demonstrate the improved performance over traditional deterministic approaches via: 1) the more accuracy mean estimate;2) the confidence interval covering the true state;and 3) the reduced computational time.

关键词： Renewable penetration operational planning probabilistic state estimation graphical model distributed algorithms message passing

来源：评论

学校读者我要写书评

暂无评论

Decentralised optimal dispatch of multi-area power systems based on non-linear value-function approximation

引用

IET GENERATION TRANSMISSION & DISTRIBUTION 2019年第22期13卷 5083-5090页

作者： Zhu, Jianquan Zhu, Tao Liu, Mingbo Lu, Wentian South China Univ Technol Sch Elect Power Engn Guangzhou 510640 Guangdong Peoples R China Guangdong Power Exchange Ctr Guangzhou 510000 Peoples R China

In recent years, the use of interconnected multi-area systems has increased significantly. To operate these systems efficiently, a proper coordination approach among different areas is required. With this context, a novel decentralised optimal dispatch algorithm is proposed in this study. The centralised economic dispatch model is decoupled into a series of sub-problems for different areas, allowing the independent decision of each area without a central operator. The detailed information of each area is not required for information exchange. To better estimate the impact of each area's decision on other areas, the approximate value functions of the tie-line powers are added into the local objective function of the sub-problem. This technique makes the decentralised solution of the proposed algorithm more explicit and rational compared with most existing distributed algorithms. Besides, the proposed technique does not require parameter tuning and has good convergence performance. Numerical simulations on several test systems and a real power system demonstrate that the proposed algorithm is favourable in terms of accuracy, adaptability, and computational efficiency.

关键词： function approximation power generation economics power generation dispatch distributed algorithms information exchange approximate value functions tie-line powers local objective function decentralised optimal dispatch multiarea power systems nonlinear value-function approximation interconnected multiarea systems optimal dispatch algorithm centralised economic dispatch model convergence performance numerical simulations

来源：评论

学校读者我要写书评

暂无评论

A Metropolis-Hastings Algorithm for Task Allocation

A Metropolis-Hastings Algorithm for Task Allocation

引用

IEEE Conference on Decision and Control

作者： Doha Hamza Sarah Toonsi Jeff S. Shamma CEMSE division King Abdullah University of Science and Technology (KAUST) Thuwal KSA Industrial and Enterprise Systems Engineering (ISE) University of Illinois Urbana-Champaign Illinois USA

ISBN: (纸本)9781665436601

We consider a robot-location assignment problem. The problem is confounded by a location network that restricts robots’ motion to neighboring locations. The problem can be optimally solved using a centralized Hungarian algorithm. We propose a distributed game-theoretic algorithm, based on the Metropolis-Hastings mechanism, to eliminate the need for a central coordinator. Agents are activated at random. Agents compare their action, location, against a neighboring one based on the location network. If the new location represents an improvement in agent’s utility, they move with probability one, otherwise, they move with a probability proportional to the difference in the two locations’ utilities. Our algorithm converges to the optimal assignment of robots to locations. We provide extensive simulations, compare with previous work, and demonstrate the versatility of the proposed algorithm to various task allocation scenarios.

关键词： Robot motion Robot kinematics Conferences Resource management Task analysis distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

distributed Aggregation over Homomorphically Encrypted Data under Switching Networks

Distributed Aggregation over Homomorphically Encrypted Data ...

引用

IEEE Conference on Decision and Control

作者： Donggil Lee Junsoo Kim Hyungbo Shim ASRI Seoul National University Korea

ISBN: (数字)9781728174471

ISBN: (纸本)9781728174488

This paper presents a distributed algorithm for additive aggregation over encrypted data. Our algorithm allows networked systems to compute the sum of all individual data without revealing each node's private contribution. To conceal the private data, the local computations on each node and the communications with neighbor nodes are conducted by utilizing the additively homomorphic cryptosystem. As a consequence, the leader node which has the secret key of the cryptosystem recovers the correct outcome after decryption in a finite time. Moreover, the leader cannot learn the private data of the other nodes. Furthermore, the proposed algorithm can operate on encrypted data for an infinite time horizon even when the network varies intermittently with time.

关键词： Cryptography Encryption distributed databases Additives Protocols Public key cryptography distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

Communication and location discovery in geometric ring networks

引用

INFORMATION AND COMPUTATION 2019年 266卷 19-48页

作者： Gasieniec, Leszek Jurdzinski, Tomasz Martin, Russell Stachowiak, Grzegorz Univ Liverpool Dept Comp Sci Ashton BldgAshton St Liverpool L69 3BX Merseyside England Univ Wroclaw Inst Comp Sci Przesmyckiego 20 PL-50383 Wroclaw Poland

We study a distributed coordination mechanism for uniform agents located on a circle. The agents perform their actions in synchronized rounds. At the beginning of each round an agent chooses the direction of its movement from clockwise, anticlockwise, or idle, and moves at unit speed during this round. Agents are not allowed to overpass, i.e., when an agent collides with another it instantly starts moving with the same speed in the opposite direction (without exchanging any information with the other agent). However, at the end of each round each agent has access to limited information regarding its trajectory of movement during this round. We assume that n mobile agents are initially located on a circle unit circumference at arbitrary but distinct positions unknown to other agents. The agents are equipped with unique identifiers from a fixed range. The location discovery task to be performed by each agent is to determine the initial position of every other agent. Our main result states that, if the only available information about movement in a round is limited to distance between the initial and the final position, then there is a superlinear lower bound on time needed to solve the location discovery problem. Interestingly, this result corresponds to a combinatorial symmetry breaking problem, which might be of independent interest. If, on the other hand, an agent has access to the distance to its first collision with another agent in a round, we design an asymptotically efficient and close to optimal solution for the location discovery problem. Assuming that agents are anonymous (there are no IDs distinguishing them), our solution applied to randomly chosen IDs from appropriately chosen range gives an (almost) optimal algorithm, improving upon the complexity of previous randomized results. (C) 2018 Published by Elsevier Inc.

关键词： Mobile robots distributed algorithms Location discovery Boundary patrolling Combinatorial structures

来源：评论

学校读者我要写书评

暂无评论

Decentralized Auctioneerless Combinatorial Auctions for Multi-Unit Resource Allocation

引用

IEEE ACCESS 2019年 7卷 78625-78639页

作者： Yen, Li-Hsing Sun, Guang-Hong Natl Chiao Tung Univ Coll Comp Sci Dept Comp Sci Hsinchu 300 Taiwan

Auction has been used to allocate resources or tasks to processes, machines, or other autonomous agents in distributed systems. Among various types of auctions, combinatorial auction (CA) allocates a bundle of items to each agent at once. Finding an optimal auction result for CA that maximizes total winning bid is NP-hard. Many time-efficient approximations to this problem work with a bid ranking function (BRF). However, the existing approximations are mostly for single-unit resource and demand an auctioneer. This paper proposes the first auctioneerless open-bid multi-unit CA (MUCA) scheme. It includes a BRF-based winner determination scheme that enables every agent to locally compute a critical bid value for it to win the MUCA and accordingly take its best response to other agent's bid and win declarations. It also allows each winner to locally compute its payment for a critical-value-based pricing scheme. We analyze stabilization, correctness, and consistency properties of the proposed approach. The simulation results confirm that the proposed approach identifies exactly the same set of winners as the centralized counterpart regardless of initial bid setting, but at the cost of the lower total winning bid and payment.

关键词： distributed algorithms resource management combinatorial auctions resource allocation game theory

来源：评论

学校读者我要写书评

暂无评论

Diffusion Variable Step Size Algorithm Based on Maximum Correntropy Criterion

Diffusion Variable Step Size Algorithm Based on Maximum Corr...

引用

Power Electronics, Computer Applications (ICPECA), IEEE International Conference on

作者： Lin Yun Hu Xiaobin Gao Qianqian College of Communication and Information Engineering Chongqing University of Posts and Telecommunications Chongqing China

ISBN: (数字)9781728190044

ISBN: (纸本)9781728190051

As a new kind of method using localized similarity measure by kernel function, maximum correntropy criterion has the better performance in the environment of non-Gaussian noise. And in order to accelerate the convergence speed of the algorithm, this paper introduces a variable step size method inspired by maximum correntropy criterion, proposes a variable step size distributed algorithm based on maximum correlation criterion (VSS-DMCC). Simulation results show that our algorithm has smaller steady-state error and faster convergence speed than the minimum mean square variable step size distributed algorithm (VSS-DLMS) and maximum correntropy criterion distributed algorithm (DMCC).

关键词： Correlation Simulation Entropy Steady-state Kernel distributed algorithms Convergence

来源：评论

学校读者我要写书评

暂无评论

distributed Community Detection on Overlapping Stochastic Block Model

Distributed Community Detection on Overlapping Stochastic Bl...

引用

International Conference on Wireless Communications and Signal Processing (WCSP)

作者： Jiasheng Xu Luoyi Fu Xiaoying Gan Bo Zhu School of Electronic Information and Electrical Engineering Shanghai Jiao Tong University Shanghai China School of Agriculture and Biology Shanghai Jiao Tong University Shanghai China

ISBN: (数字)9781728172361

ISBN: (纸本)9781728172378

Community detection, referred as the clustering procedure for similar nodes in the network, is an important research topic in the area of big data network. distributed community detection algorithm, with its simplicity and high-efficiency, has drawn extensive attention recently. The existing distributed algorithm can only be applied on networks with non-overlapping communities, however, overlapping communities widely exist in real networks, which cannot be detected by the distributed algorithm. We carefully study the overlapping community structure and introduce the overlapping stochastic block model, in which each node may belong to multiple communities. Based on the existing distributed algorithm, we further propose an improved algorithm with an extra stage to discover nodes belonging to the overlapping community, which can be applied on the overlapping stochastic block model. Through theoretical analysis, we show that the proposed algorithm achieves effective detection results on both overlapping and non-overlapping communities. We also conduct various simulations on the overlapping stochastic block model, showing that the proposed algorithm outperforms the existing distributed algorithm and maintains effectiveness in a wide range of system parameters.

关键词： Wireless communication Analytical models Simulation Stochastic processes Signal processing algorithms distributed algorithms Detection algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：