Computer Science Seminar
Computing in the Age of Low Memory
When: Friday, April 12, 2019
Where: PGH 232
Time: 11:00 AM
Speaker: Dr. Amitabh Trehan, Loughborough University, UK
Host: Dr. Gopal Pandurangan, 海角社区
ABSTRACT
We look at the problem of computing in the setting of large networks of low memory - as may possibly be in the setting such as the Internet of Things. We discover a connection between distributed computing and streaming. We formalize this by introducing the Compact Local Streaming model - nodes in an arbitrary network that have low memory (at most O(log^2 n)), even though they support O(n) neighbors and computation happens by 'local streaming' at nodes.
We look at some simple variants of the model and then propose the first self-healing compact routing protocol. Our scheme, based on Thorup and Zwick [SPAA 2001] tree routing scheme and the ForgivingTree [PODC’ 2008] self-healing scheme, is a compact scheme (using at most O(log^2 n) memory per node) that functions despite node failures with only a small additional overhead.
This research was supported by the EPSRC first grant COSHER: Compact Self-Healing Routing
References:
[1] Armando Castañeda, Jonas Lefèvre, Amitabh Trehan, Some Problems in Compact Message Passing - ,
[2] Armando Castañeda, Danny Dolev, Amitabh Trehan: Compact routing messages in self-healing trees. Theoretical Computer Science, 2018,
Bio:
Dr. Amitabh Trehan is an assistant professor of Computer Science at Loughborough University, UK, specialising in algorithms, in particular, distributed and reliable (self-healing) algorithms. He received his PhD from University of New Mexico, USA, followed by postdocs in Canada (Victoria) and Israel (Technion, Hebrew University). He maintains a personal website at and a technical blog at