Repost: Questions regarding the Ent

[Jeff Rush <jrush@xxxxxxxxxx>]

Mark S Miller wrote:
> 
> At 06:18 AM 1/25/2002 Friday, Jeff Rush wrote:
> >
> >1. what kind of enfilade is an OTree?  They look like they might
> >   be type 1 (DSP only, no WID).  Are type 2 enfilades used
> >   _anywhere_ in Gold?
> 
> On the way from Green to Gold, Wids got replaced with Splits.  Similar in
> concept, but Splits scale much better.  We got the idea by trying to imagine
> how Enfilades relate to K-D-Trees.
> 
> Can you give us a pointer on type1 vs type2 enfilades?  I don't remember
> this classification.
> 
> >2. canopies are implemented as AVL trees, correct?
> 
> I don't remember thinking of them as AVL trees, but I also don't remember
> what kind of balancing properties they had.
> 
> >The bert
> >   and recorder canopies are _identical_ in *implementation*,
> >   just differing in how they are used?
> 
> That was certainly true at one time.  But I think the Bert Canopy went
> through a Dean-driven reform since then.  Or perhaps this was planned but
> never happened.  Dean?
> 
> >3. Are the nodes (histons) in an HTree and the nodes (dsploafs)
> >   in an OTree the same object, just seen from a different
> >   perspective?  To say it a different way, are there an equal
> >   number of histons and dsploafs in an Ent, permanently paired
> >   from their moment of creation?  One of the documents refers
> >   to red/blue butterfly shapes, leading me to believe Ent
> >   nodes are composite objects, each with a histon and dsploaf
> >   _interface_.
> 
> I don't remember the terminology any more, so I'll answer in more basic
> terms.  Let's call each southward pointing OTree node an ONode, and each
> northward pointing HTree node an HNode.  The inter-penetration of HTrees and
> OTrees can be seen in terms of units consisting of a single H-subtree and a
> perpendicular single O-subtree attached to each other at their roots.  As I
> recall, it was such a unit that was called a histon.  A histon wasn't a kind
> of object, but rather a particular kind of clump of objects.
> 
> >4. Technically speaking, canopies are not considered, by the
> >   documents I've read, to be a part of the Ent, but rather a
> >   data structure _over_ it.  I'd like to get my terminology
> >   right, so is this correct?
> 
> We were probably ambiguous about this, but I'd say it was indeed part of the
> Ent.  Perhaps we should speak separately about the Ent's internal volume vs
> the Ent's canopies, but the Ent consists of both together.  This also fits
> the metaphor better -- forests have canopies.
> 
> >5. Do the H and O trees interpenetrate at _all_ levels or only
> >   at the leave/root levels?  From my many readings, Mark
> >   Miller's tutorial implied they only connect at the leave
> >   and root levels but the red/blue butterfly concept would
> >   contradict this.  I suspect they connect at all levels.
> 
> All levels.  I'm surprised my tutorial implied otherwise.
> 
> >6. Mark Miller's tutorial makes a brief mention of expanding
> >   loafs, with regard to the real and sequence coordinate
> >   spaces, but never goes any deeper.  Aren't expanding
> >   loafs really the 'hang POOM enfilades off the bottom'
> >   concept from Green?
> 
> I don't remember the 'hang POOM enfilades off the bottom' concept from
> Green, so I can't say.  I believe the notion is that you only need to divide
> up the south leaves as driven by sharing differences.
> 
> >7. At one point in a transcript it is stated that text
> >   documents can have gaps or voids in the coordinate space.
> >   The person who asks is told that such an ability is crucial
> >   to Gold, but nothing further is said.  Why is it crucial?
> 
> I don't know why I said it was crucial, but it is a necessary consequence of
> Gold's view that all enfilades are a parameterization of generic enfilade
> code with a coordinate space.
> 
> >8. With all the unique/cute names in Xanadu, what is the name
> >   of the AVL nodes within a canopy?
> 
> Independent of whether these are actually AVL nodes, I don't remember.  Anyone?
> 
> >9. Considering mutability and read-only storage, are histons,
> >   canopies and dsploafs *immutable* or not?  I don't see
> >   how the splay tree of histons can be immutable, nor the
> >   nodes that make up a canopy.  Canopies seem to be mutable
> >   since they get *marked* and *unmarked* over time.
> 
> Internally, as a data structure, it's all mutable.  At the Edition/Works
> level of external semantics, Editions are approximately immutable.
> 
> >10. With regard to multithreading/locking, doesn't the
> >   marking/unmarking of canopies, mean that there can only
> >   be one entity in the Ent at a time?  Doesn't this place
> >   a severe bottleneck on the performance? (I need to learn
> >   more re dagwood, endorsements/permissions).
> 
> The backend runs as a singly threaded event loop.  Anything else would lead
> to multi-threaded madness.  For later thoughts on this issue, see
> http://www.erights.org/elib/concurrency/event-loop.html .
> 
> >11. In Mark Miller's transcript he says that the canopies
> >   get updated "just in time" but then he is interrupted
> >   and never finishes the thought.  When are they updated?
> 
> I'm surprised I said this, and it doesn't correspond to my memory of the
> canopies.  I don't remember anything lazy going on there.
> 
> >12. The bert canopy is only used when going northward in
> >   the H-Tree; does this mean the recorder canopy is *only*
> >   used when going southward in the O-Tree?
> 
> The bert canopy is only *read* when going north in the HTree.  It is
> written southward when moving permissions and endorsements around.
> 
> If I recall, the recorder canopy is indeed only read going south in the
> OTree, when moving permissions and endorsements around.  It is written
> northward when placing recorders.
> 
> >And two unrelated questions:
> >
> >1. Should I be posting these questions on the Udanax mailing
> >   list (i.e. are all of you subscribed?) or would you prefer
> >   private correspondence for spamming/privacy reasons?
> >   I'm not always sure whom to email and whom to leave out
> >   of the private stuff, so I'd prefer the mailing list
> >   _if_ you are on it.
> 
> As far as I'm concerned, all of this is public.  I feel confident the rest
> of us feel likewise.  We have all suffered too severely from our past
> secrecy.  I'm not sure what I subscribe to anymore.  How about sending it
> out to Udanax and cc'ing the rest of us?
> 
> Feel free to start by reposting your questions and my answers.
> 
> >2. Are any of you aware of a promising microtransaction,
> >   e-currency system?  The billing system in Xanadu, your
> >   work on E and agorics seem to need that, but none of
> >   the alternatives I've researched are satisfying.  E-gold
> >   seems the most solid, but has a problem (IMHO) with
> >   getting funds into/out of the system at a reasonable
> >   transaction fee (i.e. right now they charge 6-12%).
> >   It also is totally centralized, with issues there.
> 
> Despite the problems, e-gold is the best I'm aware of.  See also the Hansa
> Dollar and GoldMoney.  As for centralization, no one knows how to build a
> truly decentralized issuer.  It's the holy grail of money protocols, but it
> may be impossible.
> 
> The best I know to do is to divide the center into multiple organizations
> along separation-of-duty lines, such that the risk from any one going bad is
> bounded.  E-gold has done a tremendous job of that.
> 
>         Cheers,
>         --MarkM