Algorithms and Complexity (ACiD) Seminar: Sending and Forgetting: Amnesiac Flooding on a Graph

Imagine a network where every user is very aggressive about forwarding the messages they receive (like hyperactive WhatsApp users). The users are polite enough in that they do not send the message back to the users they have just received the message from in the previous round. However, as busy social media users, they quickly forget this interaction and forward the same message if they get it again in the future - potentially circulating the same message till the end of social media civilisation! Consider any arbitrary finite graph modelling such a network and a user who begins the process by flooding (we call this Amnesiac Flooding) one such message. The natural question is will Amnesiac flooding ever stop i.e. will this message stop getting circulated? In general, flooding is about the simplest of distributed algorithms achieving broadcast of messages to all nodes but termination is a critical property to achieve. We analyse both the termination of Amnesiac Flooding and termination times and get somewhat surprising results.

Contact algorithms.complexity@dur.ac.uk for more information