Incremental Distributed Graph Coloring

Extension to the wiki:DLF algorithm for recoloring an updated graph incrementally.

Collective procedure: Incremental DLF for node k.
   Precondition: Node k is colored with color c.
   Precondition: All neighbors of k are marked active.

   If there is a color nc < c that is not used:
      Set c to nc.

   Choose a random number r.

   Send CHECK(c, deg(k), r) to all active neighbors.
   Receive CHECK(c(n), deg(n), r(n)) from all active neighbors n.

   Compare (c, deg(k), r) against all received parameters.
   If color c produces no conflict:
      Set accept to TRUE.
      For all active neighbors n with higher degree:
         Call: Receive reply message m from neighbor n.
         If received message m was CANCEL(): 
            Set accept to FALSE.

      If accept:
         Send message COLOR(c) to all neighbors.
      Else:
         Send message CANCEL() to all active neighbors.

      For all active neighbors n with lower or equal degree:
         Call: Receive reply message m from neighbor n.

      If accept:
         Call: Receive missing color messages.
      Else:
         Call: DLF for node k.

   Else if k has heighest priority:
      Send message COLOR(c) to all neighbors.
      Set node k colored.
      Call: Receive reply messages.
      Call: Receive missing color messages.

   Else:
      Send message CANCEL() to all neighbors with less priority 
         or no conflict.
      Call: Receive reply messages.
      Call: DLF for node k.

With:

Condition: node x has a higher priority than node y  <=>
   (deg(x), r(x), rank(x)) >,>,> (deg(y), r(y), rank(y))

Procedure: Receive reply messages.
   For all active neighbors n with higher priority or no conflict:
      Call: Receive reply message m from neighbor n.

Procedure: Receive reply message m from neighbor n.
   Receive message m from neighbor n.
   Switch message m:
      COLOR(cn):
         Call: Handle message COLOR(cn).

      CANCEL():
         Do nothing.

Procedure: Receive missing color messages.
   For each active neighbor n: 
      Receive message COLOR(cn) from neighbor n.
      Call: Handle message COLOR(cn) from neighbor n.

Procedure: Handle message COLOR(cn) from neighbor n.
   Assign color cn to neighbor n.
   Mark color cn as USED.
   Mark neighbor n as not ACTIVE.