[erlang-questions] MPI based BST and AVL

[Jiansen He]

BST is a common data structure.  In some cases, the speed of producing data
might be faster than the speed of inserting data.  Or, many users might want
to do operations(inserting, deleting, etc.) at the same time, if the tree is
shared by many users.

It is practical to do tree (both BST and AVL) operations concurrently based
on locks and (software transactional memory) STM.  I wonder if it is
practical  to build concurrent BST/AVL in message passing style.

In a locks/STM based concurrent BST/AVL, it is parent node's job to check
the accessibility of child nodes before performing an operation.  This
increase the complexity  of programming.  A beauty of message passing style
is that the sender does not need to worry about the status of receivers.
If a concurrent BST/AVL is build in message passing style, the solution will
be simpler, even if it will not give a better performance.

Please let me know if the problem is not clear.

I plan to build such a tree if I have time.  A design for concurrent BST has
in my mind for a while, but it might be difficulty to build a lock free
concurrent AVL.

In the mean time, I wounder if someone else has implemented this idea, or it
might be in library.


Jiansen


On Fri, Nov 5, 2010 at 11:24 PM, Francis Stephens <francisstephens@REDACTED
> wrote:

> Jiansen,
>
> I am interested in your problem.  However, I don't think I fully understand
> what you are asking.  Are you able to spell out more clearly what problem
> you are trying to solve?
>
> Francis
>