Speaker: Miguel Mosteiro, Pace University
Title: Polynomial Counting in Anonymous Dynamic Networks with Applications to Anonymous Dynamic Algebraic Computations
In recent years, the problem of Counting the number of nodes in Anonymous Dynamic Networks (ADNs) has attracted a lot of attention. ADNs are algorithmically challenging because nodes are indistinguishable (they lack identifiers) and the topology is adversarial (i.e. network links may change arbitrarily from a communication round to the next one) limited only to maintain the network connected. Counting is central in distributed computing because the number of participants is frequently needed for algorithmic decisions, such as termination, agreement, and synchronization.
A variety of distributed algorithms built on top of mass-distribution techniques have been presented, analyzed, and also experimentally evaluated; some of them assumed additional knowledge of network characteristics, such as bounded degree or given upper bound on the network size. However, the question of whether Counting can be solved deterministically in sub-exponential time remained open until recently.
In this talk, I will present our recent Methodical Counting Algorithm for ADNs, which runs in polynomial time and requires no knowledge of network characteristics. I will also show how to extend Methodical Counting to compute the sum of input values and more complex functions without extra cost. The Methodical Counting Algorithm and its extensions to other algebraic and Boolean function computations were the first that could be implemented in practice on large ADNs with worst-case guarantees. I will also overview some of the successful follow-up work on this and other lines of research involving undergraduate students.
Miguel A. Mosteiro is an Associate Professor of Computer Science Pace University. Before, he was Assistant Professor at Kean University, Research Professor at Rutgers University and Research Fellow at the Universidad Rey Juan Carlos (Spain). He obtained his PhD in Computer Science from Rutgers University, and his BE in Electronics from Universidad Tecnologica Nacional (Argentina). His research interests span the broad areas of algorithms and distributed computing. He focuses on algorithms for restricted wireless networks, crowd computing, cloud computing, and more recently spammability and fairness of ranking algorithms such as PageRank. His research work is conducted in collaboration with scholars from various countries, involving graduate as well as undergraduate students. Prof. Mosteiro has received the 2016 Kean University Undergraduate Research Mentor of the Year Award, concurrently with the Undergraduate Researcher of the Year Award for one of his students.