4 August 2020 – NUS Computing Dean’s Chair Associate Professor Yu Haifeng won the Best Paper Award at the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2020), held online from 14 to 16 July 2020.
A/P Yu and his co-author, NUS Computer Science PhD student Irvan Jahja, won the award for their paper, titled ‘Sublinear Algorithms in T-interval Dynamic Networks’.
The paper, which was presented online to conference participants, considers a number of fundamental distributed computing problems in T-interval dynamic networks.
Distributed computing is an area of research that focuses on systems comprised of multiple computers (or computational devices) that communicate via a network. Dynamic networks, meanwhile, refer to computer networks whose network topology can change over time.
Prior to this, algorithms solving several fundamental distributed computing problems all have time complexity – roughly, the amount of time it takes to run an algorithm – that increases linearly with the number of nodes in the dynamic network. This makes these algorithms inefficient when there is a large number of nodes.
A/P Yu’s paper tackles these distributed computing problems by developing a novel framework for designing algorithms in dynamic networks. This framework is based on the idea of massively parallel aggregation, which refers to simultaneous aggregation along numerous network paths, all done in parallel. Using this framework, the paper proposes novel algorithms for solving these distributed computing problems.
These novel algorithms are the first such algorithms whose time complexity do not linearly depend on the number of nodes in the network, explained A/P Yu.
