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

Breaking the Bellman-Ford Shortest-Path Bound

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Elmasry, Amr Egypt University of Informatics Alexandria University Egypt

In this paper we give a single-source shortest-path algorithm that breaks, after over 65 years, the O(n · m) bound for the running time of the Bellman-Ford-Moore algorithm, where n is the number of vertices and m is the number of arcs of the graph. Our algorithm converts the input graph to a graph with nonnegative weights by performing at most min(2 · √n, 2 · pm/ log n) calls to a modified version of Dijkstra’s algorithm, such that the shortest-path trees are the same for the new graph as those for the original. When Dijkstra’s algorithm is implemented using Fibonacci heaps, the running time of our algorithm is therefore O(√n · m + n · √m log n). © 2024, CC BY.

关键词： consensus algorithm

A Near-Optimal Low-Energy Deterministic Distributed SSSP with Ramifications on Congestion and APSP

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Ghaffari, Mohsen Trygub, Anton MIT United States

We present a low-energy deterministic distributed algorithm that computes exact Single-Source Shortest Paths (SSSP) in near-optimal time: it runs in Õ(n) rounds and each node is awake during only poly(log n) rounds. When a node is not awake, it performs no computations or communications and spends no energy. The general approach we take along the way to this result can be viewed as a novel adaptation of Dijkstra’s classic approach to SSSP, which makes it suitable for the distributed setting. Notice that Dijkstra’s algorithm itself is not efficient in the distributed setting due to its need for repeatedly computing the minimum-distance unvisited node in the entire network. Our adapted approach has other implications, as we outline next. As a step toward the above end-result, we obtain a simple deterministic algorithm for exact SSSP with near-optimal time and message complexities of Õ(n) and Õ(m), in which each edge communicates only poly(log n) messages. Therefore, one can simultaneously run n instances of it for n sources, using a simple random delay scheduling. That computes All Pairs Shortest Paths (APSP) in the near-optimal time complexity of Õ(n). This algorithm matches the complexity of the recent APSP algorithm of Bernstein and Nanongkai [STOC 2019] using a completely different method (and one that is more modular, in the sense that the SSSPs are solved independently). It also takes a step toward resolving the open problem on a deterministic Õ(n)-time APSP, as the only randomness used now is in the scheduling. Copyright © 2024, The Authors. All rights reserved.

关键词： consensus algorithm

Research on Travel Route Planing Problem Based on Greedy algorithm

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Wang, Yiquan College of Mathematics and System Science Xinjiang University Urumqi China Shenzhen X-institute Shenzhen China

The greedy algorithm based route planning problem is a method of finding the optimal or near optimal route between a given starting and ending point. This article first uses PCA method to reduce the dimensionality of urban evaluation indicators, extracts key principal components, and KMO and TOPSIS algorithms to reduce the dimensionality of the data. Secondly, for datasets that have not passed the KMO test, a comprehensive evaluation will be conducted using the entropy weight method and TOPSIS method. Finally, based on the greedy algorithm, a route planning algorithm was proposed and optimized to provide personalized route customization according to the different needs of tourists. We also took into account the local travel efficiency, the time required to visit tourist attractions, and necessary daily rest time to reduce costs and avoid falling into the local optimal solution. © 2024, CC BY-NC-SA.

关键词： consensus algorithm

Blockchain-Enabled Parallel Learning in Industrial Edge-Cloud Network: a Fuzzy DPoSt-PBFT Approach

学校读者我要写书评

暂无评论

Blockchain-Enabled Parallel Learning in Industrial Edge-Clou...

IEEE Globecom Workshops

作者： Fan Yang Jianwei Tian Tao Feng Fangmin Xu Chao Qiu Chenglin Zhao School of Information and Communication Engineering (SICE) Beijing University of Posts and Telecommunications (BUPT) Beijing China State Grid Hunan Electric Power Company Limited China National Tendering Center of Mach. Elec. Equipment MIIT College of Intelligence and Computing Tianjin University

ISBN: (纸本)9781665423915

