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 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
