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

43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL)

作者： Dragoi, Cezara Henzinger, Thomas A. Zufferey, Damien CNRS ENS INRIA F-75700 Paris France IST Austria Vienna Austria MIT CSAIL Boston MA USA

ISBN: (纸本)9781450335492

fault-tolerant distributed algorithms play an important role in many critical/high-availability applications. These algorithms are notoriously difficult to implement correctly, due to asynchronous communication and the occurrence of faults, such as the network dropping messages or computers crashing. We introduce PSYNC, a domain specific language based on the Heard-Of model, which views asynchronous faulty systems as synchronous ones with an adversarial environment that simulates asynchrony and faults by dropping messages. We define a runtime system for PSYNC that efficiently executes on asynchronous networks. We formalize the relation between the runtime system and PSYNC in terms of observational refinement. The high-level lockstep abstraction introduced by PSYNC simplifies the design and implementation of fault-tolerant distributed algorithms and enables automated formal verification. We have implemented an embedding of PSYNC in the SCALA programming language with a runtime system for asynchronous networks. We show the applicability of PSYNC by implementing several important fault-tolerant distributed algorithms and we compare the implementation of consensus algorithms in PSYNC against implementations in other languages in terms of code size, runtime efficiency, and verification.

关键词： fault-tolerant distributed algorithms Round model Partial synchrony Automated verification Consensus

来源：评论

学校读者我要写书评

暂无评论

PSYNC: A Partially Synchronous Language for fault-tolerant distributed algorithms

引用

ACM SIGPLAN NOTICES 2016年第1期51卷 400-415页

作者： Dragoi, Cezara Henzinger, Thomas A. Zufferey, Damien CNRS ENS INRIA F-75700 Paris France IST Austria Vienna Austria MIT CSAIL Boston MA USA

关键词： fault-tolerant distributed algorithms Round model Partial synchrony Automated verification Consensus

来源：评论

学校读者我要写书评

暂无评论

Distal: A Framework for Implementing fault-tolerant distributed algorithms

Distal: A Framework for Implementing Fault-tolerant Distribu...

引用

43rd Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN)

作者： Biely, Martin Delgado, Pamela Milosevic, Zarko Schiper, Andre Ecole Polytech Fed Lausanne CH-1015 Lausanne Switzerland

ISBN: (纸本)9781479901814;9781467364713

We introduce Distal, a new framework that simplifies turning pseudocode of fault tolerant distributed algorithms into efficient executable code. Without proper tool support, even small amounts of pseudocode normally ends up in several thousands of non-trivial lines of Java or C++. Distal is implemented as a library in Scala and consists of two main parts: a domain specific language (DSL) in which algorithms are expressed and an efficient messaging layer that deals with low level issues such as connection management, threading and (de) serialization. The DSL is designed such that implementations of distributed algorithms highly resemble the pseudocode found in research papers. By writing code that is close to the protocol description, one can be more convinced that the implemented system really reflects the protocol specification on paper. Distal does not only make it simple and intuitive to implement distributed algorithms but it also leads to efficient implementations.

关键词： DSL fault-tolerant distributed algorithms Paxos SMR

来源：评论

学校读者我要写书评

暂无评论

Synthesis of fault-tolerant Reliable Broadcast algorithms With Reinforcement Learning

引用

IEEE ACCESS 2023年 11卷 62394-62408页

作者： Vaz, Diogo Matos, David R. Pardal, Miguel L. Correia, Miguel Univ Lisbon INESC ID Inst Super Tecn P-1000029 Lisbon Portugal

fault-tolerant algorithms, such as Reliable Broadcast, assure the correct operation of modern distributed systems, even when some of the system nodes fail. However, the development of distributed algorithms is a manual and complex process, where slight changes in requirements can require a complete redesign of the algorithm. To automate the process of developing such algorithms, this work presents a new approach that uses Reinforcement Learning to synthesize correct and efficient fault-tolerant distributed algorithms. This work shows the first application of the approach on the synthesis of fault-tolerant Reliable Broadcast algorithms. The presented technique is capable of synthesizing correct and efficient algorithms with the same performance as others available in the literature as well as a new Byzantine tolerant algorithm, in only 12,000 learning episodes. Based on the success of this implementation, we aim, in the future, to extend this technique to other distributed algorithms such as Consensus.

