Workshop Speakers

George B. Mertzios

Title: Sliding Window Temporal Graph Coloring

Abstract: Graph coloring is one of the most famous computational problems with applications in a wide range of areas such as planning and scheduling, resource allocation, and pattern matching. So far coloring problems are mostly studied on static graphs, which often stand in stark contrast to practice where data is inherently dynamic and subject to discrete changes over time. A temporal graph is a graph whose edges are assigned a set of integer time labels, indicating at which discrete time steps the edge is active. In this paper we present a natural temporal extension of the classical graph coloring problem. Given a temporal graph and a natural number $\Delta$, we ask for a coloring sequence for each vertex such that (i) in every sliding time window of $\Delta$ consecutive time steps, in which an edge is active, this edge is properly colored (i.e. its endpoints are assigned two different colors) at least once during that time window, and (ii) the total number of different colors is minimized. This sliding window temporal coloring problem abstractly captures many realistic graph coloring scenarios in which the underlying network changes over time, such as dynamically assigning communication channels to moving agents. We present a thorough investigation of the computational complexity of this temporal coloring problem. More specifically, we prove strong computational hardness results, complemented by efficient exact and approximation algorithms. Some of our algorithms are linear time fixed-parameter tractable with respect to appropriate parameters, while others are asymptotically almost optimal under the Exponential Time Hypothesis (ETH).

Sayan Bhattacharya

Title: Dynamic Primal-Dual Algorithm for Minimum Vertex Cover

Abstract: Many real-world networks such as the ones arising out of facebook and twitter, webpages and hyperlinks etc. evolve with the passage of time. This motivates the study of dynamic graph algorithms, where we have to maintain the solution to a given optimization problem when the input graph keeps changing via a sequence of updates (edge insertions/deletions). The goal is to design algorithms whose update times (time taken to handle an edge insertion/deletion) are significantly faster than recomputing the solution from scratch after each update in the input graph. In this talk, I will present a high level overview of a recent development in dynamic graph algorithms, by presenting a clean, deterministic primal-dual algorithm for maintaining an approximately minimum vertex cover with small update time. I will also highlight the fact that this dynamic algorithm can be easily implemented in a distributed setting, thereby pointing towards an interesting research direction at the intersection of dynamic and distributed algorithms.

Amitabh Trehan

Title: The Dynamic and Varied Nature of Distributed Computing

Abstract: Distributed computing differs from centralised computing in that the computation can proceed despite component failures with the purpose often being to achieve fault-tolerance. At the same time, there are almost an unlimited number of models attempting to capture the multi-agent settings. We give a brief overview of some of these, in particular, low memory flooding and compact local streaming, and the self-healing model for reconfigurable/peer-to-peer/overlay network/graphs.

James Worrell

Title: Computing Algebraic and Semi-Algebraic Invariants

Abstract: We consider the problem of computing algebraic and semi-algebraic invariants for simple classes of programs with integer variables and polynomial assignments, giving both algorithms and undecidability results. Joint work with Almagor, Chistikov, Ouaknine, Pouly, Hrushovski.

Tomasz Radzik

Title: Counting the size of population in the probabilistic population model

Abstract: We consider the problem of counting the size of population in the probabilistic population model. In this model, we are given a distributed system of identical agents which interact in pairs with the goal to solve a common task. In each time step, the two interacting agents are selected uniformly at random. In this paper we consider 'uniform protocols', which require that the actions of interacting agents do not depend in any way on the population size. We present population protocols for
approximate and exact counting of the size of the population, highlighting the notions of time and state complexity of uniform protocols. This talk is based on joint work by Petra Berenbrink, Dominik Kaaser and Tomasz Radzik.

Andrew Adamatzky

Title: Distributed unconventional computing devices

Abstract:  We will discuss prototypes of unconventional computing devices made of reaction-diffusion chemical media, living swarms, slime mould, plants, fungi, and (bio)polymer networks. We show how these natural systems compute via travelling excitation wave-fronts, localised patterns of activity, oscillations and peristaltic dynamics of cytoplasm, pulses in vascular system and mycelium, morphogenesis, electrical current and interaction of solitonic waves. Mechanisms of information processing in and functional properties of these physical, chemical and living substrates might help to develop future efficient algorithms of distributed computation, design robust architectures and manufacture end-user prototypes of emergent computing devices.

Iain A. Stewart

Title: Some "mathematical" aspects of data centre networks

Abstract: Interconnection networks form the communication fabrics of distributed computer systems and are common-place in distributed-memory multiprocessor machines (supercomputers), systems on chips, and data centres. The massive number of processors involved in an interconnection networks means that it is simply not feasible to build prototypes and consequently interconnection network design is guided by appropriate graph-theoretical structural properties combined with simulation (in software). In this talk, I will illustrate a number of ways in which discrete mathematics impacts upon the design of interconnection networks for data centres.