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

COMPUTATION OF ZOLOTAREV RATIONAL FUNCTIONS

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Trefethen, Lloyd N. Wilber, Heather D. School of Engineering and Applied Sciences Harvard University CambridgeMA02138 United States Dept. of Applied Mathematics University of Washington SeattleWA98195 United States

An algorithm is presented to compute Zolotarev rational functions, that is, rational functions rn∗ of a given degree that are as small as possible on one set E ⊆ C ∪ {∞} relative to their size on another set F ⊆ C ∪ {∞} (the third Zolotarev problem). Along the way we also approximate the sign function relative to E and F (the fourth Zolotarev problem).MSC Codes 30E10, 41A20, 65D15 © 2024, CC BY.

关键词： consensus algorithm

On the Hardness of Decentralized Multi-Agent Policy Evaluation under Byzantine Attacks

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Hairi Fang, Minghong Zhang, Zifan Velasquez, Alvaro Liu, Jia Dept. of Computer Science University of Wisconsin-Whitewater United States Dept. of Computer Science and Engineering University of Louisville United States Dept. of Computer Science North Carolina State University United States Dept. of Computer Science University of Colorado Boulder United States Dept. of Electrical and Computer Engineering The Ohio State University United States

In this paper, we study a fully-decentralized multi-agent policy evaluation problem, which is an important sub-problem in cooperative multi-agent reinforcement learning, in the presence of up to f faulty agents. In particular, we focus on the so-called Byzantine faulty model with model poisoning setting. In general, policy evaluation is to evaluate the value function of any given policy. In cooperative multi-agent system, the system-wide rewards are usually modeled as the uniform average of rewards from all agents. We investigate the multi-agent policy evaluation problem in the presence of Byzantine agents, particularly in the setting of heterogeneous local rewards. Ideally, the goal of the agents is to evaluate the accumulated system-wide rewards, which are uniform average of rewards of the normal agents for a given policy. It means that all agents agree upon common values (the consensus part) and furthermore, the consensus values are the value functions (the convergence part). However, we prove that this goal is not achievable. Instead, we consider a relaxed version of the problem, where the goal of the agents is to evaluate accumulated system-wide reward, which is an appropriately weighted average reward of the normal agents. We further prove that there is no correct algorithm that can guarantee that the total number of positive weights exceeds |N|− f, where |N| is the number of normal agents. Towards the end, we propose a Byzantine-tolerant decentralized temporal difference algorithm that can guarantee asymptotic consensus under scalar function approximation. We then empirically test the effective of the proposed algorithm. Copyright © 2024, The Authors. All rights reserved.

关键词： consensus algorithm

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Bektas, Sebahattin Ondokuz Mayis University Geomatics Engineering Samsun Turkey

Nowadays, we have seen that dual quaternion algorithms are used in 3D coordinate transformation problems due to their advantages. 3D coordinate transformation problem is one of the important problems in geodesy. This transformation problem is encountered in many application areas other than geodesy. Although there are many coordinate transformation methods (similarity, affine, projective, etc.), similarity transformation is used because of its simplicity. The asymmetric transformation is preferred to the symmetric coordinate transformation because of its ease of use. In terms of error theory, the symmetric transformation should be preferred. In this study, the topic of symmetric similarity 3D coordinate transformation based on the dual quaternion algorithm is discussed, and the bottlenecks encountered in solving the problem and the solution method are discussed. A new iterative algorithm based on the dual quaternion is presented. The solution is implemented in two different models: with constraint equations and without constraint equations. The advantages and disadvantages of the two models compared to each other are also evaluated. Not only the transformation parameters but also the errors of the transformation parameters are determined. The detailed derivation of the formulas for estimating the symmetric similarity of 3D transformation parameters is presented step by step. Since symmetric transformation is the general form of asymmetric transformation, we can also obtain asymmetric transformation results with a simple modification of the model we developed for symmetric transformation. The proposed algorithm is capable of performing both 2D and 3D symmetric and asymmetric similarity transformations. For the 2D transformation, it is sufficient to replace the z and Z coordinates in both systems with zero. © 2024, CC BY.

关键词： consensus algorithm

