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, University of Houston

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 - https://arxiv.org/abs/1803.03042,
[2] Armando Castañeda, Danny Dolev, Amitabh Trehan: Compact routing messages in self-healing trees. Theoretical Computer  Science, 2018, https://www.sciencedirect.com/science/article/pii/S0304397516306818?via%3Dihub

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 www.amitabhtrehan.net and a technical blog at www.huntforthetowel.wordpress.com