[erlang-questions] MPI based BST and AVL

Michael Truog <>
Sat Nov 6 18:27:49 CET 2010


A library that might be useful for parallel algorithms in a functional
language is here:
http://www.cs.cmu.edu/~scandal/nesl.html


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.
>
>
> Jiansen
>
>
> On Fri, Nov 5, 2010 at 11:24 PM, Francis Stephens <
>   
>> 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
>>
>>     
>   



More information about the erlang-questions mailing list