Logo image
Back
Brief Announcement: Using Read-k Inequalities to Analyze a Distributed MIS Algorithm
Conference proceeding

Brief Announcement: Using Read-k Inequalities to Analyze a Distributed MIS Algorithm

Sriram Pemmaraju and Talal Riaz
Proceedings of the 2016 ACM Symposium on principles of distributed computing, pp.483-485
PODC '16
07/25/2016
DOI: 10.1145/2933057.2933062

View Online

Abstract

Until recently, the fastest distributed MIS algorithm, even for simple graphs, e.g., unoriented trees, has been the simple randomized algorithm discovered in the 80s. This algorithm (commonly called Luby's algorithm ) computes an MIS in O (log n ) rounds (with high probability). This situation changed when Lenzen and Wattenhofer (PODC 2011) presented a randomized O (√log n } ⋅ log\log n )-round MIS algorithm for unoriented trees. This algorithm was improved by Barenboim et al. (FOCS 2012), resulting in an MIS algorithm running in O (√log n ⋅ log\log n ) rounds. The analyses of these tree MIS algorithms depends on "near independence" of probabilistic events, a feature of the tree structure of the network. In their paper, Lenzen and Wattenhofer hope that their algorithm and analysis could be extended to graphs with bounded arboricity. We show how to do this in this note. By using a new tail inequality for read-k families of random variables due to Gavinsky et al. Random Struct Algorithms , 2015), we show how to deal with dependencies induced by the recent tree MIS algorithms when they are executed on bounded arboricity graphs. Specifically, we analyze a version of the tree MIS algorithm of Barenboim et al. and show that it runs in O (poly(α) ⋅ √log n ⋅ log log n ) rounds in the CONGEST model for arboricity-α graphs.
 bounded arboricity graphs congest model luby's algorithm maximal independent set read-$k$ inequality

Details

Metrics

48 Record Views
1 Times Cited - Web of Science
Logo image