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

Reductions and abstractions for formal verification of distributed round-based algorithms

SOFTWARE QUALITY JOURNAL 2021年第3期29卷 705-731页

作者： Barbosa, Raul Fonseca, Alcides Araujo, Filipe Univ Coimbra Dept Informat Engn CISUC P-3030290 Coimbra Portugal

Model checking has advanced over the last decades to become an effective formal technique for verifying distributed and concurrent systems. As computers grew in memory and processing capacity, it became possible to exhaustively verify systems with billions of states, making it practical to model and verify real-world protocols and algorithms. However, writing a model is a manual task that potentially introduces defects which the model checker tool finds to fulfill the formal specification (e.g., an incorrect model that fulfills an incomplete specification). Furthermore, this kind of formal verification technique is limited by the well-known state-space explosion problem. This paper aims to provide a set of generic template models, appropriate for distributed round-based algorithms, to be used to focus modeling effort on algorithm-specific details. To mitigate state-space explosion, the paper proposes two reduction techniques, named partition symmetry reduction and message order reduction, that exploit symmetries in the state space to avoid expanding equivalent states. The reusable framework for verifying round-based algorithms and the two proposed reduction techniques provide the means for reducing by orders of magnitude the number of states required to analyze common distributed algorithms.

关键词： Model checking distributed algorithms Formal verification

来源：评论

学校读者我要写书评

暂无评论

distributed fault simulation algorithms on parallel virtual machine

引用

VLSI DESIGN 2001年第1期12卷 81-99页

作者： Ravikumar, CP Jain, V Dod, A Indian Inst Technol Dept Elect Engn New Delhi 110016 India

In this paper, we describe distributed algorithms for combinational fault simulation assuming the classical stuck-at fault model. Our algorithms have been implemented on a network of Sun workstations under the Parallel Virtual Machine (PVM) environment. Two techniques are used for subdividing work among processors - test set partition and fault set partition. The sequential algorithm for fault simulation, used on individual nodes of the network, is based on a novel path compression technique proposed in this paper We describe experimental results on a number of ISCAS'85 benchmark circuits.

关键词： distributed algorithms fault simulation stuck-at fault model parallel processing fault coverage

来源：评论

学校读者我要写书评

暂无评论

distributed SIMULATED ANNEALING algorithms FOR JOB-SHOP SCHEDULING

引用

IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS 1995年第7期25卷 1102-1109页

作者： KRISHNA, K GANESHAN, K RAM, DJ WIPRO INFOTECH BANGALORE 560001KARNATAKAINDIA INDIAN INST TECHNOL DEPT COMP SCI & ENGNMADRAS 600036TAMIL NADUINDIA

Job shop scheduling belongs to the class of NP-hard problems, There are a number of algorithms in literature for finding near optimal solution for the job shop scheduling problem. Many of these algorithms exploit the problem specific information and hence are less general. However, simulated annealing algorithm for job shop scheduling is general and produces better results in comparison with other similar algorithms, But one of the major drawbacks of the algorithm is that the execution time is high, This makes the algorithm inapplicable to large scale problems, One possible approach to reduce the execution time of the algorithm is to develop distributed algorithms for simulated annealing, In this paper, we discuss approaches to developing distributed algorithms for simulated annealing for solving the job shop scheduling problem. Three different algorithms have been developed, These are the Temperature Modifier, the Locking Edges and the Modified Locking Edges algorithms, These algorithms have been implemented on the distributed Task Sharing System (DTSS) running on a network of 18 sun workstations. The observed performance showed that each of these algorithms performs well depending on the problem size.

关键词： Simulated annealing Scheduling algorithm Job shop scheduling distributed algorithms Temperature Processor scheduling Space technology Computational modeling Large-scale systems Sun

来源：评论

学校读者我要写书评

暂无评论

distributed Continuous-Time algorithms for Optimal Resource Allocation With Time-Varying Quadratic Cost Functions

引用

IEEE TRANSACTIONS ON CONTROL OF NETWORK SYSTEMS 2020年第4期7卷 1974-1984页

作者： Wang, Bo Sun, Shan Ren, Wei Beijing Inst Technol Sch Automat Beijing 100081 Peoples R China Univ Calif Riverside Dept Elect & Comp Engn Riverside CA 92521 USA

