NESTiD Seminars

NESTiD Seminar Coordinator: George Mertzios

Here you can find the links to the dedicated webpages for the NESTiD Seminars and videos from previous years: Past NESTiD Seminars

NESTiD Seminar 2023/24

The seminar talks will be streamed online on zoom. Whenever the speaker is physically present in Durham, the presentation will also be in the room MCS2050 at the MCS building (in addition to zoom streaming). Whenever a speaker is not physically present, all people at Durham are invited to watch the zoom seminar in the above room. Below you can find the list of speakers and talks for the year 2023/24. In the schedule of talks below is in UK time.

NOTE: Please refer to the schedule below for any room changes for some selected talks.

Link for 2023-24 Seminar videos: click here

Term 1 of 2023/24:
(online on zoom)

Date and Time	Talk
Friday 6 Oct 2023 13:00 – 14:00 (Inaugural talk of the NESTiD seminar series)	Petra Berenbrink (University of Hamburg, Germany) On opinion dynamics and phase clocks in the population model (Part 1) In the first part of the talk I will give an overview over recent results about opinion dynamics (voter, undecided state and majority dynamics). in the population model. In the second part I will explain how to use these dynamics for self-stabilizing phase clocks.
Friday 13 Oct 2023 13:00 – 14:00	Petra Berenbrink (University of Hamburg, Germany) On opinion dynamics and phase clocks in the population model (Part 2) This is a sequel talk from the previous week.
Tuesday 17 Oct 2023 11:00 – 12:00 (Please note the UPDATED TIME)	Ravi Mazumdar (University of Waterloo, Canada) Learning while bidding in Vickrey Auctions with acquisition rate and targeting constraints Ad placement in web-browsing and wireless mobiles is an increasingly important component of the advertisement market. The market size is over $ 100 billion and counting. The mechanism is as follows: when a user opens a webpage or mobile ap a message is sent to an exchange where multiple bidders have the possibility of placing an ad that would target the right user, eg. age, sex, location, etc. The ad that is displayed corresponds to the bidder who bids the highest while the cost is calculated according to a first or second price. Typically bidders are DSP (Demand Side Platforms) that aggregate bids on behalf of clients who wish to run a campaign for a given length of time with certain targeting criteria. The goal is to minimize the total cost of obtaining the required number of impressions (ads that meet targeting criteria) over the duration of a contract. The real time constraint is that bidding must be done within 100ms. In this talk I will present the theory developed for computing the least cost bids in the second price or Vickrey auction context. This involves the notion of an information state for the problem. There is a very rich primal-dual theory that emerges, one in the so called impressions space and the other in the contracts space. Computationally and structurally the primal and dual views of the optimization have different properties that can be exploited to come up with fast algorithms. The optimal solutions depend on solving a constrained convex optimization problem when the information state is known. However this is not readily available and thus there is the problem of learning the information state. We show that in the second price case, stochastic approximation (SA) algorithms that operate on censored data (prices are only known by a bidder when the bidder wins) can be devised that solve the constrained optimization problem without learning the information state explicitly and we prove their convergence. Finally I will present the dynamic behaviour through simulations. Joint work with Ryan Kinnear (OpenAI), Amirhossein Boreiri (waterloo) and Peter Marbach (Toronto). We thank Addictive Mobility Inc., a Pelmorex company for having proposed the problem and to Addictive Mobility, Ontario OCE VIP II, and NSERC funding the work.
Friday 27 Oct 2023 13:00 – 14:00
Friday 3 Nov 2023 13:00 – 14:00	Kieran Fernandes (Durham University Business School, UK) Smart Cities [slides-p ptx] [slides-pdf] Cities play an important role in tackling climate change due to human population and the evergrowing pressure on energy usage. My presentation will discuss how cities can respond to the circularity challenge by proposing a social contract model to engage the quadruple stakeholders in developing inclusive, safe, resilient and sustainable cities – which contributes directly to SDGs 8 & 11. We identify the following eight factors that are essential to this social contract and are detailed in this report: Innovation & Technology, People & Human Resources, Wellness, Health, Education & Liveability, Financial Funding, Leadership & Governance, Business Professional ESR, Circular Economy and Energy Net Neutrality. and Atanu Chaudhuri (Durham University Business School, UK) Performance Impact and capabilities needed for Blockchain implementation in Supply Chains: Findings from case studies and econometric modelling [click here for the slides] This presentation is based on Atanu’s recently published qualitative case study research on the role of blockchain in reducing transaction costs, improving quality, risk management and social sustainability across the chain and the capabilities needed to deliver Blockchain implementation projects. Atanu will also talk about the impact of announcements of Blockchain implemenation on stock prices and operating performance based on data of 136 Blockchain implementation projects in the supply chain.
Friday 10 Nov 2023 13:00 – 14:00	Neil Walton (Durham University, UK) Stability Properties of Proportional Fairness and MaxWeight We present results on the stability of MaxWeight and Proportional Fairness, both of which are policies that are readily employed in the analysis of communications systems. MaxWeight is a greedy policy that does not depend on knowledge of arrival rates and is straightforward to implement. We prove that MaxWeight itself is not in general maximally stable in networks where jobs move between queues. We prove MaxWeight is maximally stable in a more restrictive setting, and that a weighted version of MaxWeight, where the weighting depends on the traffic intensity, is always stable. We introduce a scheduling policy for FIFO networks, the Proportional Scheduler, which is based on the proportional fairness criterion. We show that the Proportional Scheduler has a maximal stability region and does not require explicit knowledge of traffic arrival rates. The Proportional Scheduler has the advantage that information about the network’s route structure is not required for scheduling, which substantially improves the policy’s performance for large networks.
Friday 17 Nov 2023 13:00 – 14:00	Paola Flocchini (University of Ottawa, Canada) Distributed Computing by Autonomous Oblivious Mobile Robots In this seminar I will talk about algorithmic and computability issues arising in systems (or “swarms”) of autonomous mobile robots, where the swarm is composed of a large number of identical very-small extremely-simple autonomous computational entities, capable of moving in a spatial universe. The research in this area has focused on the computational and complexity issues arising in such systems, in particular on how “weak” the robots can be while still capable of collectively and autonomously solving possibly complex problem. I will describe the main robots’ model and some of its variants, and I will review some of the results in the field, showing that complex tasks can be performed by such robots even if they are oblivious and incapable of any direct means of communication.
Friday 24 Nov 2023 13:00 – 14:00	Sagnik Mukhopadhyay (University of Sheffield, UK) Alice and Bob Walked into a Graph… [click here for the slides] I will talk about simple algorithms for cut and flow problems in the 2-party communication setting that can be adapted to many other distributed models of computation quickly. In the realm of data explosion, it is usually the case that a single computational processor is unable to store the vast amount of data needed to do any meaningful computation. We are indeed in the era of distributed computing, but it is not ideal to have different ad-hoc ‘model-dependent’ algorithms for solving the same problem. I will show recent progress in designing cross-paradigm algorithms that tackle this issue. I will show two examples: the minimum-cut problem (or min-cut) and the maximum bipartite matching problem (or BMM) where, in each case, a simple schematic algorithm can be implemented in a number of computational models to achieve the optimal complexity. This is a culmination of a number of papers that appeared in the last couple of years with coauthors Joakim Blikstad, Jan van den Brand, Yuval Efron, Troy Lee, Simon Apers, Pawel Gawrychowski, Michal Dory, Andrés López-Martínez and Danupon Nanongkai.
Friday 1 Dec 2023 13:00 – 14:00 This talk is co-organized with the research group Scientific Computing at Durham	Filippo Spiga (NVIDIA) The NVIDIA superchip (Grace-Grace and Grace-Hopper) platform: the ‘what’, the ‘how’, the ‘why’ The purpose of this talk is to introduce the NVIDIA Grace CPU Superchip and NVIDIA Grace Hopper Superchip (CPU+GPU) platforms and how advancements in hardware coupled with NVIDIA’s vision on programming models for accelerated computing can have profound implications in developing next generation fast (time to solution) and efficient (energy to solution) HPC and AI codes.
Friday 8 Dec 2023 13:00 – 14:00	THIS TALK IS CANCELED !!

