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

Self-stabilizing c-wave algorithms for arbitrary networks

COMPUTING 2023年第1期105卷 53-88页

作者： Karaata, Mehmet Hakan Alrashed, Ebrahim Allaho, Mohammad Kuwait Univ Dept Comp Engn 13060 POB 5969 Safat Kuwait

In this paper, we propose the first self-stabilizing c-wave algorithm for broadcasting large size messages from multiple initiator processes such that every process receives at least one of these messages broadcast by the initiators. The proposed algorithm first splits each message into a sequence of message shares and then broadcasts the message shares in a pipelined manner in order. We then present an improved maximally concurrent self-stabilizing c-wave algorithm called dynamic clusteringc-wavealgorithm that constructs dynamic broadcast trees by allowing a process to dynamically change its parent to a neighbouring process with the most message shares to implement a maximally concurrent broadcasting of large size messages. The improved algorithm is maximally concurrent in the sense that a process is allowed to receive a message share from any neighbouring process with a larger sequence of message shares than its current parent from which it receives message shares in the broadcast trees constructed by the initiators when available. We implemented and experimentally evaluated the c-wave algorithm to compare its message propagation delay to those of the m and the k-wave algorithms. Simulation results show that the proposed algorithm significantly reduces the broadcast propagation delays compared to that of the m and the k-wave algorithms. The improvement is more evident over the m-wave algorithm. Solutions to global-snapshots, distributed broadcast and various synchronization problems can be solved efficiently using c-wave algorithms. In addition, the proposed algorithms have applications in blockchain, mobile wireless sensor networks, VANETs and military communication networks.

关键词： c-wave Distributed computing Multi-node broadcast m-wave Self-stabilization wave algorithms

来源：评论

学校读者我要写书评

暂无评论

A reliable concurrent multicast algorithm for content distribution

引用

JOURNAL OF SUPERCOMPUTING 2022年第8期78卷 10542-10574页

作者： Karaata, Mehmet Hakan Dabees, Aysha Alazemi, Fawaz Kuwait Univ Dept Comp Engn POB 5969 Safat 13060 Kuwait Kuwait Univ Dept Comp Sci POB 5969 Safat 13060 Kuwait

Rapid growth in the number of users, devices and applications and infrastructures generating and demanding massive amount of content traffic on the Internet has necessitated the available network infrastructures to evolve to cope up with the ever increasing content traffic. One of the approaches in reducing the content traffic and increasing the network throughput is the paradigm of multicast. Multicast is a one-to-many wave scheme for content distribution from a source to all or a large number of destinations. In this paper, we propose the first novel reliable concurrent content multicast algorithm, referred to as a CD-wave algorithm, for concurrent distribution of content from some or all peers to all other network peers. The proposed algorithm synchronises concurrent multicasts in sharing network resources while providing the desirable properties of self- and snap-stabilization. Concurrent mulicasts from different sources are synchronized so that multiple multicasts use each network channel mutually exclusively while ensuring that each multicast eventually succeeds to deliver its content to all system peers. Due to being reliable, each multicast content is guaranteed to be received by all system peers exactly once regardless of the arbitrary initial system configuration in the presence of potentially n - 1 other multicasts competing for network resources where n denotes the number of peers in the network. The snap-stabilization property of our proposed algorithm facilitates the reliability property by ensuring that content distribution proceeds as per its specification to reach all system peers without backtracking after starting in an arbitrary initial configuration.

关键词： Content-distribution Multicast Snap-stabilization Self-stabilization Synchronization wave algorithms

来源：评论

学校读者我要写书评

暂无评论

A Snap-Stabilizing m-wave Algorithm for Tree Networks

引用

COMPUTER JOURNAL 2020年第2期63卷 220-238页

作者： Karaata, Mehmet Hakan Almutairi, Anwar Nais Kuwait Univ Dept Comp Engn POB 5969 Safat 13060 Kuwait

In this paper, we propose the first efficient, reliable and safe snap-stabilizing - (multi-initiator wave) algorithm implementing concurrent waves started by multiple initiator processes in tree networks. Unlike its self-stabilizing counterpart and broadcast algorithms, the proposed algorithm is a reliable and safe m-wave algorithm, i.e. it implements an m-wave such that after it is started in an arbitrary initial configuration or after faults, the first m-wave started is guaranteed to reach all system processes as per its specification. In addition, the proposed m-wave algorithm increases the efficiency of the broadcast compared to a 1-wave algorithm by allowing the broadcast to be initiated by multiple processes. Our proposed algorithm is safe in the sense that after initiating an m-wave, it completes as per the specifications. Additionally, it is reliable as the algorithm guarantees that each process receives at least one broadcast from an initiator process. Furthermore, the proposed algorithm significantly reduces the broadcast completion time compared to that of its single counterparts. Solutions to global-snapshots, distributed broadcast and various synchronization problems can be solved efficiently using waves with multiple concurrent initiators. In addition, the proposed algorithm has applications in mobile wireless sensor networks, VANETs and military communication networks.