In this article, we propose distributed continuous-time algorithms to solve the optimal resource allocation problem with certain time-varying quadratic cost functions for multiagent systems. The objective is to allocate a quantity of resources while optimizing the sum of all the local time-varying cost functions. Here, the optimal solutions are trajectories rather than some fixed points. We consider a large number of agents that are connected through a network, and our algorithms can be implemented using only local information. By making use of the prediction-correction method and the nonsmooth consensus idea, we first design two distributed algorithms to deal with the case when the time-varying cost functions have identical Hessians. We further propose an estimator-based algorithm which uses distributed average tracking theory to estimate certain global information. With the help of the estimated global information, the case of nonidentical constant Hessians is addressed. In each case, it is proved that the solutions of the proposed dynamical systems with certain initial conditions asymptotically converge to the optimal trajectories. We illustrate the effectiveness of the proposed distributed continuous-time optimal resource allocation algorithms through simulations.

关键词： Cost function Resource management Heuristic algorithms Prediction algorithms Time-varying systems Trajectory distributed algorithms optimization resource allocation time-varying cost functions

来源：评论

学校读者我要写书评

暂无评论

On the robust synthesis of logical consensus algorithms for distributed intrusion detection

引用

AUTOMATICA 2013年第8期49卷 2339-2350页

作者： Fagiolini, Adriano Bicchi, Antonio Univ Palermo DEIM Fac Engn I-90133 Palermo Italy Univ Pisa Fac Engn Interdept Res Ctr E Piaggio I-56100 Pisa Italy Ist Italiano Tecnol Dept Adv Robot I-16163 Genoa Italy

We introduce a novel consensus mechanism by which the agents of a network can reach an agreement on the value of a shared logical vector function depending on binary input events. Based on results on the convergence of finite-state iteration systems, we provide a technique to design logical consensus systems that minimizing the number of messages to be exchanged and the number of steps before consensus is reached, and tolerating a bounded number of failed or malicious agents. We provide sufficient joint conditions on the input visibility and the communication topology for the method's applicability. We describe the application of our method to two distributed network intrusion detection problems. (C) 2013 Elsevier Ltd. All rights reserved.

关键词： Consensus distributed algorithms Intrusion detection Security

来源：评论

学校读者我要写书评

暂无评论

Optimal Dispersion in Triangular Grids: Achieving Efficiency Without Prior Knowledge 21st

Optimal Dispersion in Triangular Grids: Achieving Efficiency...

引用

21st International Conference on distributed Computing and Intelligent Technology

作者： Pandit, Himani Pandit, Supantha Dhirubhai Ambani Inst Informat & Commun Technol Gandhinagar Gujarat India

ISBN: (纸本)9783031814037;9783031814044

In the dispersion problem, a group of k <= n mobile robots, initially placed on the vertices of an anonymous graph G with n vertices, must redistribute themselves so that each vertex hosts no more than one robot. We address this challenge on an anonymous triangular grid graph, where each vertex can connect to up to six adjacent vertices. We propose a distributed deterministic algorithm that achieves dispersion on an unoriented triangular grid graph in O(root n) time, where n is the number of vertices. Each robot requires O(log n) bits of memory. The time complexity of our algorithm and the memory usage per robot are optimal. This work builds on previous studies by Kshemkalyani et al. [WALCOM 2020 [17]] and Banerjee et al. [ALGOWIN 2024 [3]]. Importantly, our algorithm terminates without requiring prior knowledge of n and resolves a question posed by Banerjee et al. [ALGOWIN 2024 [3]].

关键词： distributed algorithms Mobile robots Dispersion Triangular grid Deterministic algorithms

来源：评论

学校读者我要写书评

暂无评论

Quantized incremental algorithms for distributed optimization

引用

IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS 2005年第4期23卷 798-808页

作者： Rabbat, MG Nowak, RD Univ Wisconsin Dept Elect & Comp Engn Madison WI 53706 USA

Wireless sensor networks are capable of collecting an enormous amount of data. Often, the ultimate objective is to estimate a parameter or function from these data, and such estimators are typically the solution of an optimization problem (e.g., maximum likelihood, minimum mean-squared error, or maximum a posteriori). This paper investigates a general class of distributed optimization algorithms for "in-network" data processing, aimed at reducing the amount of energy and bandwidth used for communication. Our intuition tells us that processing the data in-network should, in general, require less energy than transmitting all of the data to a fusion center. In this paper, we address the questions: When, in fact, does in-network processing use less energy, and how much energy is saved.? The proposed distributed algorithms are based on incremental optimization methods. A parameter estimate,is circulated through the network, and along the way each node makes a small gradient descent-like adjustment to the estimate based only on its local data. Applying results from the theory of incremental subgradient optimization, we find that the distributed algorithms converge to an approximate solution for a broad class of problems. We extend these results to the case where the optimization variable is quantized before being transmitted to the next node and find that quantization does not affect the rate of convergence. Bounds on the number of incremental steps required for a certain level of accuracy provide insight into the tradeoff between estimation performance and communication overhead. Our main conclusion is that as the number of sensors in the network grows, in-network processing will always use less energy than a centralized algorithm, while maintaining a desired level of accuracy.

