Please use this identifier to cite or link to this item: http://hdl.handle.net/123456789/658
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
URI: http://hdl.handle.net/123456789/658
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)

8
Last Week
1
Last month
checked on Nov 17, 2019

Download(s)

3
checked on Nov 17, 2019

Google ScholarTM

Check


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