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

asynchronous approximate Byzantine consensus: A multi-hop relay method and tight graph conditions

AUTOMATICA 2025年 171卷

作者： Yuan, Liwei Ishii, Hideaki Hunan Univ Coll Elect & Informat Engn Changsha 410082 Peoples R China Univ Tokyo Dept Informat Phys & Comp Tokyo 1138656 Japan

We study a multi-agent resilient consensus problem, where some agents are of the Byzantine type and try to prevent the normal ones from reaching consensus. In our setting, normal agents communicate with each other asynchronously over multi-hop relay channels with delays. To solve this asynchronous Byzantine consensus problem, we develop the multi-hop weighted mean subsequence reduced (MWMSR) algorithm. The main contribution is that we characterize a tight graph condition for our algorithm to achieve Byzantine consensus, which is expressed in the novel notion of strictly robust graphs. We show that the multi-hop communication is effective for enhancing the network's resilience against Byzantine agents. As a result, we also obtain novel conditions for resilient consensus under the malicious attack model, which are tighter than those known in the literature. Furthermore, the proposed algorithm can be viewed as a generalization of the conventional flooding-based algorithms, with less computational complexity. Lastly, we provide numerical examples to show the effectiveness of the proposed algorithm. (c) 2024 The Authors. Published by Elsevier Ltd. This is an open access article under the CC BY-NC license

关键词： Byzantine consensus asynchronous distributed algorithms Cyber-security Multi-hop communication

来源：评论

学校读者我要写书评

暂无评论

distributed Detection of Minimum Cuts in Wireless Multi-Hop Networks

引用

IEEE TRANSACTIONS ON COMPUTERS 2022年第4期71卷 919-932页

作者： Akram, Vahid Khalilpour Ege Univ Int Comp Inst TR-35040 Izmir Turkey

Communicating over multi-hop connections simplifies the establishment of wireless multi-hop networks but brings new challenges such as limited reliability, bottlenecks, and weak connections. The minimum cut of a graph is the smallest subset of edges whose removal disconnects some nodes from the others. Finding minimum cuts of a wireless multi-hop network may reveal useful information such as bottlenecks and critical areas. This article introduces a distributed algorithm for detecting minimum cuts of a given witless multi-hop network by finding available edge-disjoint paths. Initially, the paths between two arbitrary neighbors are detected and these nodes are grouped as visited nodes. Then, the other nodes are added to the visited group one by one by finding at most O(n) paths in total where n is the number of nodes. The comprehensive simulation results showed that the proposed asynchronous algorithm detects minimum cuts with up to 37.1 and 55.8 percent lower sent bytes than the existing synchronous and central algorithms, respectively.

关键词： asynchronous distributed algorithms minimum cut wireless multi-hop networks topology control fault fault tolerance

来源：评论

学校读者我要写书评

暂无评论

An asynchronous distributed Algorithm for Minimum s - t Cut Detection in Wireless Multi-hop Networks

引用

AD HOC NETWORKS 2020年 101卷 102092-000页

作者： Akram, Vahid Khalilpour Izmir Bakircay Univ Dept Comp Engn Izmir Turkey

Stable communication is a vital and challenging requirement in wireless multi-hop networks because nodes failure may disconnect other active nodes. Minimum s-t cuts can help to measure the reliability of a network regarding the nodes or links failure. A minimum s-t cut is the smallest subset of links that their failure disconnects all communication paths between nodes s and t. Minimum s-t cuts can also reveal the bottlenecks, bridges, and clusters in the network. This paper proposes an asynchronous distributed algorithm for finding minimum s-t cuts in wireless multi-hop networks. The proposed algorithm iteratively finds link-disjoint paths from s to t and changes the direction of the selected edges to ignore them in the next iteration. After finding all paths, the undiscovered nodes in the last search determine the minimum s-t cut. The comprehensive simulation results on different networks with up to 500 nodes show that the proposed algorithm finds minimum s-t cuts in reasonable time with up to 64% and 39% lower energy consumption than the existing central and distributed algorithms, respectively. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Wireless Multi-hop Networks Minimum s-t Cut Fault Tolerance asynchronous distributed algorithms Cut Edge

来源：评论

学校读者我要写书评

暂无评论

Partially ordered distributed computations on asynchronous point-to-point networks

引用

PARALLEL COMPUTING 2009年第1期35卷 12-28页

作者： Correa, Ricardo C. Barbosa, Valmir C. Univ Fed Ceara Dept Computacao BR-60455760 Fortaleza CE Brazil Univ Fed Rio de Janeiro Programa Engn Sistemas & Computacao COPPE BR-21941972 Rio De Janeiro Brazil

