Date: 05 June 2019
Time: 12:45 - 13:30 (Lunch available from 12:35)
Room: RA 1501 (Ravelijn)
Speaker: John Augustine (IIT Madras)
Title: Distributed Computation in Node-Capacitated Networks
Abstract
In this talk, we will begin with a brief overview of well-studied distributed computing models and their applications. We will then introduce a new model called the node capacitated clique (NCC) model in which network nodes are connected in the form of a clique (so any two nodes can communicate), but the nodes have limited communication bandwidth (so a node can't communicate with too many other nodes at any time). The NCC model is aimed at modeling peer-to-peer networks (like the bitcoin network) where any two nodes can communicate when at least one of them knows the other's IP address. We will then discuss some basic algorithmic primitives in this model for aggregating and disseminating information. Finally, we will use these primitives to design an algorithm to find the minimum spanning tree of an input graph.
This is joint work with Mohsen Ghaffari, Robert Gmyr, Kristian Hinnenthal, Fabian Kuhn, and Christian Scheideler. It will be presented shortly at SPAA 2019.