From mboxrd@z Thu Jan  1 00:00:00 1970
From: David Tolpin <dvd@davidashen.net>
Message-Id: <200403020914.i229EuBt071805@adat.davidashen.net>
To: 9fans@cse.psu.edu
Subject: Re: [9fans] Re: advantages of limbo
In-Reply-To: <197c245cd830d9ea21caa61e67d26169@plan9.bell-labs.com>
Content-Type: text/plain; charset=KOI8-R
Date: Tue,  2 Mar 2004 13:14:56 +0400
Topicbox-Message-UUID: 0ab6f316-eacd-11e9-9e20-41e7f4b1d025

> > It is a wrong assumption that mark'n'sweep requires staged garbage
> > collection. Why don't you just use propagating markers? It is marginally
> > complex algorithmically, instantly throws away rubbish and does not
> > make a difference between cyclic and acyclic data structures.
>
> I don't know about this.  Could you provide a reference?
>

I'll try to find; I used to implement it according to a paper
from a conference but I don't have the exact link. The idea
is that you maintain and update marks (as in mark'n'sweep)
instantly. Adding or deleting a reference induces modifications
in a subgraph of the marked graph. Nodes which were marked and
become unmarked  can be deleted and it is almost equivalent in
response time to reference counting.  Graph updates must be
synchronized on reference modifications, and nowhere else.

Or is it what the paper on limbo calls 'graph coloring'?