An execution example of the algorithm:
Let T be an tree like this:
R
|_ N1
| |_ N3
| |_ N4
|_ N2
|_ N5
|_ N6
So, an euler tour E of the tree using depth first search could be:
E={R, N1, N3, N1, N4, N1, R, N2, N5, N2, N6, N2, R}
L denotes the level numbers, so we would have:
L={0, 1, 2, 1, 2, 1, 0, 1, 2, 1, 2, 1, 0}
R is an array that contains the index of the first occurrence of node i in
E:
R={0, 1, 7, 2, 4, 8, 10},
where R[0] is the first occurrence of node R in E,
R[1] is the first occurrence of node N1 in E,
R[2] is the first occurrence of node N2 in E, ...
RMQL is a function that gets the index of the smallest element between two
specified indexes in the list L.
Then, if we want the lowest common ancestor between N3 and N5 (that is R) we
have:
lca(N3, N5) = E[RMQL(R[N3],R[N5])]
= E[RMQL(2,8)]
= E[6]
= R
On Mon, Aug 10, 2009 at 8:35 PM, Douglas Leite <[email protected]> wrote:
> Hi,
>
> There was a bug on the previous implementation of the LCA algorithm. The
> bug was solved with the implementation of the Bender and Farach's LCA
> algorithm [1].
>
> Summarizing, the Bender and Farach's algorithm calculates the lca between
> two nodes i and j by:
> *lca(i,j) = E[RMQL(R[i],R[j])]*
>
> Where, *E* is an Euler tour of the tree obtained by listing the nodes
> visited in a depth first search of the tree starting from the root. *RMQL*is
> a function that gets the index of the smallest element between two
> specified indexes in the list *L*. *L* is an array of level numbers such
> that *L[i]* contains the tree-depth of the node *E[i]*. *R* is an array of
> size n such that *R[i]* contains the index of the first occurrence of node
> *i* in *E*.
>
> Regards,
>
> [1]
> http://www.cs.sunysb.edu/~bender/pub/lca.ps<http://www.cs.sunysb.edu/%7Ebender/pub/lca.ps>
>
>
> On Thu, Aug 6, 2009 at 11:42 AM, Douglas Leite <[email protected]>wrote:
>
>> The last updates in my project are related to allowing the existence of
>> concurrent exceptions, as well as providing suitable mechanisms to treat
>> them ([1]). The sequence diagram at [2] shows the messages exchange between
>> the guardian group, guardian members, and participants, when a participant
>> raises an external exception.
>>
>> First of all, the participant that wants to raise an external exception,
>> invokes the *gthrow* method from its respective guardian member. The
>> exception is propagated to the guardian group that set all the involved
>> participants in a suspended state. A participant can assume two states:
>> normal and suspended. When a participant is suspended, it blocks until its
>> state change to the normal state. (However, in the current implementation
>> the participants that did not raise an external exception, continue its
>> normal execution, in a normal state, until an exception is raised in it).
>>
>> After that, the guardian group starts a new thread to process the external
>> exception. The process consists in applying the recovery rules that was
>> defined by the programmer (see an example at [3]). The recovery rules define
>> which exception should be raised in a specific participant (or a set of
>> participants) when an external exception is signaled from a participant to
>> the guardian.
>>
>> While an exception is being processed, another exception may be raised by
>> other participant, in other words, concurrent exceptions may occur. The
>> concurrent exceptions are queued in the guardian group, and before applying
>> the solution described at the recovery rules for the first exception raised,
>> the guardian checks if there are, or not, concurrent exceptions queued.
>>
>> In case of concurrent exceptions, the guardian provides the list of all
>> concurrent exceptions to the concurrent recovery rules. These ones check for
>> the lowest common ancestor (LCA) of all the concurrent exceptions in a
>> resolution tree (see an example at [4]). If there is a LCA, then the
>> guardian invokes the recovery rules for this exception. Otherwise, the
>> guardian simple invokes the recovery rules for each concurrent exception
>> sequentially.
>>
>> In the end, the resolved exception is delivered to the guardian members,
>> and raised in its respective participants by the invocation of the *
>> checkStatusException* method.
>>
>> There are some things related to the design and algorithms that I need to
>> review in order to enhance the model. Despite of that, all the parts of the
>> model were already implemented.
>>
>> Some possible next stpes are:
>>
>> 1) Use the recovery rules and resolution tree as policies;
>> 2) Test the examples with remotable interface;
>> 3) Use implicit declaration of the guardian members;
>>
>> Thoughts?
>>
>> [1]
>> http://svn.apache.org/repos/asf/tuscany/sandbox/dougsleite/guardian-model/
>> [2]
>> http://svn.apache.org/repos/asf/tuscany/sandbox/dougsleite/guardian-model/sequenceDiagram-externalException.jpg
>> [3]
>> http://svn.apache.org/repos/asf/tuscany/sandbox/dougsleite/guardian-model/src/main/resources/recoveryrules_nbackpus.xml
>> [4]
>> http://svn.apache.org/repos/asf/tuscany/sandbox/dougsleite/guardian-model/src/main/resources/resolutionTree.xml
>>
>> --
>> Douglas Siqueira Leite
>> Graduate student at University of Campinas (Unicamp), Brazil
>>
>>
>
>
> --
> Douglas Siqueira Leite
> Graduate student at University of Campinas (Unicamp), Brazil
>
>
--
Douglas Siqueira Leite
Graduate student at University of Campinas (Unicamp), Brazil