Distributed And Parallel Low-Diameter Decompositions for Arbitrary and Restricted Graphs

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Dou, Jinfeng Götte, Thorsten Hillebrandt, Henning Scheideler, Christian Werthmann, Julian

We consider the distributed and parallel construction of low-diameter decompositions with strong diameter for (weighted) graphs and (weighted) graphs that can be separated through k ∈ Õ(1) shortest paths. This class of graphs includes planar graphs, graphs of bounded treewidth, and graphs that exclude a fixed minor Kr. We present algorithms in the PRAM, CONGEST, and the novel HYBRID communication model that are competitive in all relevant parameters. Given D > 0, our low-diameter decomposition algorithm divides the graph into connected clusters of strong diameter D. For a arbitrary graph, an edge e ∈ E of length e is cut between two clusters with probability O(***(n) ). If the graph can be separated by k ∈ Õ(1) paths, the probability improves to O(*** log n ). In either case, the decompositions can be computed in Õ(1) depth and Õ(kn) work in the PRAM and Õ(1) time in the HYBRID model. D In CONGEST, the runtimes are Õ(HD + √n) and Õ(HD) respectively. All these results hold w.h.p. Broadly speaking, we present distributed and parallel implementations of sequential divide-and-conquer algorithms where we replace exact shortest paths with approximate shortest paths. In contrast to exact paths, these can be efficiently computed in the distributed and parallel setting [STOC’22]. Further, and perhaps more importantly, we show that instead of explicitly computing vertex-separators to enable efficient parallelization of these algorithms, it suffices to sample a few random paths of bounded length and the nodes close to them. Thereby, we do not require complex embeddings whose implementation is unknown in the distributed and parallel setting. Copyright © 2024, The Authors. All rights reserved.

关键词： consensus algorithm

A Comprehensive Study on Blockchain and its Frameworks

学校读者我要写书评

暂无评论

A Comprehensive Study on Blockchain and its Frameworks

IEEE UP Section Conference on Electrical Computer and Electronics (UPCON)

作者： Aditi Sharma Rajesh Kumar Kaushal Naveen Kumar Computer Science & Engineering Chitkara University Institute of Engineering and Technology Chitkara University Punjab India

ISBN: (数字)9798350378726

ISBN: (纸本)9798350378733

The industrial applications of blockchain technology are examined in this paper, with particular attention on layered architecture and well-known frameworks such as Ethereum, Hyperledger, Corda, and Quorum. The paper highlights the main advantages and disadvantages of the present implementations by analyzing scalability, privacy, and governance across these frameworks. Research indicates that energy-efficient and scalable blockchain systems could significantly increase data security and transparency in sectors including supply chains, healthcare, and finance. Future blockchain improvements in interoperability and consensus efficiency may be able to address current issues and encourage more secure, effective data management across various domains.

关键词： Surveys Privacy Distributed ledger Scalability Supply chains Medical services consensus algorithm Computer architecture Energy efficiency Blockchains

Research on Hierarchical Sharding Based on Spectral Clustering algorithm

学校读者我要写书评

暂无评论

Research on Hierarchical Sharding Based on Spectral Clusteri...

Computer Science and Blockchain (CCSB), International Conference on

作者： Yang Zhang The School of Cyberspace Security Zhongyuan University of Technology Zhengzhou Henan China

ISBN: (数字)9798350356502

ISBN: (纸本)9798350356519

Traditional blockchains face scalability issues such as low throughput, high transaction delay, and high storage redundancy. Introducing sharding technology can effectively improve the scalability of blockchain systems. However, current sharding techniques typically use random sharding, which may have an impact on the performance of the entire blockchain system. In response to the above issues, this article proposes a hierarchical sharding scheme based on spectral clustering and semi-sharding storage. This scheme adopts a master-slave hierarchical deployment of the blockchain, with the main chain responsible for integrating the state information of shard sub-chains, achieving consistency in the state of master-slave multi-chains. In the chain design, this article uses a spectral clustering algorithm to partition nodes with similar performance and geographical location into the same shard, thereby reducing transaction delay and ensuring performance balance among nodes within the shard. The simulation experiment results show that the proposed sharding scheme can significantly shorten transaction delay and effectively improve the throughput of the blockchain system.