Recently, parallel reinforcement learning (PRL) based Industrial Internet of Things (IIoT) edge-cloud resource scheduling has elicited escalating attention. However, with the scale of IIoT expands, there are several challenges in the existing researches: 1) large number of parallel servers slows down the convergence rate of PRL; 2) malicious parallel server affects resource allocation efficiency. In order to solve the above efficiency and security problem, blockchain-based approaches are introduced in PRL based resource allocation problem. However, traditional consensus algorithm in blockchain is not suitable for resource allocation and is inefficient. Thus, in this article, based on a novel fuzzy delegated proof of state and practical byzantine fault tolerance (fuzzy DPoSt+PBFT) consensus algorithm, we propose a blockchain-enabled collaborative parallel Q-learning (CPQL) approach to address the above challenges. To be specific, we first construct an edge-cloud collaborative architecture for executing the diversity intelligence IIoT applications. Then, we propose a CPQL algorithm for edge-cloud resource allocation and choosing the optimal number of parallel edge servers to speed up the Q-table training. In the Q-table aggregation process in CPQL, a fuzzy DPoSt+PBFT algorithm is designed for secure CPQL training and efficient consensus. Experimental results show the superior performance of the proposed approach. And the proposed approach has great potential in IIoT resource allocation problem.

关键词： Training Q-learning Job shop scheduling Fault tolerant systems Collaboration consensus algorithm Resource management

PUF-Based Authentication System with Resilience against Multi-Faceted Attacks for Blockchain-based IoT Networks

学校读者我要写书评

暂无评论

PUF-Based Authentication System with Resilience against Mult...

Applied Intelligence and Computing (AIC), IEEE World Conference on

作者： Anindita Sarkar Souvik Ganguly Partha Sarathi Sarkar Swagata Roy Chatterjee Department of Electronics and Communication Engineering Netaji Subhash Engineering College Kolkata India

ISBN: (数字)9798350384598

ISBN: (纸本)9798350384604

Now a days, blockchain based IOT networks are gaining popularity for the unlimited space and robust security mechanism. Blockchain is the best solution for the IoT devices to store the huge amount of data generated by them with utmost privacy and security using distributed ledger. However, the resource constrained IoT devices having low computing power are unable to meet the huge computing requirements of data mining in blockchain networks. This paper has proposed a robust Physically Unclonable Function (PUF)-based authentication system to replace the popular consensus algorithms by a lightweight hardware-based authentication mechanism without compromising the security and privacy. The proposed ring oscillator based PUF modules fortify users' credentials and withstand various types of attacks in decentralized and tamper-resistant blockchain based IOT network with significant reduction in latency and power consumption. Attack analysis is done to compare the vulnerabilities of both the proposed and conventional systems to prominent blockchain attacks. The results of attack analysis demonstrate that the proposed system outperforms the conventional PoW system.

关键词： Power demand Dictionaries System performance Authentication consensus algorithm Vectors Blockchains Internet of Things Security Resilience

Two-Step Blackout Mitigation by Flexibility-Enabled Microgrid Islanding 24

学校读者我要写书评

暂无评论

Two-Step Blackout Mitigation by Flexibility-Enabled Microgri...

Proceedings of the 15th ACM International Conference on Future and Sustainable Energy Systems

作者： Philipp Danner Anna Volkova Hermann De Meer University of Passau Germany

ISBN: (纸本)9798400704802

Blackouts are disastrous events with a low probability of occurrence but a high impact on the system and its users. With the help of more distributed and controllable generation and sector-coupled flexibility, microgrids could be prepared to operate in islanded mode during a blackout. This paper discusses a two-step blackout mitigation approach for highly renewable microgrids that utilizes user flexibility and energy storage systems for power balance in islanded grid operation. The proposed method includes a proactive flexibility reservation step, which derives a minimal reservation schedule for microgrid resources under uncertainty considering related operational costs. As a second step, during a blackout, a fully distributed control is implemented to maximize the usage of available resources based on a sequence of max and min-consensus rounds. This paper focuses on the second step, for which the effectiveness of blackstart and long-term coordination is shown. Load shedding can be reduced by 40% compared to the forecast value. A hardware-in-the-loop simulation of a grid-forming converter further showed a fast convergence toward the optimal operation point.

