[erlang-questions] MPI based BST and AVL
Sat Nov 6 18:27:49 CET 2010
A library that might be useful for parallel algorithms in a functional
language is here:
On 11/06/2010 08:45 AM, Jiansen He wrote:
> 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.
> On Fri, Nov 5, 2010 at 11:24 PM, Francis Stephens <
>> 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?
More information about the erlang-questions