关键词： distributed computing multi-node broadcast m-wave algorithms propagation of information with feedback and cleaning (PFC) snap-stabilization wave algorithms

来源：评论

学校读者我要写书评

暂无评论

wave algorithm applied to collective navigation of robotic swarms

引用

APPLIED SOFT COMPUTING 2017年 57卷 698-707页

作者： Silva Junior, Luneque Nedjah, Nadia Univ Fed Rio de Janeiro Rio De Janeiro Brazil Univ Estado Rio De Janeiro Rio De Janeiro Brazil

In swarm robotics, it is necessary to develop methods and strategies that guide the collective execution of tasks by the robots. The design of such tasks can be done considering it as a collection of simpler behaviors, called subtasks. In this paper, the wave Swarm is presented as a general strategy to manage the sequence of subtasks that compose the collective navigation, which is an important task in swarm robotics. The proposed strategy is based mainly on the execution of wave algorithms. The swarm is viewed as a distributed system, wherein the communication is achieved by message passing among robot's neighborhood. Message propagation delimits the start and end of each subtask. Simulations are performed to demonstrate that controlled navigation of robot swarms/clusters is achieved with three subtasks, which are recruitment, alignment and movement. The performance of the proposed strategy regarding the time spent in the two first subtasks is analyzed. Furthermore, the simulations of the navigation in different environments including obstacles are presented and discussed. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Swarm robotics wave algorithms Collective navigation Subtask sequentialization

来源：评论

学校读者我要写书评

暂无评论

An open modal stabilizing m-wave algorithm for arbitrary networks

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2019年 128卷 15-29页

作者： Karaata, Mehmet Hakan Kuwait Univ Dept Comp Engn POB 5969 Safat 13060 Kuwait

A system that operates in multiple input and corresponding operational modes depending on external input is referred to as an open modal (multi-mode) system. An input mode refers to a particular type and pattern of input whereas an operational mode refers to the operational semantics or the specification implemented by an algorithm. An open modal stabilizing system can operate in multiple operational modes and, eventually enters an operational mode depending on its current input mode. Such a system can be viewed as a generalization of the closed single-mode stabilizing systems that do not receive external input and implement a single operational mode upon entering a legitimate configuration. A wave is a distributed execution, often made up of a broadcast phase followed by a feedback phase, requiring the participation of all the system processors before a particular event called decision is taken. wave algorithms with one initiator such as the 1-wave algorithm (Bui et al., 1999) have been shown to be very efficient for broadcasting messages in networks. However as the network size increases, having a single initiator adversely affects the message delivery times to nodes further away from the initiator. As a remedy, broadcast waves can be initiated by multiple initiator nodes forming a collection of waves covering the entire network to reduce the completion times of broadcasts. Solutions to global-snapshots, distributed broadcast and various synchronization problems can be solved efficiently using waves with multiple concurrent initiators (Prakash and Singhal, 1994). In this paper, we propose the first open modal stabilizing m-wane (multi-initiator wave) algorithm implementing concurrent waves started by multiple initiator processors. An m-wave is an execution in which a (non-empty) set of processors initiate broadcasts such that each processor in the network receives a broadcast that was initiated in the current m-wave. A broadcast is said to be initiated by a proces

关键词： Multi-node broadcast m-wave algorithms Modal systems Open systems Stabilization wave algorithms

来源：评论

学校读者我要写书评

暂无评论

Optimal snap-stabilizing PIF algorithms in un-oriented trees

引用

JOURNAL OF HIGH SPEED NETWORKS 2005年第2期14卷 185-200页

作者： Cournier, A Datta, AK Petit, F Villain, V Univ Picardie CNRS FRE 2733 LaRIA F-80025 Amiens France Univ Nevada Dept Comp Sci Las Vegas NV 89154 USA

A snap-stabilizing protocol, starting from any arbitrary initial system configuration, always behaves according to its specification. In other words, a snap-stabilizing protocol is a self-stabilizing protocol which stabilizes in zero steps. In this paper, we first prove the number of states required on processors to design a snap-stabilizing Propagation of Information with Feedback (PIF) algorithm in arbitrary un-oriented trees running under any distributed daemon (four states per processor for the middle processors and two states for each of the two extreme end processors). Then, we propose two snap-stabilizing PIF algorithms for un-oriented trees. The former works under any (fair or unfair, central or distributed) daemon. It matches the lower bound in terms of number of states we established in this paper. The latter works under any (fair or unfair) central daemon. It uses only three states for the internal processors (two states for the root and the leaves). It is optimal in terms of number of states assuming a central daemon. Thus, both algorithms are optimal both in terms of the stabilization time (zero steps) and state requirement per processor.

关键词： distributed systems fault-tolerance PIF self-stabilization snap-stabilization wave algorithms

来源：评论

学校读者我要写书评

暂无评论

