3 citations · 4 across the 5 of their papers we have counts for
11 papers · 1 filter
The Message Complexity of Distributed Graph Optimization
Fabien Dufoulon, Shreyas Pai, Gopal Pandurangan +2
The message complexity of a distributed algorithm is the total number of messages sent by all nodes over the course of the algorithm. This paper studies the message complexity of d…
Byzantine-Resilient Counting in Networks
Soumyottam Chatterjee, Gopal Pandurangan, Peter Robinson
We present two distributed algorithms for the {\em Byzantine counting problem}, which is concerned with estimating the size of a network in the presence of a large number of Byzant…
Can We Break Symmetry with o(m) Communication?
Shreyas Pai, Gopal Pandurangan, Sriram V. Pemmaraju +1
We study the communication cost (or message complexity) of fundamental distributed symmetry breaking problems, namely, coloring and MIS. While significant progress has been made in…
The Complexity of Symmetry Breaking in Massive Graphs
Christian Konrad, Sriram V. Pemmaraju, Talal Riaz +1
The goal of this paper is to understand the complexity of symmetry breaking problems, specifically maximal independent set (MIS) and the closely related -ruling set problem, in…
Network Size Estimation in Small-World Networks under Byzantine Faults
Soumyottam Chatterjee, Gopal Pandurangan, Peter Robinson
We study the fundamental problem of counting the number of nodes in a sparse network (of unknown size) under the presence of a large number of Byzantine nodes. We assume the full i…
Leader Election in Well-Connected Graphs
Seth Gilbert, Peter Robinson, Suman Sourav
In this paper, we look at the problem of randomized leader election in synchronous distributed networks with a special focus on the message complexity. We provide an algorithm that…