Abstract:
|
We present a set of local rules to deal with
distributed dictionaries,
having as a main advantage their possible scheduling
in a highly synchronized way to get
massively parallel dictionaries on AVLs.
Recall that, up to now trees
used in massively parallel dictionaries needed
to have all the leaves
at the same depth, such as 2-3 trees. Therefore,
it was possible (in INSERTions and deletions) to reconstruct the tree
bottom-up in a very
regular fashion, as a pipeline of
straight plane waves moving
up. On AVL trees the situation looks different because
leaves can
have different depth, therefore any weave
in a pipeline is
highly irregular. To solve this problem we define
virtual plane waves allowing us to develop an
EREW dictionary for k keys with k processors
and time O(log n + log k).
Later on we generalize the sequential algorithms on brother
trees presented by T. Ottmann and D. Wood in the same way. |