关键词： consensus algorithm microgrid islanding

On the Hypomonotone Class of Variational Inequalities

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Alomar, Khaled Chavdarova, Tatjana CISPA Helmholtz Center for Information Security Germany Politecnico di Milano University of California Berkeley United States

This paper studies the behavior of the extragradient algorithm [Korpelevich, 1976] when applied to hypomonotone operators, a class of problems that extends beyond the classical monotone setting. To support the understanding of this variational inequality problem class, we focus on a subclass of hypomonotone linear operators, characterizing them based on their eigenvalues and providing concrete examples. While the extragradient method is widely recognized for its efficiency in solving variational inequalities involving monotone and Lipschitz continuous operators, we demonstrate that it does not guarantee convergence in the hypomonotone case. In particular, we construct a counterexample where the extragradient method diverges regardless of the step size. A numerical experiment is presented to support this result. © 2024, CC BY.

关键词： consensus algorithm

Partible State Replication for Industrial Controller Redundancy

学校读者我要写书评

暂无评论

Partible State Replication for Industrial Controller Redunda...

IEEE International Conference on Industrial Technology (ICIT)

作者： Bjarne Johansson Olof Holmgren Thomas Nolte Alessandro V. Papadopoulos ABB Process Automation Process Control Platform Vasteras Sweden Malardalen University Vasteras Sweden

ISBN: (数字)9798350340266

ISBN: (纸本)9798350340273

Distributed control systems are part of the often invisible backbone of modern society that provides utility services like water and electricity. Their uninterrupted operation is vital, and unplanned stops due to failure can be expensive. Critical devices, like controllers, are often duplicated to minimize the service stop probability, with a secondary controller acting as a backup to the primary. A seamless takeover requires that the backup has the primary's latest state, i.e., the primary has to replicate its state to the backup. While this method ensures high availability, it can be costly due to hardware doubling. This work proposes a state replication solution that doesn't require the backup to store the primary state, separating state storage from the backup function. Our replication approach allows for more flexible controller redundancy deployments since one controller can be a backup for multiple primaries without being saturated by state replication data. Our main contribution is the partible state replication approach, realized with a distributed architecture utilizing a consensus algorithm. A partial connectivity-tolerant consensus algorithm is also an additional contribution.

关键词： Electricity Redundancy Decentralized control consensus algorithm Hardware

Surplus-Based ADMM for Distributed Constrained Optimization over Directed Graphs

学校读者我要写书评

暂无评论

Surplus-Based ADMM for Distributed Constrained Optimization ...

IEEE Conference on Decision and Control

作者： Qiutong Ji Guanghui Wen Tao Yang School of Cyber Science and Engineering Southeast University Nanjing China Department of Systems Science School of Mathematics Southeast University Nanjing China State Key Laboratory of Synthetical Automation for Process Industries Northeastern University Shenyang China

ISBN: (数字)9798350316339

ISBN: (纸本)9798350316346

This paper introduces a distributed parallel Alternating Direction Method of Multipliers (ADMM) algorithm for solving the distributed constrained optimization problem over directed graphs. To effectively handle the effect of asymmetric information communication on the convergence of the optimization algorithm, a surplus-based averaging consensus algorithm is integrated into the ADMM-based optimization algorithm. Unlike existing distributed ADMM algorithms over directed graphs that focus on the case with solely local constraints, the proposed algorithm can deal with both local constraints and coupling constraints. Under the assumption that the objective function is convex and the underlying graph is strongly connected, the convergence of the surplus-based ADMM to an optimal solution of the distributed constrained problem is proved. Finally, numerical simulations are conducted to validate the effectiveness of the proposed algorithm.

关键词： Couplings Directed graphs consensus algorithm Linear programming Numerical simulation Convex functions Optimization Convergence