关键词： fault-tolerant distributed algorithms reliable broadcast program synthesis reinforcement learning program verification model-checking

来源：评论

学校读者我要写书评

暂无评论

Resilient Real-Valued Consensus in Spite of Mobile Malicious Agents on Directed Graphs

引用

IEEE TRANSACTIONS ON PARALLEL AND distributed SYSTEMS 2022年第3期33卷 586-603页

作者： Wang, Yuan Ishii, Hideaki Bonnet, Francois Defago, Xavier KTH Royal Inst Technol Div Decis & Control Syst S-11428 Stockholm Sweden Tokyo Inst Technol Dept Comp Sci Tokyo 1528550 Japan

This article addresses novel real-valued consensus problems in the presence of malicious adversaries that can move within the network and induce faulty behaviors in the attacked agents. By adopting several mobile adversary models from the computer science literature, we develop protocols which can mitigate the influence of such malicious agents. The algorithms follow the class of mean subsequence reduced (MSR) algorithms, under which agents ignore the suspicious values received from neighbors during their state updates. Different from the static adversary models, even after the adversaries move away, the infected agents may remain faulty in their values, whose effects must be taken into account. We develop conditions on the network structures for both the complete and non-complete directed graph cases, under which the proposed algorithms are guaranteed to attain resilient consensus. The tolerance bound for network conditions becomes more strict as the adversaries are allowed to have more power. Extensive simulations are carried out over random graphs to verify the effectiveness of our approach when the information of the adversarial agents in terms of their models and numbers is unknown to the agents.

关键词： Protocols Directed graphs Computer science Computational modeling Voltage measurement Timing Security fault-tolerant distributed algorithms multi-agent systems resilient real-valued consensus mobile adversary agents malicious agents network connectivity

来源：评论

学校读者我要写书评

暂无评论

Automatic Generation of distributed algorithms with Generative AI 53

Automatic Generation of Distributed Algorithms with Generati...

引用

53rd Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN)

作者： Vaz, Diogo Matos, David R. Pardal, Miguel L. Correia, Miguel Univ Lisbon Inst Super Tecn INESC ID Lisbon Portugal

ISBN: (纸本)9798350325454

fault-tolerant distributed algorithms such as Reliable Broadcast, Causal Broadcast, Total Order Broadcast, and Consensus, are at the core of many modern distributed systems. However, the development of distributed algorithms by humans is a laborious and complex process. This work presents a novel approach to generating distributed algorithms using Generative Artificial Intelligence that allows for automating the process of generating such algorithms. The paper also summarizes our initial results on using the approach to generate Reliable Broadcast algorithms.

关键词： fault-tolerant distributed algorithms Reliable Broadcast Automatic Algorithm Generation Generative AI Reinforcement Learning Automatic Algorithm Validation

来源：评论

学校读者我要写书评

暂无评论

fault-tolerant Clock Synchronization Over Unreliable Channels in Wireless Sensor Networks

引用

IEEE TRANSACTIONS ON CONTROL OF NETWORK SYSTEMS 2018年第4期5卷 1551-1562页

作者： Kikuya, Yuhei Dibaji, Seyed Mehran Ishii, Hideaki Tokyo Inst Technol Dept Comp Sci Yokohama Kanagawa 2268502 Japan MIT Dept Mech Engn Cambridge MA 02139 USA

In this paper, we study a distributed approach based on consensus algorithms for clock synchronization in wireless sensor networks. The sensor nodes face two types of uncertainties. One is that some of the nodes in the network can be faulty and transmit arbitrary signals by not following the given protocol;similar effects may be caused by false data injection by an external malicious attacker. The other is that the communication is unreliable and the packets exchanged may become lost. To deal with these uncertainties, we propose a resilient consensus-type algorithm based on the so-called mean subsequence reduced (MSR) technique, where each normal node ignores the outliers in the clock data collected from its neighbors and makes updates using data from the past if new data have not arrived yet. We establish network connectivity conditions in terms of graph robustness for the MSR algorithm to attain resilient properties.

关键词： Clock synchronization cybersecurity fault-tolerant distributed algorithms multiagent consensus wireless sensor networks

来源：评论

学校读者我要写书评

暂无评论

Construction and Formal Verification of a fault-tolerant distributed Mutual Exclusion Algorithm 16