关键词： Sharding Scalability Redundancy Clustering algorithms consensus algorithm Throughput Main-secondary Blockchains Delays Partitioning algorithms

An approximation algorithm for Maximum DiCut vs. Cut

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Nakajima, Tamio-Vesa Živný, Stanislav University of Oxford United Kingdom

Goemans and Williamson designed a 0.878-approximation algorithm for Max-Cut in undirected graphs [JACM’95]. Khot, Kindler, Mosel, and O’Donnel showed that the approximation ratio of the Goemans-Williamson algorithm is optimal assuming Khot’s Unique Games Conjecture [SICOMP’07]. In the problem of maximum cuts in directed graphs (Max-DiCut), in which we seek as many edges going from one particular side of the cut to the other, the situation is more complicated but the recent work of Brakensiek, Huang, Potechin, and Zwick showed that their 0.874-approximation algorithm is tight under the Unique Games Conjecture (up to a small delta) [FOCS’23]. We consider a promise version of the problem and design an SDP-based algorithm which, if given a directed graph G that has a directed cut of value p, finds an undirected cut in G (ignoring edge directions) with value at least p. © 2024, CC BY.

关键词： consensus algorithm

HEX: Hierarchical Emergence Exploitation in Self-Supervised algorithms

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Kokilepersaud, Kiran Kim, Seulgi Prabhushankar, Mohit AlRegib, Ghassan OLIVES The Center for Signal and Information Processing CSIP School of Electrical and Computer Engineering Georgia Institute of Technology AtlantaGA United States

In this paper, we propose an algorithm that can be used on top of a wide variety of self-supervised (SSL) approaches to take advantage of hierarchical structures that emerge during training. SSL approaches typically work through some invariance term to ensure consistency between similar samples and a regularization term to prevent global dimensional collapse. Dimensional collapse refers to data representations spanning a lower-dimensional subspace. Recent work has demonstrated that the representation space of these algorithms gradually reflects a semantic hierarchical structure as training progresses. Data samples of the same hierarchical grouping tend to exhibit greater dimensional collapse locally compared to the dataset as a whole due to sharing features in common with each other. Ideally, SSL algorithms would take advantage of this hierarchical emergence to have an additional regularization term to account for this local dimensional collapse effect. However, the construction of existing SSL algorithms does not account for this property. To address this, we propose an adaptive algorithm that performs a weighted decomposition of the denominator of the InfoNCE loss into two terms: local hierarchical and global collapse regularization respectively. This decomposition is based on an adaptive threshold that gradually lowers to reflect the emerging hierarchical structure of the representation space throughout training. It is based on an analysis of the cosine similarity distribution of samples in a batch. We demonstrate that this hierarchical emergence exploitation (HEX) approach can be integrated across a wide variety of SSL algorithms. Empirically, we show performance improvements of up to 5.6% relative improvement over baseline SSL approaches on classification accuracy on Imagenet with 100 epochs of training. © 2024, CC BY.

关键词： consensus algorithm

A Policy Iteration algorithm for N-player General-Sum Linear Quadratic Dynamic Games

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Guan, Yuxiang Salizzoni, Giulio Kamgarpour, Maryam Summers, Tyler H. The Control Optimization and Networks Lab University of Texas at Dallas United States The Systems Control and Multi-Agent Optimization Research Lab EPFL Switzerland

We present a policy iteration algorithm for the infinite-horizon N-player general-sum deterministic linear quadratic dynamic games and compare it to policy gradient methods. We demonstrate that the proposed policy iteration algorithm is distinct from the Gauss-Newton policy gradient method in the N-player game setting, in contrast to the single-player setting where under suitable choice of step size they are equivalent. We illustrate in numerical experiments that the convergence rate of the proposed policy iteration algorithm significantly surpasses that of the Gauss-Newton policy gradient method and other policy gradient variations. Furthermore, our numerical results indicate that, compared to policy gradient methods, the convergence performance of the proposed policy iteration algorithm is less sensitive to the initial policy and changes in the number of players. Copyright © 2024, The Authors. All rights reserved.

关键词： consensus algorithm