Summary of Results for CFP (et al.)

• Theoretical models

  • convergence when under-constrained
  • convergence when critically constrained
  • loose upper-bound on communication costs
  • scalability (constant parallel complexity)

• Experimental results

  • reasonable activation probability for wide range of graphs
  • convergence
  • rapid short-term reduction in conflicts when under-constrained
  • rapid short-term reduction in conflicts when critically constrained
  • good behavior when over-constrained
  • low communication costs
  • scalability
  • robustness against node/communication failure

• Simple algorithm for decentralized, anytime graph coloring

  • promises fast, cheap, robust resource management