Cookies

We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.

Durham University

Research & business

Research lectures, seminars and events

The events listed in this area are research seminars, workshops and lectures hosted by Durham University departments and research institutes. If you are not a member of the University, but  wish to enquire about attending one of the events please contact the organiser or host department.


 

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

Presented by Amitabh Trehan, Loughborough University
12 November 2019 13:00 in E245

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