Possibility and the Impossibility of Premature Feedback Safety in Broadcast (Prof. Mehmet Hakan Karaata)

A 1-Safe and Reliable Broadcast Algorithm in the Presence of Arbitrary Initialization
Propagation safety and reliability are key components of command-and-control systems, defence and security mechanisms, and secure network protocols in distributed systems. Propagation safety is defined as the broadcast of only legitimate source-based messages, while propagation reliability, refers to the receipt of the legitimate message by all system processes, and may include the message receipt notifications by all processes to the receiver over a finite time. Propagation safety is a property of broadcast algorithms and refers to the propagation of only those messages which have been sent by an actual source. While propagation reliability refers to a message broadcast to all system processes with exact once semantics, and it may additionally guarantee that all system processes eventually inform the source of the broadcast completion.
In this thesis, we first prove that it is not possible to develop an asynchronous reliable broadcast algorithm that is capable of starting in an arbitrary initial system configuration where processes execute their actions solely using local knowledge. Then we propose the first asynchronous reliable broadcast algorithm which is capable of starting in any arbitrary initial system configuration while ensuring three properties, namely, premature feedback safety, propagation 1-safety, and propagation reliability. Due to possessing premature feedback safety property, the proposed algorithm always executes as per its specification without premature feedback and is able to implement propagation reliability with exact once semantics. The proposed broadcast algorithm has a time complexity of O(D^2), where the communication network diameter is denoted by D.

Supervisor: Prof. Mehmet Hakan Karaata
Convener: Prof. Anwar Al-yatama
Examination Committee: Prof. Anwar Al-yatama, Prof. Mahmoud Ben Naser