04 January 2019 Department of Computer Science , Faculty , Systems & Networking , Algorithms & Theory

4 January 2019 – Dean’s Chair Associate Professor Seth Gilbert and his collaborators received the Best Paper Award at the 22nd International Conference on Principles of Distributed Systems (OPODIS) on 19 December 2018.

OPODIS is an open forum for the exchange of state-of-the-art knowledge concerning distributed computing and distributed computer systems. The 2018 conference was held from 17 to 19 December in Hong Kong. A total of 28 papers were accepted at the conference, with two papers receiving the Best Paper and the Best Student Paper awards.

A/P Gilbert and his team won the coveted award for their paper on backoff protocols. “A backoff protocol is a simple approach for sharing a resource. If you want to use a resource but it is busy, the protocol backs you off to wait a little while before trying again,” explained A/P Gilbert. “In general, if you carefully fine tune the protocol, you can get an efficient resource usage. Backoff protocols are used quite frequently—wherever there is a shared resource.”

The paper, “On Simple Back-Off in Unreliable Radio Networks”, investigated why backoff protocols are successful in practice despite negative results from theory and research. “In practice, backoff protocols work great, even in dynamic, constantly changing real-world networks. Yet theory shows that they should work quite poorly in dynamic networks. Why the difference? That is the question we wanted to answer,” said A/P Gilbert.

In the course of their study, A/P Gilbert and his team were able to solve the mystery through analysing wireless network changes in two different paradigms – fast fading and slow fading. “Fast fading captures changes that occur fairly randomly and on a very short time scale, such as noise and interference,” said A/P Gilbert. “Slow fading, on the other hand, captures changes that are not random and happen on a longer time scale, like a user walking away from the room.”

With this new constraints, when the team conducted their analysis on backoff protocols, they were able to match the reality of what they see and prove that backoff protocols could work well. “What I liked about our paper is that it shows that theoretical work can help explain and give a deeper understanding for why a given algorithm or approach does or does not work,” said A/P Gilbert.