David Worley

COMP 5704: Parallel Algorithms and Applications in Data Science

School of Electrical Engineering and Computer Science
University of Ottawa, Ottawa, Canada

Project Title: A Round-Based Approach to Distributed Graph Coloring and Comparison to Other Methods

Name: David Worley

E-Mail: dworl020 at uottawa .ca

Project Outline: The first stage of my project is to present a literature review and comparison of current state-of-the-art methodologies for distributed graph coloring. The second stage will be to implement one such algorithm, recently designed by Maus. This is a round based algorithm where each of the p processors will process n/p vertices and generate a sequence for them. This sequence is calculated by sampling distinct polynomials from a prime field to guarantee minimal conflicts between any two polynomials. With this, vertices can test the colors in their sequence for conflicts with their neighbour and permanently color themselves once they have found a more suitable color. This algorithm scales between generating a Δ + 1 coloring and a O(Δ^2) coloring, subsuming many prevalent distributed graph coloring algorithms through clever choice of parameters. Experimental coloring results will be discussed for graphs of increasing size.

Startup Paper(s): Maus, Y. (2021). Distributed Graph Coloring Made Easy. Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures. https://doi.org/10.1145/3409964.3461804

Deliverables:

Literature Review (PDF file created from LATEX template.)<--- updated to better match final paper
Presentation Outline (PDF file created from LATEX template)
Slide Presentation (PowerPoint File) incl. Question Sheet
Final Paper (PDF file created from LATEX template)
Code and Data (put all code, data, etc. into this directory)

Relevant References:

L. Barenboim, M. Elkin, and U. Goldenberg. Locally-iterative distributed (δ + 1)- coloring below szegedy-vishwanathan barrier, and applications to self-stabilization and to restricted-bandwith models. Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 437–446, 2018
L. Barenboim and M. Elkin. Distributed graph coloring: Fundamentals and recent developments. Synthesis Lectures on Distributed Computing Theory, 4, 07 2013.
R. Cole and U. Vishkin. Deterministic coin tossing with applications to optimal parallel list ranking. Information and Control, 70(1):32–53, 1986
D. Hefetz, F. Kuhn, Y. Maus, and A. Steger. Polynomial lower bound for distributed graph coloring in a weak local model. Proc. of the 30th International Symp. on Dis- tributed Computing, pages 99–113, 2016.
N. Linial. Locality in distributed graph algorithms. Society for Industrial and Applied Mathematics, 21(1):193–201, 1992
Y. Maus. Distributed graph coloring made easy. SPAA ’21, pages 362–372, 2021.
M. Szegedy, S. Vishwanathan. Locality Based Graph Coloring. In Proceedings of the twenty-fifth annual ACM symposium on Theory of Computing (STOC '93).