Snap-stabilizing depth-first search on arbitrary networks

引用

COMPUTER JOURNAL 2006年第3期49卷 268-280页

作者： Cournier, A Devismes, S Petit, F Villain, V Univ Picardie CNRS FRE 2733 LaRIA Amiens France

A snap-stabilizing protocol, starting from any arbitrary initial configuration, always behaves according to its specification. In this paper, we present the first snap-stabilizing depth-first search wave protocol for arbitrary rooted networks assuming an unfair daemon, i.e. assuming the weakest scheduling assumption (a preliminary version of this work was presented in OPODIS 2004, 8th International Conference on Principles of Distributed Systems, Grenoble (France)).

关键词： distributed systems fault-tolerance stabilization depth-first search wave algorithms

来源：评论

学校读者我要写书评

暂无评论

An optimal snap-stabilizing multi-wave algorithm

引用

COMPUTER JOURNAL 2007年第3期50卷 332-340页

作者： Bein, Doina Datta, Ajoy K. Karaata, Mehmet Hakan Kuwait Univ Dept Comp Engn Kuwait 13060 Kuwait Univ Nevada Sch Comp Sci Las Vegas NV 89154 USA Univ Texas Erik Jonsson Sch Engn & Comp Sci Richardson TX 75083 USA

Synchronization is an important task in distributed computing since it allows asynchronous systems to simulate synchronous ones. Synchronization among distributed processes can be implemented using waves. A wave is a distributed execution, often made up of a broadcast phase followed by a feedback phase, requiring the participation of all the system processes before a particular event called decision is taken. waves consisting of consecutive distinct broadcasts with corresponding feedbacks are referred to as a multi-wave. Solutions to a large number of fundamental problems in distributed computing such as distributed reset [1] and multiphase stabilization [10] require the completion of multi-waves. In this article, we propose a time and state-space optimal snap-stabilizing multi-wave algorithm implementing k distinct consecutive waves (k > 2) in a rooted tree, with O(kh) rounds of delay and at most k + 4 states per process, where h is the height of the tree. A system is said to be snap-stabilizing if it always behaves according to its specification [13]. One of the main advantages of the multi-wave algorithm being snap-stabilizing is that the arbitrary initial configuration has limited or no effect on the pace of the broadcast propagation.

关键词： distributed computing fault tolerance phase clocks propagation of information with feedback and cleaning (PFC) self-stabilization snap-stabilization wave algorithms

来源：评论

学校读者我要写书评

暂无评论

Snap-stabilization and PIF in tree networks

引用

DISTRIBUTED COMPUTING 2007年第1期20卷 3-19页

作者： Bui, Alain Datta, Ajoy K. Petit, Franck Villain, Vincent Univ Picardie LaRIA CNRS Amiens France Univ Reims CReSTIC Reims France Univ Nevada Sch Comp Sci Las Vegas NV 89154 USA

The contribution of this paper is threefold. First, we present the paradigm of snap-stabilization. A snap-stabilizing protocol guarantees that, starting from an arbitrary system configuration, the protocol always behaves according to its specification. So, a snap-stabilizing protocol is a time optimal self-stabilizing protocol (because it stabilizes in 0 rounds). Second, we propose a new Propagation of Information with Feedback (PIF) cycle, called Propagation of Information with Feedback and Cleaning (PFC). We show three different implementations of this new PIF. The first one is a basic PFC cycle which is inherently snap-stabilizing. However, the first PIF cycle can be delayed O(h(2)) rounds (where h is the height of the tree) due to some undesirable local states. The second algorithm improves the worst delay of the basic PFC algorithm from O(h(2)) to 1 round. The state requirement for the above two algorithms is 3 states per processor, except for the root and leaf processors that use only 2 states. Also, they work on oriented trees. We then propose a third snap-stabilizing PIF algorithm on un-oriented tree networks. The state requirement of the third algorithm depends on the degree of the processors, and the delay is at most h rounds. Next, we analyze the maximum waiting time before a PIF cycle can be initiated whether the PIF cycle is infinitely and sequentially repeated or launch as an isolated PIF cycle. The analysis is made for both oriented and un-oriented trees. We show or conjecture that the two best of the above algorithms produce optimal waiting time. Finally, we compute the minimal number of states the processors require to implement a single PIF cycle, and show that both algorithms for oriented trees are also (in addition to being time optimal) optimal in terms of the number of states.

关键词： fault-tolerance optimality self-stabilization snap-stabilization wave algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient Strategy for Collective Navigation Control in Swarm Robotics

Efficient Strategy for Collective Navigation Control in Swar...

引用

16th Annual International Conference on Computational Science (ICCS)

作者： Silva Junior, Luneque Nedjah, Nadia Univ Fed Rio de Janeiro Rio De Janeiro RJ Brazil Univ Estado Rio De Janeiro Rio De Janeiro RJ Brazil

关键词： Swarm Robotics wave algorithms Collective Navigation Task Sequentialization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：