Hi,<br><br>I'm trying to write a concurrent Binary Search Tree (BST) in Erlang with the operations insert/delete/contains. My goal is for multiple processes to be able to concurrently modify this structure and query it correctly.<br>

<br>My problem is, I can't think of a way to take advantage of the inherent parallelism in the BST structure. BSTs should be easy to parallelize, since different inserts/deletes of nodes from the tree could be in completely different branches. In C for example, it's not hard to write a nonblocking implementation (lock-free) where adding nodes to the tree can happen concurrently (unless there's a conflict) using Compare and Exchange (CAS). Adding concurrency with deleting nodes is a bit more challenging but should still be doable.<br>

<br>That said, I've only managed to think of an Erlang implementation that is capable of running contains() in parallel with an insert or delete. However, I cannot think of a way where I could have the server thread somehow distribute its updates if they are to nonconflicting branches. I feel like the solution should be a simple, recursive one, and that the answer is on the tip of my brain so to speak :) But I'm still baffled.<br>

<br>My question is this; I can reason about shared memory objects and how concurrent accesses should be, either using locks or for the simpler cases using atomic instructions such as CAS. However, I'm finding it difficult to do that with Erlang/functional languages in general. I did a google search, couldn't really find any examples of what I'm looking for. Any tips or pointers?<br>

<br>Here's what my code looks like (the whole thing is attached to this email). Apologies in advance for the quality of my code, still learning :)<br><br>The basic idea, to be able to have contains() run in parallel with insertions and deletions, is that whenever the server gets a request to add something or remove something from the tree, its continue applying contains() to the old version until it receives the modifications back.<br>

<br>The code for the tree itself is pretty much the same as that in Concurrent Programming in Erlang.<br><br>% No changes pending for the tree<br>parallelServer(Tree, stable, _) -><br>    receive<br>        {Requester, insert, Key} -><br>

            Self = self(),<br>            spawn(fun() -> insertProcessor(Self, Key, Tree) end),<br>            parallelServer(Tree, changing, Requester);<br><br>        {Requester, delete, Key} -><br>            Self = self(),<br>

            spawn(fun() -> deleteProcessor(Self, Key, Tree) end),<br>            parallelServer(Tree, changing, Requester);<br><br>        {Requester, contains, Key} -><br>            spawn(fun() -> containsProcessor(Requester, Key, Tree) end),<br>

            parallelServer(Tree, stable, void);<br><br>        {Requester, dump} -><br>            Requester ! Tree,<br>            parallelServer(Tree, stable, void)<br>    end;<br><br>% Tree is being modified<br>parallelServer(Tree, changing, Requester) -><br>

    receive<br>        {Requester, contains, Key} -><br>            spawn(fun() -> containsProcessor(Requester, Key, Tree) end),<br>            parallelServer(Tree, changing, Requester);<br><br>        {Requester, dump} -><br>

            Requester ! Tree,<br>            parallelServer(Tree, changing, Requester);<br><br>        {update, NewTree} -><br>            Requester ! done,<br>            parallelServer(NewTree, stable, void)<br>    end.<br>

<br><br>% insertProcessor and deleteProcessor cannot notify the requester directly to<br>% ensure that parallelServer knows what the new tree is like first for<br>% consistency.<br><br>insertProcessor(Server, Key, Tree) -><br>

    Server ! {update, insert(Key, Tree)}.<br><br><br>deleteProcessor(Server, Key, Tree) -><br>    Server ! {update, delete(Key, Tree)}.<br><br><br>containsProcessor(Requester, Key, Tree) -><br>    Requester ! contains(Key, Tree). % Can report it directly<br>

<br><br><br>Thanks !<br clear="all"><br>Cheers,<br>/Fuad