Construction and Formal Verification of a Fault-Tolerant Dis...

引用

16th ACM SIGPLAN International Workshop on Erlang (Erlang)

作者： Shishkin, Evgeniy JSC InfoTeCS Adv Res Dept Moscow Russia

ISBN: (纸本)9781450351799

distributed fault-tolerant control algorithms are in great demand nowadays due to their practical importance in cloud computing, Internet of Things (IoT) technology, swarm robotics, and other areas. It is usually hard to make a distributed algorithm fault-tolerant. It is even harder to ensure that such algorithm behaves correctly in the presence of faults of some kind. In this work, we construct a reliable, adaptive, fault-tolerant distributed mutual exclusion algorithm based on the well-known Ricart-Agrawala algorithm. In order to formally verify it, we use a hybrid approach of deductive reasoning and bounded model-checking. First, a safety property of the Ricart-Agrawala algorithm is proved in Calculus of Inductive Constructions of Coq proof assistant using assertional reasoning. Then, an extension of that algorithm turning it into fault-tolerant and adaptive to participants set change, is formalized in TLA and checked on a bounded model. Besides constructing and verifying the algorithm, this work aims to familiarize those interested in constructing highly reliable components with well established verification methods that were used to verify the proposed algorithm.

关键词： fault-tolerant distributed algorithms deductive verification model-checking mutual exclusion

来源：评论

学校读者我要写书评

暂无评论

Para: parameterized path reduction, acceleration, and SMT for reachability in threshold-guarded distributed algorithms

引用

FORMAL METHODS IN SYSTEM DESIGN 2017年第2期51卷 270-307页

作者： Konnov, Igor Lazic, Marijana Veith, Helmut Widder, Josef TU Wien Vienna Univ Technol Inst Informat Syst E184 4 Favoritenstr 9-11 A-1040 Vienna Austria

Automatic verification of threshold-based fault-tolerant distributed algorithms (FTDA) is challenging: FTDAs have multiple parameters that are restricted by arithmetic conditions, the number of processes and faults is parameterized, and the algorithm code is parameterized due to conditions counting the number of received messages. Recently, we introduced a technique that first applies data and counter abstraction and then runs bounded model checking (BMC). Given an FTDA, our technique computes an upper bound on the diameter of the system. This makes BMC complete for reachability properties: it always finds a counterexample, if there is an actual error. To verify state-of-the-art FTDAs, further improvement is needed. In contrast to encoding bounded executions of a counter system over an abstract finite domain in SAT, in this paper, we encode bounded executions over integer counters in SMT. In addition, we introduce a new form of reduction that exploits acceleration and the structure of the FTDAs. This aggressively prunes the execution space to be explored by the solver. In this way, we verified safety of seven FTDAs that were out of reach before.

关键词： Parameterized verification Bounded model checking Completeness Partial orders in distributed systems Reduction fault-tolerant distributed algorithms Byzantine faults

来源：评论

学校读者我要写书评

暂无评论

On the completeness of bounded model checking for threshold-based distributed algorithms: Reachability

引用

INFORMATION AND COMPUTATION 2017年 252卷 95-109页

作者： Konnov, Igor Veith, Helmut Widder, Josef TU Wien Vienna Univ Technol Vienna Austria

Counter abstraction is a powerful tool for parameterized model checking, if the number of local states of the concurrent processes is relatively small. In recent work, we introduced parametric interval counter abstraction that allowed us to verify the safety and liveness of threshold-based fault-tolerant distributed algorithms (FTDA). Due to state space explosion, applying this technique to distributed algorithms with hundreds of local states is challenging for state-of-the-art model checkers. In this paper, we demonstrate that reachability properties of FTDAs can be verified by bounded model checking. To ensure completeness, we need an upper bound on the distance between states. We show that the diameters of accelerated counter systems of FTDAs, and of their counter abstractions, have a quadratic upper bound in the number of local transitions. Our experiments show that the resulting bounds are sufficiently small to use bounded model checking for parameterized verification of reachability properties of several FTDAs, some of which have not been automatically verified before. (C) 2016 The Authors. Published by Elsevier Inc. This is an open access article under the CC BY license.

关键词： Model checking fault-tolerant distributed algorithms Byzantine faults Computational models

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：