Using Read-$k$ Inequalities to Analyze a Distributed MIS Algorithm

Sriram Pemmaraju, Talal Riaz

Until recently, the fastest distributed MIS algorithm, even for simple graphs, e.g., unoriented trees has been the simple randomized algorithm discovered the 80s. This algorithm (c…