NESTiD Seminars 2021/22
NESTiD Seminar 2021/22
Below you can find the list of NESTiD seminar speakers and talks for the year 2021/22.
The seminar talks every two weeks were co-organized together with the research group of Networks and Distributed Computing at the University of Liverpool, as part of the Durham-Liverpool synergy. The contact person of this synergy in Liverpool is Leszek Gasieniec.
NESTiD Seminar Coordinator: George Mertzios
Link for the Seminar videos of 2021/22: click here
Term 1 of 2021/22:
(online on zoom)
| Date and Time | Talk |
|---|---|
| Thursday 7 Oct 2021 13:00 – 14:00 (Inaugural talk of the NESTiD seminar series) | Christian Scheideler (University of Paderborn, Germany) Towards a Theory of Hybrid Communication Networks [slides] Humans naturally communicate in a hybrid fashion due to their different senses and the availability of different communication technologies. Thus, it seems natural to study hybrid communication also in distributed systems. But fundamental research in this area is still in its infancy, even though there are several examples where hybrid communication is already exploited in practice. For instance, in modern data centers, wired communication networks are combined with high-speed wireless or optical communication to reduce wire length or increase bandwidth. Also, nowadays, hybrid smartphone networks can be set up by combining ad-hoc, WLAN-based connections with connections via a cellular or satellite infrastructure, and dynamic multipoint VPNs can be set up via the Internet to connect different branches of an organization by combining leased lines (offering them quality-of-service guarantees for their mission-critical traffic) with standard, best-effort VPN connections (for their lower-priority traffic). In my talk, I propose a simple model capturing some important properties of these hybrid networks. In this model, we assume that each node has two different communication modes: a local communication mode that only allows it to send messages in some given communication network, and a global communication mode, which allows a node to send messages to any other node as long as it knows its address but comes with certain other constraints. To motivate its usefulness, I will present some simple solutions for this model and discuss the state-of-the-art. |
| Thursday 14 Oct 2021 13:00 – 14:00 (Inaugural talk of the seminar series of the Durham-Liverpool synergy) | Paul Spirakis (University of Liverpool) Actively Dynamic Networks [slides] We discuss here systems of (distributed) entities that can actively modify their communication network. We focus on two broad issues: (a) distributed algorithms that can reconfigure a network to carry out a given task efficiently, (b) creating a desired network starting from a single entity and allowing entities (nodes) to self-replicate (and thus expand) the network and its size. Such issues lead to a natural balance between how fast (time) and how efficiently (number of link activations , number of excess links to be eventually deleted) a target network can be generated. Our results include lower bounds and algorithms that try to balance speed and efficiency. |
| Thursday 21 Oct 2021 | no seminar |
| Thursday 28 Oct 2021 16:00 – 17:00 (Durham-Liverpool synergy) | Armando Castañeda (Universidad Nacional Autónoma de México) Combinatorial Topology Techniques for Message Passing Systems with Arbitrary Communication Graphs More than two decades ago, combinatorial topology was shown to be useful for analyzing distributed fault-tolerant algorithms in shared memory systems and in message passing systems. So far all systems studied using this approach provide an underlaying communication that allows each process to communicate with all other processes in the system, namely, a complete communication graph. In this talk we will see two recent works that extend the combinatorial topology approach to encompass models where the communication network is an arbitrary graph. Using the new tools, consensus and k-set agreement are studied in synchronous failure-free and fail-prone message passage systems are considered. This is a joint work with Pierre Fraigniaud, Ami Paz, Sergio Rajsbaum, Matthieu Roy and Corentin Travers. |
| Thursday 4 Nov 2021 16:00 – 17:00 | Petra Berenbrink (University of Hamburg, Germany) Fast Consensus via the Unconstrained Undecided State Dynamics We consider the plurality consensus problem for n agents. Initially, each agent has one of k different opinions. Agents choose random interaction partners and revise their state according to a fixed transition function, depending on their own state and the state of the interaction partners. The goal is to reach a configuration in which all agents agree on the same opinion. If there is initially a sufficiently large bias towards some opinions one of them should prevail. In this paper we consider a synchronized variant of the undecided state dynamics which is defined as follows. The agents act in phases, consisting of a decision and a boosting part. In the decision part, any agent that encounters an agent with a different opinion becomes undecided. In the boosting part, undecided agents adopt the first opinion they encounter. We consider this dynamics in the population model. Agents interact in randomly chosen pairs, one pair per time step, and the runtime is measured in parallel time. We show that our protocol reaches consensus (w.h.p.) in O(log2 n) parallel time, providing the first polylogarithmic result for k > 2 (w.h.p.) in this model. Joint work with Gregor Bankhammer, Felix Biermeier, Robert Elsaesser, Hamed Hosseinour, Peter Kling and Dominik Schallmoser. |
| Thursday 11 Nov 2021 16:00 – 17:00 (Durham-Liverpool synergy) | Viktor Zamaraev (University of Liverpool) Sharp thresholds in random simple temporal graphs A graph whose edges only appear at certain points in time is called a temporal graph (among other names). Such a graph is temporally connected if each ordered pair of vertices is connected by a path which traverses edges in chronological order (i.e., a temporal path). In this work, we consider a simple model of random temporal graph, obtained from an Erdős-Rényi random graph G_{n,p} by considering a random permutation π of the edges and interpreting the ranks in π as presence times. Temporal reachability in this model exhibits a surprisingly regular sequence of thresholds. In particular, we show that at p=logn/n any fixed pair of vertices can a.a.s. reach each other; at 2logn/n at least one vertex (and in fact, any fixed vertex) can a.a.s. reach all others; and at 3logn/n all the vertices can a.a.s. reach each other, i.e., the graph is temporally connected. Furthermore, the graph admits a temporal spanner of size 2n+o(n) as soon as it becomes temporally connected, which is nearly optimal as 2n−4 is a lower bound. This result is significant because temporal graphs do not admit spanners of size O(n) in general (Kempe et al, STOC 2000). In fact, they do not even admit spanners of size o(n^2) (Axiotis et al, ICALP 2016). Thus, our result implies that the obstructions found in these works, and more generally, all non-negligible obstructions, must be statistically insignificant: nearly optimal spanners always exist in random temporal graphs. All the above thresholds are sharp. Carrying the study of temporal spanners further, we show that pivotal spanners — i.e., spanners of size 2n−2 made of two spanning trees glued at a single vertex (one descending in time, the other ascending subsequently) — exist a.a.s. at 4logn/n, this threshold being also sharp. Finally, we show that optimal spanners (of size 2n−4) also exist a.a.s. at p=4logn/n. This is a joint work with Arnaud Casteigts (University of Bordeaux), Michael Raskin (Technical University of Munich), Malte Renken (Technical University of Berlin) Arxiv: https://arxiv.org/abs/2011.03738 |
| Thursday 18 Nov 2021 13:00 – 14:00 (Please note the different time) | Ulrich Speidel (University of Auckland, New Zealand) Making better use of satellite links into remote locations with titrated network-coded tunnels Many remote locations – such as Pacific islands or remote villages in inaccessible terrain – are still cut off from the international fibre networks and and rely on expensive satellite Internet via GEO and MEO links. These links tend to fall into three categories: overused and dominated by small flows, underused and dominated by TCP queue oscillation, and plain underused (the rarest of the categories). The second category in particular is often where local ISP budget and link pricing meet. The queue oscillation on these links causes the paradoxical effect that up to half of the nominal link capacity can become inaccessible to TCP due to collective back-off during half of the oscillation cycle while large TCP flows especially suffer from significant slow-down due to packet loss incurred during the other half of the cycle. We have observed this effect on both GEO and MEO links in the Pacific. A cooperation with Muriel Médard from MIT led us to develop network-coded tunnels. In field experiments in the Cook Islands, Tuvalu and Niue, we were able to showed that such tunnels could accelerate individual flows. This was promising enough – but we couldn’t really disconnect an entire island for a while to let us insert a technology we weren’t 100% certain would work, let alone reliably over time. To be able to study all-of-island coding, we established a dedicated hardware-based simulator facility at the University of Auckland. It can simulate traffic to remote locations on actual hardware (24 “world-side” servers with different terrestrial latencies and 106 island-side clients, plus dedicated servers for satellite emulation, coding/decoding, titration, performance-enhancing proxies and data capture) with thousands of “end users”. This has allowed us to demonstrate that coded tunnels allow much higher link utilization at the same demand levels at which we would normally see TCP queue oscillation impair the flow. Moreover, much this gain accrues to large TCP flows, which can accelerate by an order of magnitude or more. Unlike performance-enhancing proxies, coded tunnels do not break the end-to-end principle of the Internet either, allowing for all IP-based protocols to operate across such links. Last but not least, titration allows us to keep surplus coding overhead off the link itself, leading to further significant gains in goodput. |
| Thursday 25 Nov 2021 16:00 – 17:00 (Durham-Liverpool synergy) | Valerie King (University of Victoria, Canada) Distributed connectivity and the k-out random graph conjecture We consider the following problem. Each node in a graph has a distinct ID and each knows only the ID’s of its neighbors. Suppose it can send one message to a referee who must determine the graph’s connected components. The graph sketching technique described by Ahn, Guha and McGregor in 2012 gives a method which requires only O(log^3 n) bits to be sent by each node, to compute the solution with high probability, and this is tight, according to a recent result of Nelson and Yu. However this method requires public randomness. We began by investigating the one-way communication cost of this problem when there is private randomness, and ended up posing and partially proving a surprising conjecture about sampling in graphs and connectivity. This is joint work with Jacob Holm, Mikkel Thorup, Or Zamir, and Uri Zwick which appeared in FOCS 2019. |
| Thursday 2 Dec 2021 16:00 – 17:00 | Yunfei Chen (University of Warwick) UAV for Wireless Communications Unmanned aerial vehicles (UAV) have gained great popularity in recent years due to their low cost and high mobility. In wireless communications, they can act as either aerial base station or relay for information delivery. In this talk, the main principles of UAV communications will be discussed. Firstly, the issue of UAV placement will be studied. For UAVs, a higher altitude gives a better line-of-sight condition in the communications channel but also leads to higher path loss from the ground user due to the longer distance. Hence, we will look for an optimum value of altitude for different application scenarios. Secondly, the use of a flock or swarm of UAVs with multiple UAVs can increase efficiency. We will consider their use as relays. Two typical settings of using multiple UAVs in a multi-hop single link and in multiple dual-hop links will be optimized and compared. Other issues in UAV communications will also be discussed. |
| Thursday 9 Dec 2021 16:00 – 17:00 (Durham-Liverpool synergy) | Leszek Gasieniec (University of Liverpool) A time and space optimal stable population protocol solving exact majority We study population protocols, a model of distributed computing appropriate for modelling well-mixed chemical reaction networks and other physical systems where agents exchange information in pairwise interactions, but have no control over their schedule of interaction partners. The well-studied majority problem is that of determining in an initial population of n agents, each with one of two opinions A or B, whether there are more A, more B, or a tie. A stable protocol solves this problem with probability 1 by eventually entering a configuration in which all agents agree on a correct consensus decision of A, B, or T, from which the consensus cannot change. We describe a protocol that solves this problem using O(log n) states loglog n +O(1) bits of memory and optimal expected time O(log n). The number of states O(log n) is known to be optimal for the class of poly-logarithmic time stable protocols that are output dominant and monotone. These are two natural constraints satisfied by our protocol, making it simultaneously time- and state-optimal for that class. We introduce a key technique called a fixed resolution clock to achieve partial synchronization. Our protocol is non-uniform, i.e., the transition function has the value ⌈log n⌉ encoded in it. We show that the protocol can be modified to be uniform, while increasing the state complexity to Θ(log n loglog n). This is a joint work with David Doty, Mahsa Eftekhari, Eric Severson (UC Davis, USA) and Grzegorz Stachowiak, Przemysław Uznański (Wroclaw U, Poland). Arxiv link: https://arxiv.org/abs/2106.10201 |
Term 2 of 2021/22:
(online on zoom)
| Thursday 13 Jan 2022 16:00 – 17:00 | Peter Davies (University of Surrey) LOCAL and Low-Space MPC: A Bridge Between Distributed and Parallel Computing In recent years, the fields of distributed and parallel graph algorithms, while always linked, have grown increasingly close. In particular, the emergent Massively Parallel Computation (MPC) model has been shown to have a strong connection to the classic LOCAL model of distributed computing. Under some restrictions, LOCAL algorithms can be run at an exponential speedup in MPC, via a process known as graph exponentiation. Furthermore, recent work has suggested that for many problems, this might be the best that one can hope to do in low-space MPC. This talk will begin with an overview of what is known about this connection, both from an upper- and lower-bounds perspective. We will then discuss some recent results (joint work with Artur Czumaj and Merav Parter) showing that the power of low-space MPC is not limited to graph exponentiation, and demonstrate examples of algorithms which are super-exponentially faster than their LOCAL counterparts. Finally, we will consider the implications for designing algorithms or proving lower bounds in MPC. |
| Thursday 20 Jan 2022 16:00 – 17:00 (Durham-Liverpool synergy) | Peter Etchells (Durham University) A Transcriptional Regulatory Network Controls Vascular Development in plants Transcription factor proteins bind to DNA to control the activity of genes. Transcriptional regulatory networks define interactions between transcription factor proteins and their target genes. These networks are required to be dynamic, fine-tuning outputs that are cell type specific, that change through developmental time, and/or in response to changes in environment. We have recently described a putative transcriptional regulatory network comprising 690 transcription factor-promoter interactions in Arabidopsis, focused on genes that act with a receptor kinase, PHLOEM INTERCALATED WITH XYLEM (PXY), which regulates cell division and influences organization in plant vascular tissue. By cross referencing network and gene expression data, we have identified novel regulators of vascular development. More recently, we have expanded our network to include further interactions, such that the network contains 1447 edges. We would like to use this information to understand how the flux of signals through networks differs between cell types. |
| Thursday 27 Jan 2022 16:00 – 17:00 | Omer Rana (Cardiff University) Autonomics at the Edge: Resource Orchestration for “Edge Native” applications [slides] As processing and communication capacities of edge devices increase, the need for a computing environment that can benefit from this additional capacity, closer to a user, has emerged. The complexity of applications hosted on these devices has continued to increase, including complex data processing of audio and video streams, to event-processing capabilities (e.g. triggers for service offloading in mobile devices). Understanding how edge native applications can be designed and deployed becomes a key research challenge, for instance application developers must consider how offloading can improve quality of service levels, depending on connectivity between a user and the computing infrastructure. In this context, pre-configured prior application configuration is now unsuitable. Understanding how self-adaptation and autonomic computing techniques can be used to adapt application behaviors for edge devices is described — making use of control actions across the cloud-to-edge continuum. We describe how performance, user mobility and resource requirements (e.g. security credentials) can be used to trigger such adaptation. |
| Thursday 3 Feb 2022 16:00 – 17:00 (Durham-Liverpool synergy) | Thiru (Thirupathaiah) Vasantam (Durham University) A throughput optimal scheduling policy for a quantum switch We study a quantum switch that creates shared end-to-end entangled quantum states to multiple sets of users that are connected to it. Each user is connected to the switch via an optical link across which bipartite Bell-state entangled states are generated in each time-slot with certain probabilities, and the switch merges entanglements of links to create end-to-end entanglements for users. One qubit of an entanglement of a link is stored at the switch and the other qubit of the entanglement is stored at the user corresponding to the link. Assuming that qubits of entanglements of links decipher after one time-slot, we characterize the capacity region, which is defined as the set of arrival rates of requests for end-to-end entanglements for which there exists a scheduling policy that stabilizes the switch. We propose a Max-Weight scheduling policy and show that it stabilizes the switch for all arrival rates that lie in the capacity region. We also provide numerical results to support our analysis. |
| Thursday 10 Feb 2022 16:00 – 17:00 | Nishanth Sastry (University of Surrey) Untangling the Web by tracking our trackers The Web has evolved into a complex ecosystem — visiting one website may actually involve a large number of other third party domains such as advertisers and analytics companies, which place cookies in our browsers. Many of these third parties are present on several common websites, and are therefore able to track users’ visits across websites and gain visibility into their browsing patterns. We have created a browser extension that helps users understand how their privacy may be compromised by third parties. Over 10,000 users across the world have deployed this extension. Based on this, we present an analysis of the current state of privacy on the Web in over 85 different countries. We find, for example, that Chinese users fare better than users in countries like UK, US and Canada. We also develop a metric called `tangle factor’, to quantify the interconnectedness of independent first party websites, and use this to measure and compare the efficacy of different privacy measures (e.g., ad blockers). Finally, we examine the impact of GDPR and find that this does not seem to have had an appreciable impact, perhaps because users are choosing default suggestions for allowed cookies. |
| Thursday 17 Feb 2022 16:00 – 17:00 (Durham-Liverpool synergy) | No seminar. |
| Thursday 24 Feb 2022 16:00 – 17:00 | Jared Saia (University of New Mexico) Bankrupting Attackers in Dynamic Networks In dynamic networks, participants join and leave at will, with little-to-no oversight. Such networks are vulnerable to the Sybil attack, where a single attacker pretends to be multiple participants in order to manipulate the system state or monopolize system services. Current Sybil defenses have high costs, which is a barrier to deployment. Can we design defenses with costs that scale slowly with the costs of an attacker? In this talk, we show this is possible. In particular, we describe an algorithm that ensures a minority of Sybil IDs, and has cost that is O(sqrt(BJ) + J), where B is the cost of the attacker, and J is the join rate of good nodes. Thus, surprisingly, the algorithm’s cost scales more slowly than the attacker’s. This talk discusses results from a paper at ICDCS 2021, and is joint work with Diksha Gupta and Maxwell Young. |
| Thursday 3 Mar 2022 16:00 – 17:00 (Durham-Liverpool synergy) | Merav Parter (Weizmann Institute, Israel) New Diameter Reducing Shortcuts: Breaking the $O(\sqrt{n})$ Barrier [slides] For an $n$-vertex digraph $G=(V,E)$, a \emph{shortcut set} is a (small) subset of edges $H$ taken from the transitive closure of $G$ that, when added to $G$ guarantees that the diameter of $G \cup H$ is small. Shortcut sets, introduced by Thorup in 1993, have a wide range of applications in algorithm design, especially in the context of parallel, distributed and dynamic computation on directed graphs. A folklore result in this context shows that every $n$-vertex digraph admits a shortcut set of linear size (i.e., of $O(n)$ edges) that reduces the diameter to $\widetilde{O}(\sqrt{n})$. Despite extensive research over the years, the question of whether one can reduce the diameter to $o(\sqrt{n})$ with $\widetilde{O}(n)$ shortcut edges has been left open. In this talk, I will present the first improved diameter-sparsity tradeoff for this problem, breaking the $\sqrt{n}$ diameter barrier. Specifically, we show an $O(n^{\omega})$-time randomized algorithm for computing a linear shortcut set that reduces the diameter of the digraph to $\widetilde{O}(n^{1/3})$. We also extend our algorithms to provide improved $(\beta,\epsilon)$ hopsets for $n$-vertex weighted directed graphs. Joint work with Shimon Kogan. |
| Thursday 10 Mar 2022 16:00 – 17:00 | Marco Chiesa (KTH Royal Institute of Technology) Designing high-speed datacenter load balancers Large service providers use load balancers (LBs) to dispatch millions of incoming connections per second towards thousands of servers. There are two basic yet critical requirements for a load balancer: (i) uniform load distribution of the incoming connections across the servers and (ii) resilience to failure, and (iii) efficiency to reduce the massive energy consumption of datacenter networks. Yet, satisfying all these requirements at the same time today is highly non-trivial. In this talk, I will first provide some background on datacenter load balancers and briefly survey the existing work. I will then show that small modifications to existing protocols bring dramatic performance improvements in the way we design today’s datacenter load balancers. More specifically, I will show how to move the logic of more than one thousand load balancers into a single high-speed programmable switch, potentially reducing energy consumption by 300x. |
| Thursday 17 Mar 2022 16:00 – 17:00 (Durham-Liverpool synergy) | Donald Towsley (University of Massachussets Amherst) The Quantum Internet: Recent Advances and Challenges Quantum information processing is at the cusp of having significant impact on technology and society in the form of providing unbreakable security, ultra-high-precision distributed sensing with applications to metrology and science discovery (e.g., LIGO), and polynomial speeds up on search with implications to big data. Most of these applications are enabled by high-rate distributed shared entanglement between pairs and groups of users. A critical missing component that prevents crossing this threshold is a distributed infrastructure in the form of a world-wide “Quantum Internet”. This motivates our study of quantum networks, namely what is the right architecture and how should it operate, i.e., route multiple quantum information flows, and dynamically allocate resources fairly. In this talk I will review a specific class of quantum networks – those that generate and distribute entangled quantum states to pairs or groups of users. I will present opportunities and challenges related to resource sharing in such networks focusing on similarities to and differences from classical networks. I will also present challenges of analyzing the performance of such networks. I will end the talk with a list of open problems. |
Term 3 of 2021/22:
(online on zoom)
| Thursday 28 Apr 2022 16:00 – 17:00 (Durham-Liverpool synergy) | Roger Wattenhofer (ETH Zurich) Cascade: Asynchronous Proof-of-Stake Nakamoto’s Bitcoin protocol has taught the world how to achieve trust without a designated trusted party. However, Bitcoin’s proof-of-work solution comes at serious costs and compromises. While solving the energy problem of proof-of-work, proof-of-stake introduces some of its own problems. We relax the usual notion of consensus to extract the requirements necessary for an efficient cryptocurrency. Towards this end, we introduce a blockchain design called Cascade that is consensusless, asynchronous, scalable, deterministic, and efficient. While Cascade has its own limitations, it should serve as a nice discussion basis for a better blockchain design. Cascade is joint work with Jakub Sliwinski. |
| Thursday 5 May 2022 16:00 – 17:00 | Dariusz Kowalski, Augusta University Anonymous Distributed Computing in Dynamic Networks Anonymity of autonomous players is one of the classical methods of assuring privacy. It has been studied for decades in the context of feasibility and efficiency in ad hoc networks and other distributed models of computation, and recently also in dynamic networks’ models. In this talk I will present a digest of my recent work on polynomial time anonymous computation in dynamic networks, including the impact of randomness, (temporal) connectivity, networks’ isoperimetric bound and congested environment (i.e., logarithmically bounded messages and local memory) on round complexity of counting and anonymous message exchange. I will also discuss several direct and indirect open research directions arising from this work. My talk is based on a few relatively recent ICALP and SPAA papers and some new work available on arxiv, which was co-authored by Miguel Mosteiro. |