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||URI:||http://hdl.handle.net/123456789/658|
|Appears in Programs:||0612 Computer Engineering|
Show full item record
checked on Nov 17, 2019
checked on Nov 17, 2019
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.