Explain the tricolor marking algorithm used in concurrent garbage collectors?

Tricolor marking is the bookkeeping scheme concurrent collectors use to track marking progress while the application keeps mutating references at the same time. Every object is conceptually one of three colors at any point during the marking phase:

Marking proceeds by repeatedly picking a grey object, scanning its fields, coloring every white object it references grey, and finally coloring the object itself black - grey objects form the active "frontier" work list. At the end, anything still white is unreachable and can be reclaimed.

The danger with a concurrently running mutator is the tricolor invariant being violated: if a black (already-scanned) object gets a new reference pointing to a white object, and every other path to that white object is cut at the same time, the collector will never revisit the black object to discover it - and will wrongly sweep a still-reachable object as garbage. This is exactly why concurrent collectors need a write barrier: G1's SATB barrier logs the old value of any reference about to be overwritten (preserving the snapshot taken at marking's start), while other collectors use an incremental-update barrier that re-greys the target object at the moment the new reference is written. Either technique restores the invariant and keeps marking correct despite concurrent mutation.