Please use this identifier to cite or link to this item:
Title: A Snap-Stabilizing m-wave Algorithm for Tree Networks
Authors: Anwar Nais Al-Mutairi 
Supervisor: Prof.Mehmet Hakan Karaata
Keywords: Snap-Stabilizing : Algorithm
Issue Date: 2017
Publisher:  Kuwait university - college of graduate studies
Abstract: A distributed system is composed of a set of processes connected according to an arbitrary topology. Numerous advantages of distributed systems include fault tolerance, scalability, availability, resource sharing, and concurrency. 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. In most wave algorithms, a wave is initiated by one initiator such as the 1-wave algorithm (?) and 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 forming a collection of waves covering the entire network nodes called an m-wave to reduce the completion times of broadcasts. Problems such as global-snapshots, distributed broadcast and various synchronization problems can be solved efficiently using waves with multiple concurrent initiators (?). A distributed system is referred to as snap-stabilizing if, starting from an arbitrary system configuration, the system that always behaves according to its specification. In particular, a snap-stabilizing algorithm ensures that a wave is guaranteed to reach all network processes. Existing m-wave algorithms are not snap-stabilizing and existing snap-stabilizing wave algorithms are not m-wave algorithms. In this thesis, we propose the first snap-stabilizing m-wave algorithm implementing concurrent waves started by multiple initiator processes in tree networks. An m-wave is an execution in which a (non-empty) set of processes initiate broadcasts such that each process in the network receives a broadcast that was initiated in the current m-wave. Due to being snap-stabilizing, the algorithm always behaves according to its specification, that is, after a delay, every initiated m-wave is completed as per its specification. The proposed algorithm is proved theoretically to be a snap-stabilizing m-wave algorithm
Appears in Programs:0612 Computer Engineering

Files in This Item:
File Description SizeFormat 
Thesis.pdf1,08 MBAdobe PDFView/Open    Request a copy
Show full item record

Page view(s)

Last Week
Last month
checked on Nov 17, 2019


checked on Nov 17, 2019

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.