‘There is little doubt that the future of computing lies in distribution,’ says Sebastian Brandt. The rapid growth of networks and data sets in recent years confirms his point, as does the complexity of the problems we are trying to solve using the large amount of data collected. Brandt's research has been focussing on so-called distributed computing for years and the question of how this can be made even more efficient, i.e. faster and more resource-efficient. ‘A key concept for greater efficiency is locality, i.e. solving computational problems by ensuring that each network node only obtains information from its immediate environment and does not have to access information from far-flung locations in the network.’ Communication across the network is time-consuming, as each network node - such as a computer or router - can only communicate with its direct neighbours. If distant computers want to exchange information, it takes several rounds of communication and each round takes time.
Locality versus topology
Locality in computer science does not necessarily have to do with the geographical proximity of network nodes. Rather, locality describes the scope of information or interactions that are related to a particular node. What plays a role in locality, however, is the topology of computer networks, i.e. the arrangement of computing nodes and connections. For example, two servers in distant cities, such as Munich and Hamburg, can be connected as part of a corporate network by a fast fibre optic connection and be local neighbours from a topological perspective. Conversely, two computers could be in the same city but in different networks - without a direct connection. Topologically, they would not be local to each other, even if their physical distance is small. The topology of a network also influences the amount of locally available information. For example, a node in a densely networked system has more neighbours and therefore more local information than a node in a sparsely networked system.
Topology-sensitive algorithms are the key
There is another connection between topology and locality that is fundamental to Brandt's research: local algorithms can utilise specific properties of the network topology in order to work more efficiently. This is possible already today for simple tasks. According to Brandt, for example, a social network can make suggestions for new friends to its users by only looking at the existing circle of friends (and thus the direct neighbouring nodes) and suggesting new connections based on this. ‘Unfortunately, it's not as simple as in this example, depending on the complexity of the task and the network,’ explains Brandt. In his ‘OLA-TOPSENS’ project, he therefore wants to gain a fundamental understanding of the usability, but also the limits of the usability of local information and develop efficient topology-sensitive algorithms under the given constraints. ‘These should also be able to be used in complex and growing networks and data sets,’ says the researcher. Brandt is convinced that the utilisation of local information will be useful in many areas of algorithms, such as classic sequential, dynamic, sublinear, streaming and online algorithms. ‘If we succeed in what we are trying to do, we will be able to solve some of the computational problems that have been prevalent for decades,’ says the researcher.
About Sebastian Brandt
Sebastian Brandt has been a senior scientist at CISPA since 2021. He was previously a postdoc in the Discrete and Distributed Algorithms Group at ETH Zurich, where he also completed his doctorate in 2018. In his research, he deals with questions from the field of theoretical computer science, in particular with topics of design and the analysis of algorithms. He is very excited about the ERC Starting Grant. ‘I am delighted and very grateful that this funding will allow me to devote so much time and resources to the research questions I have always wanted to pursue.’
About the ERC
The ERC, set up by the European Union in 2007, is the premier European funding organization for excellent frontier research. It funds creative researchers of any nationality and age, to run projects based across Europe. The ERC offers 4 core grant schemes: Starting Grants, Consolidator Grants, Advanced Grants and Synergy Grants. With its additional Proof of Concept Grant scheme, the ERC helps grantees to explore the innovation potential of their ideas or research results. The ERC is led by an independent governing body, the Scientific Council. Since 1 November 2021, Maria Leptin is the President of the ERC. The overall ERC budget from 2021 to 2027 is more than €16 billion, as part of the Horizon Europe program, under the responsibility of the European Commissioner for Innovation, Research, Culture, Education and Youth, Iliana Ivanova.
