NESTiD Seminar
NESTiD Seminar
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 2024/25
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 2024/25. 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 2024-25 Seminar videos: click here
Term 1 of 2024/25:
(online on zoom)
| Date and Time | Talk |
|---|---|
| Friday 11 Oct 2024 13:00 – 14:00 (Inaugural talk of the NESTiD seminar series) | Artur Czumaj (University of Warwick, UK) Streaming Graph Algorithms in the Massively Parallel Computation Model We initiate the study of graph algorithms in the streaming setting on massive distributed and parallel systems inspired by practical data processing systems. The objective is to design algorithms that can efficiently process evolving graphs via large batches of edge insertions and deletions using as little memory as possible. We focus on the nowadays canonical model for the study of theoretical algorithms for massive networks, the Massively Parallel Computation (MPC) model. We design MPC algorithms that efficiently process evolving graphs: in a constant number of rounds they can handle large batches of edge updates for problems such as connectivity, minimum spanning forest, and approximate matching while adhering to the most restrictive memory regime, in which the local memory per machine is strongly sublinear in the number of vertices and the total memory is sublinear in the graph sizes. This is a joint work with Gopinath Mishra and Anish Mukherjee. |
| Friday 18 Oct 2024 13:00 – 14:00 | Jie Xu (University of Leeds, UK) A system for training massive-scale models with billions of parameters In this presentation, we will share our recent experience with designing and implementing a practical system, STRONGHOLD, for training massive-scale language models with billions of parameters, with a focus on our offloading mechanism for efficiently moving data amongst GPU memory and CPU RAM/secondary storages. Deep Learning is advancing rapidly, and with it, the size of foundation models is increasing exponentially. However, training these models requires significant GPU resources and power, which can be unaffordable for many academic and industry research teams. Even for AI teams in large companies, resources are limited, and purchasing and maintaining these devices can be prohibitively expensive. For instance, training a GPT-3 model requires over thousands of high-performance-configured A100 GPUs for continuous 3 months. Our system, STRONGHOLD, addresses this challenge by offloading model weights to CPU RAM or other secondary storages dynamically and loading them back when needed, minimizing GPU memory requirements. STRONGHOLD also allows data movement and on-GPU computation to overlap to hide the extra overhead introduced by the offloading mechanism. Compared to state-of-the-art offloading-based solutions, STRONGHOLD improves the trainable model size by 1.9x to 6.5x on a 32GB V100 GPU, with 1.2x to 3.7x improvement on the training throughput. We have successfully deployed STRONGHOLD in production to support large-scale DNN training. |
| Friday 25 Oct 2024 13:00 – 14:00 | Arpan Mukhopadhyay (University of Warwick, UK) On optimal server allocation for parallelizable jobs A large proportion of jobs submitted to modern computing clusters and data centers are parallelizable and capable of running on a flexible number of computing cores or servers. Examples of such jobs include training of large machine learning models, simulation of climate models etc. Although allocating more servers to such a job results in a higher speed-up in the job’s execution, it reduces the number of servers available to other jobs, which in the worst case, can result in an incoming job not finding any available server to run immediately upon arrival. Hence, a natural question to ask is: how to optimally allocate servers to jobs such that (i) the average execution time across jobs is minimized and (ii) almost all jobs find at least one server immediately upon arrival. To address this question, we consider a model of a loss system where jobs with arbitrary concave speed-up functions arrive and a server allocation scheme is used to allocate one or more servers from the system to each arriving job based on the availability of the servers. If a job does not find any available servers upon entry, then it is blocked and lost. We propose a simple server allocation scheme that achieves the minimum average execution time of accepted jobs while ensuring that the blocking probability of jobs vanishes as the system becomes large. To prove our result, we employ Stein’s method which also yields non-asymptotic bounds on the blocking probability and the mean execution time. The talk will be based on joint work with Samira Ghanbarian (uWaterloo), Ravi R. Mazumdar (uWaterloo), and Fabrice Guillemin (Orange Labs, France). |
| Friday 1 Nov 2024 13:00 – 14:00 | William (Billy) Moses Jr. (Durham University, UK) Towards communication-efficient peer-to-peer networks [slides-pdf] We focus on designing Peer-to-Peer (P2P) networks that enable efficient communication. Over the last two decades, there has been substantial algorithmic research on distributed protocols for building P2P networks with various desirable properties such as high expansion, low diameter, and robustness to a large number of deletions. A key underlying theme in all of these works is to distributively build a random graph topology that guarantees the above properties. Moreover, the random connectivity topology is widely deployed in many P2P systems today, including those that implement blockchains and cryptocurrencies. However, a major drawback of using a random graph topology for a P2P network is that the random topology does not respect the underlying (Internet) communication topology. This creates a large propagation delay, which is a major communication bottleneck in modern P2P networks. In this talk, we look at designing P2P networks that are communication-efficient (having small propagation delay) with provable guarantees. Our main contribution is an efficient, decentralized protocol, Close-Weaver, that transforms a random graph topology embedded in an underlying Euclidean space into a topology that also respects the underlying metric. We then present efficient point-to-point routing and broadcast protocols that achieve essentially optimal performance with respect to the underlying space. This talk is based on joint work with Khalid Hourani and Gopal Pandurangan that appeared as a paper in ESA 2024. |
| Friday 8 Nov 2024 13:00 – 14:00 | Yannic Maus (TU Graz, Austria) Sparsification for communication-efficient distributed symmetry-breaking We will present sparsification approaches beneficial for designing algorithms in the CONGEST model, with a particular focus on local symmetry-breaking problems such as graph colorings. |
| Friday 15 Nov 2024 13:00 – 14:00 | Jason Schoeters (University of Florence, Italy) Temporal Cycle Detection and Acyclic Temporisation In graph theory, a cycle can be seen as a structure that allows its vertices to loop back to themselves, or as a structure that allows pairs of vertices to reach each other through distinct paths. We extend these concepts to temporal graph theory, resulting in multiple interesting definitions of a “temporal cycle”. For each of these, we consider the problems of CYCLE DETECTION and ACYCLIC TEMPORISATION. For the former, we are given an input temporal graph, and we want to decide whether it contains a temporal cycle. Regarding the latter, for a given input (static) graph, we want to time the arcs such that no temporal cycle exists in the resulting temporal graph. We’re also interested in ACYCLIC TEMPORISATION where we bound the lifetime of the resulting temporal graph. Multiple results are presented, including polynomial and fixed parameter tractable search algorithms, polynomial-time reductions from 3-SAT andNot-All-Equal-3-SAT, and temporisations resulting from arbitrary vertex orderings which cover (almost) all cases. This is a (soon to be submitted) work with Júlio Araújo, Davi De Andrade, Allen Ibiapina, Andrea Marino, and Ana Silva. |
| Friday 22 Nov 2024 13:00 – 14:00 | Thirupathaiah (Thiru) Vasantam (Durham University, UK) An on-demand resource allocation algorithm for a quantum network hub and its performance analysis To support the execution of multiple simultaneously running quantum network applications, a quantum network must efficiently allocate shared resources. We study traffic models for a type of quantum network hub called an Entanglement Generation Switch (EGS), a device that allocates resources to enable entanglement generation between nodes in response to user-generated demand. We propose an on-demand resource allocation algorithm, where a demand is either blocked if no resources are available or else results in immediate resource allocation. We model the EGS as an Erlang loss system, with demands corresponding to sessions whose arrival is modelled as a Poisson process. To reflect the operation of a practical quantum switch, our model captures scenarios where a resource is allocated for batches of entanglement generation attempts, possibly interleaved with calibration periods for the quantum network nodes. Calibration periods are necessary to correct against drifts or jumps in the physical parameters of a quantum node. We then derive a formula for the demand blocking probability under three different traffic scenarios using analytical methods from applied probability and queueing theory. We prove an insensitivity theorem which guarantees that the probability a demand is blocked only depends upon the mean duration of each entanglement generation attempt and calibration period and is not sensitive to their underlying distributions. Our numerical results support our analysis. Our work is the first analysis of traffic characteristics at an EGS system and provides a valuable analytic tool for devising performance driven resource allocation algorithms. This is a joint work with Scarlett Gauthier (TU Delft) and Gayane Vardoyan (TU Delft & UMass, Amherst). |
| Friday 29 Nov 2024 13:00 – 14:00 | Shiri Chechik (Tel-Aviv University, Israel) Streaming edge coloring with subquadratic palette size In this talk, we will explore the problem of computing an edge-coloring in the (one-pass) W-streaming model. Here, the edges of an $n$-node graph arrive in arbitrary order, and a machine with limited memory aims to output a proper edge-coloring using as few colors as possible. It is well-established that any graph can be edge-colored using $\Delta + 1$ colors, where $\Delta$ is the maximum degree of the graph. However, achieving this bound in the W-streaming model with small memory remains a challenging open question. Previous work has provided an algorithm using $\tilde{O}(n)$ space and approximately $O(\Delta^2)$ colors. In this talk, we will present a new randomized algorithm that, while still operating in $\tilde{O}(n)$ space, reduces the number of colors used to a subquadratic value, improving upon the quadratic dependence on $\Delta$. |
| Friday 6 Dec 2024 13:00 – 14:00 | Daniel Oi (University of Strathclyde, UK) Space Quantum Networking Quantum communications offers the possibility for secure communications, enhancing a range of tasks such as sensing, positioning, navigation & timing, as well as distributed quantum information processing, i.e. networked quantum computers. The fundamental resource for enabling large-scale quantum networks is quantum entanglement that allows quantum information to be transmitted and processed without the risks associated with channel loss and corruption. However, creating entanglement across large distances is challenging due to inherent losses in optical fibres. Alternatively, satellites have been proposed for establishing long-distance links at global scale exploiting the inverse-square intensity drop-off associated with free-space transmission that is exponentially more favourable than fibre losses. The success of the Chinese satellite, Micius, has provided confirmation that satellite quantum communication is feasible, with the distribution of entanglement across a distance of over 1000km, and order of magnitude improvement over terrestrial experiments, as well as quantum teleportation from the Earth to space. In order to extend the reach of quantum links, the use of quantum repeaters and memories are the next steps which would allow networked constellations of satellites to provide coverage to the entire Earth. In this talk, I shall cover progress in the development of satellite quantum communications, the main challenges, and future directions in entanglement distribution from space, and potential realisation of the Space Quantum Internet. |
| Friday 13 Dec 2024 13:00 – 14:00 | TBA |
Term 2 of 2024/25:
(online on zoom)
| Friday 17 Jan 2025 13:00 – 14:00 | Igor Razgon (Durham University, UK) Fixed parameter algorithms for computation of hypertreewidth parameters for restricted classes of hypergraphs TBA |
| Friday 24 Jan 2025 13:00 – 14:00 | Cristina Chueca Del Cerro (Durham University, UK) Social networks’ structural property interdependencies: a (targeted) rewiring approach TBA |
| Friday 31 Jan 2025 13:00 – 14:00 | Raouf Abozariba (Birmingham University, UK) Empirical wireless network measurement in indoor and outdoor environments TBA |
| Friday 7 Feb 2025 13:00 – 14:00 | Prosanta Gope (University of Sheffield, UK) TBA TBA |
| Friday 14 Feb 2025 16:00 – 17:00 Please note the different time! | Sergio Rajsbaum (Universidad Nacional Autonoma de Mexico) TBA TBA |
| Friday 21 Feb 2025 13:00 – 14:00 | Jia Hu (University of Exeter, UK) TBA TBA |
| Friday 28 Feb 2025 13:00 – 14:00 | Hossein Anisi (University of Essex, UK) TBA TBA |
| Friday 7 Mar 2025 13:00 – 14:00 | Oliver Kullmann (Swansea University, UK) TBA TBA |
| Friday 14 Mar 2025 13:00 – 14:00 | Berk Canberk (Edinburgh Napier University, UK) TBA TBA |
| Friday 21 Mar 2025 13:00 – 14:00 | Elisa Bellotti (University of Manchester, UK) TBA TBA |
Term 3 of 2024/25:
(online on zoom)
| Friday 2 May 2025 13:00 – 14:00 | TBA |
| Wednesday 7 May 2025 13:00 – 14:00 Room: MCS 1022 (Vis Lab) Co-organized with the SciComp Research Group NOTE: different day and place! | Julian Hall (University of Edinburgh, UK) TBA |