Term 2 of 2022/23:
(online on zoom)

Friday 12 Jan 2024 13:00 – 14:00	John Augustine (IIT Madras) Byzantine Resilient Gathering of Anonymous Mobile Agents It is well known that deterministic gathering is impossible on graphs when the mobile agents are anonymous. Thankfully, randomization provides us a way out and makes the problem solvable. In this talk, we will discuss how randomization can help us in gathering anonymous mobile agents efficiently. Moreover, we will show how we can design protocols that are resilient against an adversary that can maliciously control a large subset of the mobile agents. This talk is based on joint works with Arnhav Datar and Nischith Shadagopan.
Friday 19 Jan 2024 13:00 – 14:00	Lin Dai (City University of Hong Kong) Random Access for Machine-to-Machine Communications: Connection-based or Connection-free? With the new wave of digital revolution, wireless communication networks are experiencing a radical paradigm shift from the conventional human-to-human (H2H) communications to machine-to-machine (M2M) communications. To facilitate the massive access of machine-type devices, random access is expected to play a crucial role in the next-generation M2M communications. Thanks to its distributed nature, random access has found wide applications to various wireless networks including 5G cellular networks and WiFi networks. In general, random access protocols can be divided into two categories: connection-based or connection-free. The connection-based random access procedure of cellular networks has been long criticized for its low access efficiency for supporting M2M communications, which is mainly attributed to the large overhead of connection establishment. Yet connection-free random access schemes usually suffer from high transmission failure rates, especially in massive access scenarios. The optimal access design for M2M communications requires a fundamental understanding of the performance limits of connection-based and connection-free random access, which will be the focus of this talk. Specifically, I will introduce our recently proposed unified analytical framework for random access, and show how to characterize the optimal throughput and delay performance of connection-based and connection-free random access to develop criteria for beneficial connection establishment. I will conclude the talk by highlighting the practical implications of the analysis to the access design of M2M communications.
Friday 26 Jan 2024 13:00 – 14:00	Bo Wei (Newcastle University, UK) Intelligent Internet of Things In this talk, Dr Bo Wei will introduce his research on the intelligent Internet of Things, which includes two main areas: indoor localization for mobile devices and device-free context awareness using wireless signals. Localization for mobile devices is an important part of many applications. The popular Global Positioning System (GPS)-based localization does not work in indoor environments. The constrained resources of mobile devices also preclude the use of many traditional high-performance methods, e.g., vision-based, laser-based localization systems. To overcome these challenges, we introduce accurate and efficient indoor localization solutions based on data fusion of measurements from Inertial measurement units and other sensors, which achieves sub-meter accuracy. Context awareness is another important component in the pervasive computing area. Device-free context awareness has the advantage that it does not have the privacy concern of using cameras and the subjects do not have to carry a device on them. We take advantage of wireless signals, such as readily available WiFi signals, for device-free localization, activity recognition, and identity recognition.
Friday 2 Feb 2024 13:00 – 14:00	Mutaz Barika (Newcastle University, UK) Toward efficient scheduling of IoT data-driven workflows in cloud environments IoT advancements drive complex applications, analysing data from connected devices for real-time insights in various sectors like smart farming, smart retail, and smart transportation. These applications are categorized as data-driven workflows, integrating multiple analytical components. This workflow application, also known as a stream workflow, is one type of big data workflow application and is gradually becoming viable for solving complex real-time data computation problems. Cloud computing provides resources for stream workflows, but challenges arise from diverse data sources and processing needs. Research primarily focuses on streaming operator graphs generated by streaming data platforms, where this graph differs from a stream workflow as there is a single source of data for the whole operator graph and one end operator, while a stream workflow has multiple input data sources and multiple output streams. While the majority of studies address data fluctuations, they often neglect structural changes. Stream workflows demand advanced scheduling to address the aforementioned challenges, as well as handling different runtime changes that may occur during the execution of these applications. In this talk, we will discuss scheduling techniques to efficiently manage the schedules of these applications over cloud infrastructures, handle application-level changes and data fluctuations, while meeting user real-time data analysis requirements, and minimizing the overall execution cost.
Friday 9 Feb 2024 13:00 – 14:00	Cristina Chueca Del Cerro (Durham University, UK) Networked Polarization: Simulating Social Networks and Online Filter Bubbles An ongoing debate in the political communication literature is regarding the role social media platforms play on the emergence of polarization. Social media’s filter bubbles and online echo chambers shape people’s opinions. However, the extent to which this is the case remains unclear. Social simulation scholars have provided valuable insights into the subject through opinion dynamics models and agent-based modelling approaches. This article proposes a social simulation approach to the topic of opinion dynamics from a political communication perspective to understand how social network configurations and the media environment contribute to the emergence of national identity polarization. We built an agent-based simulation model of national identity dynamics with a multilayer multiplex network of interacting agents in a hybrid media environment of both, traditional media and social media platforms. We use the Catalan secessionist movement to ground, contextualize and empirically inform parts of our model. We found that the initial social network setup conditions had a large impact on the emergence of polarization amongst agents. In particular, homophily-based social networks composed of a majority of like-minded individuals produced greater polarization compared to random networks. This was aggravated in the presence of social media filtering algorithms, selectively exposing agents to supportive information. These results emphasize the importance of both, the selective exposure by social media filtering algorithms and one’s social networks for polarization to emerge. Therefore providing further evidence on how social media platforms and social networks contribute to the emergence of polarization.
Friday 16 Feb 2024 13:00 – 14:00	Ronitt Rubinfeld (MIT, USA, and Tel Aviv University, Israel) Making use of locality in computation Modern networks can be such that complete inputs and outputs for computational problems on them are so large, that there is not time to read or write them in their entirety. However, if one is only interested in small parts of the output at any given time, is it really necessary to solve the entire computational problem? Can one avoid the need to view the whole input? Or, is there a way to take advantage of certain “locality properties” of the problem? We describe recent work in the model of “local computation algorithms” which for a given input, supports queries by a user to values of specified bits of a legal output. The goal is to design local computation algorithms in such a way that very little of the input needs to be seen in order to determine the value of any single bit of the output. Though this model describes sequential computations, techniques from local distributed algorithms have been extremely important in designing efficient local computation algorithms. We survey results on a variety of problems for which sublinear time and space local computation algorithms have been developed.
Friday 23 Feb 2024 13:00 – 14:00	Chhaya Trehan (University of Bristol) Many Short and Lazy Random Walks for Testing the Conductance (expansion) of a Graph in CONGEST Model In this talk I will present a very simple and time-optimal algorithm for testing the conductance of a graph (network) in the CONGEST model of distributed computing. The previously known algorithms for this problem in computing models such as centralized (sequential), MPC and CONGEST run many random walks from a certain set of source nodes, and then apply a global aggregate function on the information pertaining to these walks to check if the input graph has the desired conductance. Specifically in the CONGEST model, the only known algorithm proceeds in three phases. In the first phase it tries to build a rooted BFS spanning tree of the input network. In the second phase, it runs many short lazy random walks from a small number of randomly selected source nodes. Finally in the third phase it aggregates information pertaining to these walks at the root of the spanning tree to decide whether to ‘accept’ or ‘reject’ the input graph. We show in our work that all we need to test the conductance of a graph in the CONGEST model is to simply run an appropriate number of random walks from a small number of source nodes, and at the end of this process each node in the network has enough information to decide whether it is part of a good conductor or not. This completely eliminates the need to collect information at a central node and hence the need to build a rooted spanning tree. The algorithm we will discuss consists of simply running many short and lazy random walks from a certain number of random sources; at the end of which, each node outputs ‘accept’ or ‘reject’ based on how many walks it received from each of the sources. We guarantee that if the input graph indeed has the desired conductance then every node in the network will output ‘accept’ with high probability; and if its is far from it, then at least one node will output reject with high probability. Note that aggregation (using spanning trees) is a popular technique but spanning tree(s) are sensitive to node/edge/root failures, hence, we hope that our work points to other more distributed, efficient and robust solutions for suitable problems in the property testing regime and beyond.
Friday 1 Mar 2024 13:00 – 14:00	Rotem Oshman (Tel Aviv University, Israel) Distributed Certification of Network Properties In distributed certification, our goal is to certify that a network has a certain desired property, e.g., the network is connected, or the internal states of its nodes encode a valid spanning tree of the network. To this end, we store a certificate at each network node, and the nodes can then interact with one another in order to check their certificates, and verify that the property holds. Our goal is to minimize the length of the certificates, the number of rounds the nodes spend interacting with one another at verification time, and the amount of communication. In this talk I will survey the area of distributed certification, and then discuss some recent research directions in the area of distributed certification, such as adding privacy requirements and introducing computational assumptions.
Friday 8 Mar 2024 13:00 – 14:00	Nitin Vaidya (Georgetown University, USA) Fault-Tolerant Distributed Optimization and Learning Consider a network of agents wherein each agent has a private cost function. In the context of distributed machine learning, the private cost function of an agent may represent the “loss function” corresponding to the agent’s local data. The objective here is to identify parameters that minimize the total cost over all the agents. In machine learning for classification, the cost function is designed such that minimizing the cost function should result in model parameters that achieve higher accuracy of classification. Similar problems arise in the context of other applications as well. Our work addresses privacy and security (or fault-tolerance) of distributed optimization with applications to machine learning. In privacy-preserving machine learning, the goal is to optimize the model parameters correctly while preserving the privacy of each agent’s local data. In fault-tolerance, the goal is to identify the model parameters correctly while tolerating adversarial agents that may be supplying incorrect information. When a large number of agents participate in distributed optimization, security compromise of some of the agents becomes increasingly likely. We constructively show that privacy-preserving and secure algorithms for distributed optimization exist. The talk will provide intuition behind these algorithms, with a focus on fault-tolerant algorithms.
Friday 15 Mar 2024 13:00 – 14:00	Roy Friedman (Technion – Israel Institute of Technology) On optimizing deterministic concurrent scheduling for smart contracts and blockchains Executing smart contracts is a compute and storage-intensive task, which currently dominates modern blockchain’s performance. Given that computers are becoming increasingly multicore, concurrency is an attractive approach to improve programs’ execution runtime. A unique challenge of blockchains is that all replicas (minors or validators) must execute all smart contracts in the same logical order to maintain the semantics of replicated state machines. In this talk, I will discuss the maximal level of parallelism obtainable when focusing on the conflict graphs between transactions packaged in the same block, rather than relying on the total ordering order. This includes a novel generic framework for asynchronous state machine replication that is strictly serializable, and introducing the concept of graph scheduling, and the definition of the minimal latency scheduling problem, which we proved to be NP-hard. We showed that the restricted version of this problem for homogeneous transactions is exactly equivalent to the classic graph vertex coloring problem, yet the heterogeneous case is more complex. I will also discuss some practical implications of these results. This is a joint work with Yaron Hay.