asynchronous executions of a distributed algorithm differ from each other due to the nondeterminism in the order in which the messages exchanged are handled. In many situations of interest, the asynchronous executions induced by restricting nondeterminism are more efficient, in an application-specific sense, than the others. In this work, we define partially ordered executions of a distributed algorithm as the executions satisfying some restricted orders of their actions in two different frameworks, those of the so-called event- and pulse-driven computations. The aim of these restrictions is to characterize asynchronous executions that are likely to be more efficient for some important classes of applications. Also, an asynchronous algorithm that ensures the occurrence of partially ordered executions is given for each case. Two of the applications that we believe may benefit from the restricted nondeterminism are backtrack search, in the event-driven case. and iterative algorithms for systems of linear equations. in the pulse-driven case. We provide some experimental evidence in these two cases. (c) 2008 Elsevier B.V. All rights reserved.

关键词： Synchronous distributed algorithms asynchronous distributed algorithms Partially synchronous distributed algorithms distributed backtrack search Systems of linear equations Partial orders

来源：评论

学校读者我要写书评

暂无评论

Worm-IT -: A wormhole-based intrusion-tolerant group communication system

引用

JOURNAL OF SYSTEMS AND SOFTWARE 2007年第2期80卷 178-197页

作者： Correia, Miguel Neves, Nuno Ferreira Lung, Lau Cheuk Verissimo, Paulo Univ Lisbon Fac Ciencias Dept Informat P-1749016 Lisbon Portugal Pontificia Univ Catolica Parana Programa Posgrad Informat Aplicada BR-80215901 Curitiba Parana Brazil

This paper presents Worm-IT, a new intrusion-tolerant group communication system with a membership service and a view-synchronous atomic multicast primitive. The system is intrusion-tolerant in the sense that it behaves correctly even if some nodes are corrupted and become malicious. It is based on a novel approach that enhances the environment with a special secure distributed component used by the protocols to execute securely a few crucial operations. Using this approach, we manage to bring together two important features: Worm-IT tolerates the maximum number of malicious members possible;it does not have to detect the failure of primary-members, a problem in previous intrusion-tolerant group communication systems. (C) 2006 Elsevier Inc. All rights reserved.

关键词： Byzantine fault tolerance intrusion tolerance group communication view synchrony asynchronous distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

asynchronous Recommendation Systems

Asynchronous Recommendation Systems

引用

16th Annual ACM Symposium on Principles of distributed Computing

作者： Awerbuch, Baruch Nisgav, Aviv Patt-Shamir, Boaz Johns Hopkins Univ Dept Comp Sci Baltimore MD 21218 USA

ISBN: (纸本)9781595936165

Motivation. Recommendation systems are an important ingredient of modern life, where people must make decisions with partial information [6]. Everyday examples include buying books, going to a movie, choosing an on-line store etc. Computer-related examples include, among others, choosing peers in a potentially hostile peer-to-peer environment, or choosing a route in an unreliable network. The basic idea underlying such systems is that users can use the experience reported by others so as to improve their prediction of their own opinions. However, users may differ in their opinions either because they have different tastes, or because their objectives may be different (e.g., in a peer-to-peer network some users may wish to destroy the system). Obviously, only users who share preferences (said to belong to the same type) are can enjoy the advantages of recommendation systems. Copyright © 2007 ACM.

关键词： Recommender systems asynchronous distributed algorithms collaborative filtering

来源：评论

学校读者我要写书评

暂无评论

Solving maximum independent set by asynchronous distributed Hopfield-type neural networks

引用

RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS 2006年第2期40卷 371-388页

作者： Grossi, Giuliano Marchi, Massimo Posenato, Roberto Univ Milan Dipartimento Sci Informaz I-20135 Milan Italy Univ Verona Dipartimento Informat I-37134 Verona Italy

We propose a heuristic for solving the maximum independent set problem for a set of processors in a network with arbitrary topology. We assume an asynchronous model of computation and we use modified Hopfield neural networks to find high quality solutions. We analyze the algorithm in terms of the number of rounds necessary to find admissible solutions both in the worst case (theoretical analysis) and in the average case (experimental Analysis). We show that our heuristic is better than the greedy one at 1% significance level.

关键词： max independent set hopfield networks asynchronous distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

Highly concurrent group mutual exclusion algorithms based on ticket orders

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2004年第2期E87D卷 322-329页

作者： Takamura, M Igarashi, Y Gunma Univ Dept Comp Sci Kiryu Gumma 3768515 Japan