关键词： distributed algorithms energy-accuracy tradeoff gradient methods wireless sensor networks

来源：评论

学校读者我要写书评

暂无评论

distributed CONTINUOUS-TIME algorithms FOR NONSMOOTH EXTENDED MONOTROPIC OPTIMIZATION PROBLEMS

引用

SIAM JOURNAL ON CONTROL AND OPTIMIZATION 2018年第6期56卷 3973-3993页

作者： Zeng, Xianlin Yi, Peng Hong, Yiguang Xie, Lihua Beijing Inst Technol Sch Automat Key Lab Intelligent Control & Decis Complex Syst Beijing 100081 Peoples R China Washington Univ Dept Elect & Syst Engn St Louis MO 63130 USA Univ Chinese Acad Sci Chinese Acad Sci Key Lab Syst & Control Beijing 100190 Peoples R China Nanyang Technol Univ Sch Elect & Elect Engn 50 Nanyang Ave Singapore 639798 Singapore

This paper studies distributed algorithms for the nonsmooth extended monotropic optimization problem, which is a general convex optimization problem with a certain separable structure. The considered nonsmooth objective function is the sum of local objective functions assigned to agents in a multiagent network, with local set constraints and affine equality constraints. Each agent only knows its local objective function, local set constraint, and the information exchanged between neighbors. To solve the constrained convex optimization problem, we propose two novel distributed continuous-time subgradient-based algorithms, with projected output feedback and derivative feedback, respectively. Moreover, we prove the convergence of proposed algorithms to the optimal solutions under some mild conditions and analyze convergence rates, with the help of the techniques of variational inequalities, decomposition methods, and differential inclusions. Finally, we give an example to illustrate the efficacy of the proposed algorithms.

关键词： extended monotropic optimization distributed algorithms nonsmooth convex functions decomposition methods differential inclusions

来源：评论

学校读者我要写书评

暂无评论

Consensus-Based Cooperative algorithms for Training Over distributed Data Sets Using Stochastic Gradients

引用

IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS 2022年第10期33卷 5579-5589页

作者： Li, Zhongguo Liu, Bo Ding, Zhengtao Univ Manchester Dept Elect & Elect Engn Manchester M13 9PL Lancs England

In this article, distributed algorithms are proposed for training a group of neural networks with private data sets. Stochastic gradients are utilized in order to eliminate the requirement for true gradients. To obtain a universal model of the distributed neural networks trained using local data sets only, consensus tools are introduced to derive the model toward the optimum. Most of the existing works employ diminishing learning rates, which are often slow and impracticable for online learning, while constant learning rates are studied in some recent works, but the principle for choosing the rates is not well established. In this article, constant learning rates are adopted to empower the proposed algorithms with tracking ability. Under mild conditions, the convergence of the proposed algorithms is established by exploring the error dynamics of the connected agents, which provides an upper bound for selecting the constant learning rates. Performances of the proposed algorithms are analyzed with and without gradient noises, in the sense of mean square error (MSE). It is proved that the MSE converges with bounded errors determined by the gradient noises, and the MSE converges to zero if the gradient noises are absent. Simulation results are provided to validate the effectiveness of the proposed algorithms.

关键词： Training Neural networks Convergence distributed databases Machine learning algorithms Optimization distributed algorithms Consensus convergence analysis distributed training multiagent systems neural networks optimization

来源：评论

学校读者我要写书评

暂无评论

Specification and verification of various distributed leader election algorithms for unidirectional ring networks

引用

SCIENCE OF COMPUTER PROGRAMMING 1997年第1-2期29卷 171-197页

作者： Garavel, H Mounier, L VERIMAG F-38610 GIERESFRANCE

This paper deals with the formal specification and verification of distributed leader election algorithms for a set of machines connected by a unidirectional ring network. Starting from an algorithm proposed by Le Lann in 1977, and its variant proposed by Chang and Roberts in 1979, we study the robustness of these algorithms in the presence of unreliable communication medium and unreliable machines. We propose various improvements of these algorithms in order to obtain a fully fault-tolerant protocol. These algorithms are formally described using the ISO specification language LOTOS and verified (for a fixed number of machines) using the CADP (CAESAR/ALDEBARAN) toolbox. Using model-checking and bisimulation techniques, the verification of these non-trivial algorithms can be carried out automatically, in a few seconds. (C) 1997 Elsevier Science B.V.

关键词： distributed algorithms formal methods leader election LOTOS token ring validation verification

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：