Submitted by Rachel Gardner on Wed, 27/07/2022 - 15:05
A PhD student here is receiving an award this week for the analysis of a model of balanced task allocations that has wide relevance to industry.
Student Dimitrios Los is currently in the third year of his PhD here, working under the supervision of Dr Thomas Sauerwald.
This week he is attending the ACM Symposium on Principles of Distributed Computing (PODC 2022) in Italy. And the paper he is presenting there today, Wednesday 27 July, on Balanced Allocations with the Choice of Noise is receiving the Best Student Paper Award at the conference. Congratulations, Dimitrios and Thomas!
In this paper, which is joint work with his supervisor, Dimitrios conducts a mathematical analysis that extends the 'power of two choices' paradigm in several directions.
The 'two choice paradigm' originates from a simple protocol, developed more than 20 years ago, for allocating a series of balls into a number of bins – or in industry, allocating a series of tasks to a number of servers.
"The balls-and-bins framework (aka balanced allocations) is a popular abstraction for various resource allocation and storage problems such as load balancing, scheduling or hashing," the paper explains. "In order to allocate the balls in an efficient and decentralized way, randomized strategies are usually employed which are based on sampling a number of bins for each ball, and then allocating the ball into one of those bins."
The issue is that distributing the balls into bins purely at random doesn't always work very well. "When there are a very large number of balls, it doesn't produce a very balanced distribution," Dr Sauerwald explains.
A breakthrough came in the mid-1990s when, a group of researchers developed the 'power of two choices' model. Using this model, it was discovered that choosing two bins at random for each ball, instead of just one, and then placing the ball in the bin with the lesser load, brought about an exponential improvement.
This work itself received an award from the ACM in 2020. "Since bins and balls are the basic model for... processes like load balancing of jobs in servers, it is not surprising that the power of two choices that requires only a local decision rather than global coordination has led to a wide range of practical applications," the ACM said.
"These include i-Google's web index, Akamai’s overlay routing network, and highly reliable distributed data storage systems used by Microsoft and Dropbox, which are all based on variants of the power of two choices paradigm. There are many other software systems that use balanced allocations as an important ingredient."
But though the 'two-choice' model offers improvements and has significant relevance for industry, it is a theoretical model that doesn't always reflect a reality where load allocation systems may have to cope with incomplete or inaccurate load information.
"It's usually assumed that we have accurate information about the loading of the bins and how many balls are already in each bin and that there's no room for error," Dr Sauerwald says. "But that's not always the case. So in this paper, the work has been expanded into 'noisy' models."
These include models where there are time delays. "Maybe some balls have just arrived in the queue, but the server hasn't yet realised that they are there or processed them."
He adds, "We also looked at an adversarial model where some kind of adversary or opponent was trying to thwart us by fooling us that Bin A has the smaller load, when in fact it's Bin B that has the smaller load. And we considered a situation where there was a random perturbation of loads."
Dimitrios and his supervisor took these 'noisy' models and ran a tight mathematical analysis on them, including creating a visualiser where different processes with and without noise could be simulated.
And after doing that, they were able to present a general framework of four different classes of noise models that contained both some of the previously studied processes and models and also lead to new settings that were not studied before.
And it's hoped that this line of research can now be taken forward.
"The logical next step for this research is to reach out to practitioners - and to our colleagues, for example here in the Systems and Networking group," Dr Sauerwald says. "And we hope to do that."
