New Algorithm: Fixed-Probability Colorer

• FP is a soft graph colorer

  • decentralized, iterative, anytime, local-repair algorithm

• Iterated, synchronized steps, each having three phases:

  • Probabilistic activation:
    • at each step, each node activates at random with a fixed, uniform probability (the activation probability)
    • in contrast, in SI, nodes activate color by color
      • SI is less likely to introduce conflicts than FP but has lower parallelism
  • Select color using local repair/optimization:
    • when a node activates, it chooses a color that minimizes its conflicts with its neighbors
      • based on its current knowledge of its neighbors’ colors
  • Local communication:
    • when a node changes color, it informs its neighbors