Term 3 of 2023/24:
(online on zoom)

Friday 26 Apr 2024
13:00 – 14:00

William (Billy) Moses Jr. (Durham University, UK)
Awake Complexity of Distributed Minimum Spanning Tree
Consider a graph G with n nodes and consider some distributed algorithm designed to be run over G. The awake complexity of a distributed algorithm measures the number of rounds in which a node is awake. When a node is not awake, it is sleeping and does not perform any computation or communication and spends very little resources. Reducing the awake complexity of a distributed algorithm can be relevant in resource-constrained networks such as sensor networks, where saving the energy of nodes is crucial. The awake complexity of many fundamental problems such as maximal independent set, maximal matching, coloring, and spanning trees has been studied recently.

In this work, we study the awake complexity of the fundamental distributed minimum spanning tree (MST) problem and develop the following results:
– A lower bound of \Omega(\log n) on the awake complexity for computing an MST that holds even for randomized algorithms.
– A trade-off lower bound between the awake complexity and the round complexity, in particular we show that any algorithm to solve MST requires the product of its awake and round complexities to be \Tilde{\Omega}(n), where
\Tilde(\Omega) hides a 1/polylog n factor.
– A distributed randomized algorithm to find the MST with optimal awake complexity O(\log n) w.h.p. and round complexity O(n \log n).
– Two distributed deterministic algorithms to find the MST: one with optimal O(\log n) awake complexity and O(n \log^5 n) round complexity and another which sacrifices awake complexity for faster round complexity and takes O(\log n \log^* n) awake complexity and O(n \log n \log^* n) round complexity.
– A parameterized family of distributed algorithms to complement our trade-off lower bound: for integer parameter k, the algorithm takes \Tilde{O}(n/2^k) awake complexity and \Tilde{O}(D + 2^k + n/2^k) round complexity, where D is the network diameter and \Tilde{O} hides a polylog n factor.

