BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Computer Science and Engineering - ECPv6.13.0//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Computer Science and Engineering
X-ORIGINAL-URL:https://homecse.iitd.ac.in
X-WR-CALDESC:Events for Computer Science and Engineering
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:Asia/Kolkata
BEGIN:STANDARD
TZOFFSETFROM:+0530
TZOFFSETTO:+0530
TZNAME:IST
DTSTART:20250101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Kolkata:20251007T120000
DTEND;TZID=Asia/Kolkata:20251007T130000
DTSTAMP:20261012T012927
CREATED:20251005T191731Z
LAST-MODIFIED:20251005T191731Z
UID:2082-1759838400-1759842000@homecse.iitd.ac.in
SUMMARY:Amnesiac Flooding and the curious case of a Unique Algorithm by Amitabh Trehan
DESCRIPTION:Venue: Bharti501 \nAbstract: In the field of distributed algorithm design\, it is often standard to abstract the network as an undirected graph with the nodes as vertices and connections as edges. About the simplest process one can imagine on a network/graph is flooding: A node is in possession of a message M which has to be  eventually sent to every node on the graph (this is called achieving broadcast)- the node sends M immediately to all its neighbours and they send to all their neighbours they did not just receive the message from and so on. Clearly\, this achieves broadcast. But\, how to achieve termination? i.e. the copies of the message should not circulate indefinitely. \n\n\nAt the advent of distributed computing\, more than 50 years ago\, a simple solution was devised – keep a copy of M\, and if M is received again\, simply discard this M. However\, this requires memory/state and a stack of earlier received messages. Surprisingly\, we discovered [PODC2019\,STACS2020\,DC2023] that state is unnecessary to achieve terminating broadcast – the same process without any state or memory beyond the immediate receipt (hence\, called Amnesiac Flooding (AF))\, due to some still slightly mysterious properties of simple undirected graphs\, terminates in asymptotically optimal time on every graph.  Intriguingly\, we have recently discovered [DISC2025] that AF is Unique! i.e. under certain reasonable conditions\, AF is the one and only algorithm that achieves terminating broadcast. Are there other examples of Unique algorithms in literature\, and is counting the number of algorithms for solving a problem a concept we can reasonably postulate? \n\n\nAF on Wikipedia: https://en.wikipedia.org/wiki/Amnesiac_flooding \n\nBio: Amitabh Trehan is an associate professor at the department of Computer Science\, Durham University\, where he heads the NESTiD (Network Engineering\, Science\, and Theory in Durham] research group. He did his PhD in Computer Science from the University of New Mexico\, USA\, following a M.Tech. in Computer Applications from the Indian Institute of Technology\, Delhi.
URL:https://homecse.iitd.ac.in/event/amnesiac-flooding-and-the-curious-case-of-a-unique-algorithm-by-amitabh-trehan/
LOCATION:Bharti 501\, IIT Campus\, Hauz Khas\, New Delhi
END:VEVENT
END:VCALENDAR