Group mutual exclusion is an interesting generalization of the mutual exclusion problem. This problem was introduced by Joung, and some algorithms for the problem have been proposed by incorporating mutual exclusion algorithms. Group mutual exclusion occurs naturally in a situation where a resource can be shared by processes of the same group, but not by processes of a different group. It is also called the congenial talking philosophers problem. In this paper we propose two algorithms based on ticket orders for the group mutual exclusion problem on the asynchronous shared memory model. These algorithms are some modifications of the Bakery algorithm. They satisfy lockout freedom and a high degree of concurrency performance. Each of these algorithms uses single-writer shared variables together with two multi-writer shared variables that are never concurrently written. One of these algorithms has another desirable property, called smooth admission. By this property, during the period that the resource is occupied by the leader (called the chair), a process wishing to join the same group as the leader's group can be granted use of the resource in constant time.

关键词： asynchronous distributed algorithms concurrency congenial talking philosophers group mutual exclusion shared memory

来源：评论

学校读者我要写书评

暂无评论

The concept of "stability" in asynchronous distributed decision-making systems

引用

IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS PART B-CYBERNETICS 2000年第4期30卷 549-561页

作者： Lee, TS Ghosh, S Vitria Technol Sunnyvale CA 94086 USA Arizona State Univ Dept Comp Sci & Engn Tempe AZ 85287 USA

asynchronous distributed decision-making (ADDM) systems constitute a special class of distributed problems and are characterized as large, complex systems wherein the principal elements are the geographically dispersed entities that communicate among themselves, asynchronously, through message passing and are permitted autonomy in local decision making. Such systems generally offer significant advantages over the traditional, centralized algorithms in the form of concurrency, scalability, high throughput, efficiency, low vulnerability to catastrophic failures, and robustness. A fundamental property of ADDM systems is stability that refers to their behavior under representative perturbations to their operating environments, given that such systems are intended to be real, complex, and to some extent, mission-critical, and are subject to unexpected changes in their operating conditions. This paper introduces the concept of stability in ADDM systems and proposes an intuitive yet practical and usable definition that is inspired by those used in control systems and physics. An ADDM system is defined as a stable system if it returns to a steady state in finite time, following perturbation, provided that it is initiated in a steady state. Equilibrium or steady state is defined through placing bounds on the measured error in the system. Where the final steady state is equivalent to the initial one, a system is referred to as strongly stable, If the final steady state is potentially worse then the initial one, a system is deemed marginally stable. When a system fails to return to steady state following the perturbation, it is unstable. The perturbations are classified as either changes in the input pattern or changes in one or more environmental characteristics of the system, such as hardware failures. For a given ADDM system, the definitions are based on the performance indices that must be judiciously identified by the system architect and are likely to be unique. To facil

关键词： asynchronous distributed algorithms catastrophic failure complexity decision making instability performance reliability stability

来源：评论

学校读者我要写书评

暂无评论

On the concept of "stability" in asynchronous distributed decision-making systems

引用

IEICE TRANSACTIONS ON COMMUNICATIONS 2000年第5期E83B卷 1023-1038页

作者： Lee, TS Ghosh, S Vitria Technol Sunnyvale CA 94086 USA Arizona State Univ Dept Comp Sci & Engn Tempe AZ 85287 USA

asynchronous, distributed, decision-making (ADDM) systems constitute a special class of distributed problems and are characterized as large, complex systems wherein the principal elements are the geographically-dispersed entities that communicate among themselves, asynchronously, through message passing and are permitted autonomy in local decisionmaking. A fundamental property of ADDM systems is stability that refers to their behavior under representative perturbations to their operating environments, given that such systems are intended to be real, complex, and to some extent, mission critical systems, and are subject to unexpected changes in their operating conditions. ADDM systems are closely related to autonomous decentralized systems (ADS) in the principal elements, the difference being that the characteristics and boundaries of ADDM systems are defined rigorously. This paper introduces the concept of stability in ADDM systems and proposes an intuitive yet practical and usable definition that is inspired by those used in Control Systems and Physics. A comprehensive stability analysis on an accurate simulation model will provide the necessary assurance, with a high level of confidence, that the system will perform adequately. An ADDM system is defined as a stable system if it returns to a steady-state in finite time, following perturbation, provided that it is initiated in a steady-state. Equilibrium or steady-state is defined through placing bounds on the measured error in the system. Where the final steady-state is equivalent to the initial one, a system is referred to as strongly stable. If the final steady-state is potentially worse then the initial one, a system is deemed marginally stable. When a system fails to return to steady-state following the perturbation, it is unstable. The perturbations are classified as either changes in the input pattern or changes in one or more environmental characteristics of the system such as hardware failures. Thus, the ke

关键词： stability instability reliability catastrophic failure performance asynchronous distributed algorithms complexity decision-making

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：