Our work is a step towards understanding resource-efficient distributed algorithms for fundamental global problems such as MST. It shows that MST can be computed with any node being awake (and hence spending resources) for only $O(\log n)$ rounds, which is significantly better than the fundamental lower bound of $\Tilde{\Omega}(D + \sqrt{n})$ rounds for MST in the traditional CONGEST model, where nodes can be active for at least so many rounds.

This talk is based on joint work with John Augustine and Gopal Pandurangan which will be presented at SIROCCO 2024.

Friday 3 May 2024
13:00 – 14:00

Fabien Dufoulon (Lancaster University, UK)
On the message complexity of fundamental graph optimization problems
Message complexity (along with time complexity) is a fundamental performance measure of distributed algorithms. Time complexity has been extensively studied, and efficient distributed algorithms with optimal or near-optimal time complexities have been developed in the last few years for fundamental graph optimization problems such as diameter, all-pairs shortest paths (APSP), maximum matching (MaxM), minimum dominating set (MDS) and more.

On the other hand, little was known about the message complexity of these fundamental problems. We close some of the gaps in our knowledge of message complexity and in doing so we show that the message complexity landscape exhibits a somewhat surprising behavior. More precisely, we give some strong message complexity lower bounds for some graph optimization problems (such as MDS)—and these cubic message complexity lower bounds are the first of their kind—whereas for others (such as APSP), we give surprisingly message-efficient distributed algorithms.