## 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

- at each step, each node activates at random with a fixed, uniform probability (the
- 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

- when a node activates, it chooses a color that minimizes its conflicts with its neighbors
- Local communication:
- when a node changes color, it informs its neighbors

- Probabilistic activation: