Struct snowcap::strategies::StrategyTRTA[][src]

pub struct StrategyTRTA { /* fields omitted */ }
Expand description

One Strategy To Rule Them All

This is the one strategy to rule them all, combining the best from the TreeStrategy and the DepGroupsStrategy into one single strategy.

Description

The stretegy works by exploring the search space of all possible orderings in a tree-like manner. This means, that it proceeds by taking one valid modifier, while building a tree of which leaves need to be explored later. Once there are no other valid modifiers to try, we are stuck.

When we are stuck, we try to solve the current problem by finding a dependency group. This procedure is explained in detail here. If a dependency with a valid solution could be found, then we reset the exploration tree, but with the group now treated as one single modifier. If however no dependency group could be learned, then backtrack in the current exploration tree, until we have either explored everything, or found a valid solution.

Detailed Explenation of finding dependencies

When we are stuck, we try to solve the current problem by finding a dependency group. This is done in three distinct phases. The input to all phases is the current ordering of all groups, including the point where applying the first group fails.

  1. Reduction Phase: In reduciton phase, we try to eliminate groups that seem to have no impact on the dependency group. To do this, we iterate over all groups in the orering (except the problematic group), remove it temporarily from the ordering (to obtain probe_ordering) and simulate this new ordering. If this removal has absolutely no effect on the outcome, we call this group to be independent of the problem.

    Notice, that it might happen that the new ordering now fails at an earlier position. In this case, we recursively call reduce again, but with the probed group removed. Then, we ad the group back to the beginning of the resulting ordering, but only if the call resulted in no additional recursion.

    The following pseudocode illustrates the procedure:

    fn reduce(ordering: Vec<Group>, error: Error) -> Vec<Group> {
    
        for i in 0..ordering.len() - 1 {
            // generate the probe ordering by removing the group at position i.
            let probe_group = ordering[i];
            let probe_ordering = ordering.clone().remove(i);
    
            // check the new group
            match check(probe_ordering) {
                Ok(()) => {
                    // Current ordering is dependent on the probed group, because it solves the
                    // problem.
                }
                Err(new_error) if new_error.position != error.position() => {
                    // The probed ordering fails at a different position! Recursive make the
                    // problem smaller
                    let reduced_ordering = reduce(probe_ordering[..new_error.position + 1]);
                    // insert the probe group back (but only if the level of recursion is
                    // only 1, i.e., the problem was not made smaller by the call to `reduce`
                    // above.)
                    reduced_ordering.insert(0, probe_group);
                    return reduced_ordering;
                }
                Err(new_error) if new_error != error => {
                    // Current ordering is dependent on the probed group, because it changes the
                    // error
                }
                Err(new_error) if new_error == error => {
                    // Current ordering is independent on the probed group, because it has no
                    // effect on the outcome of the network. Remove the group indefinately from
                    // the ordering.
                    ordering.remove(i)
                }
            }
        }
        return ordering
    
    }
  2. Solving Phase: In this phase, we try to find a solution to the reduced problem. This is done using the already existing TreeStrategy. If we can find a valid solution to this problem, then we have found a dependency, and we add it to the list of dependency groups, in the ordering that we have determined. However, if we cannot find any valid solution, we go to step 3 and try to expand the group.

  3. Expansion Phase: In this phase, we try to expand the problem in order to still be abe to find a valid solution. To do this, we iterate over all not yet used groups (excluding those who have already been removed in the reduction phase) and try to place this group at every possible position in the ordering. If the error changes at any point, where the probed grou is moved to, then we add this group to the reduced problem. Once we have found one group with which to extend the problem, we exit and go back to step 2.

    There might be the case, where the probed group changes the problematic group (i.e., the group where the problem happens). In this case, we insert the probed group into this position and go back to step 1, reducing the problem even further.

    The following pseudocode illustrates the procedure:

    fn expand(ordering: Vec<Group>, unused: Vec<Group>, error: Error) -> Result<Vec<Group>> {
    
        // iterate over all unused groups
        for probe_group in unused {
            // iterate over all positions where this gorup might be added
            for i in 0..ordering.range() {
    
                // generate the probe ordering by removing the group at position i.
                let probe_ordering = ordering.clone().insert(i, probe_group);
    
                // check the new group
                match check(probe_ordering) {
                    Ok(()) => {
                        // The probed group seems to be dependent. Add it to the group. Since we
                        // know, that this is already a solved gorup, we can skip the solving
                        // phase, and directly call this a new group
                        return Finish(probe_group)
                    }
                    Err(new_error) if new_error.position != error.position() => {
                        // The probed ordering fails at a different position! Go back to the
                        // reduction phase and make the problem smaller!
                        let reduced_ordering = reduce(probe_ordering[..new_error.position + 1]);
                        // Now, continue to the solving phase
                        return Ok(reduced_ordering);
                    }
                    Err(new_error) if new_error != error => {
                        // Current ordering is dependent on the probed group, because it changes
                        // the error. Continue to the solving phase
                        group.insert(i, probe_group);
                        return Ok(probe_group)
                    }
                    Err(new_error) if new_error == error => {
                        // The probed ordering has the exact same effect as the original one.
                        // Continue moving the probe group to other positions in the ordering,
                        // or continue by going to the next unused group.
                    }
                }
            }
        }
        return Err
    }

Implementations

Returns true if, during exploration, we encountered a dependency without immediate effect.

This method is only available if the "count-states" feature is enabled!

Trait Implementations

Create the strategy

Main function to find a valid reconfiguration sequence (if it exists) and return it. The function also returns the number of sequences that were tested. Read more

Returns the number of states explored by the strategy. Read more

Wrapper, that creates the strategy and synthesizes the network update order.

Auto Trait Implementations

Blanket Implementations

Gets the TypeId of self. Read more

Immutably borrows from an owned value. Read more

Mutably borrows from an owned value. Read more

Performs the conversion.

Performs the conversion.

The type returned in the event of a conversion error.

Performs the conversion.

The type returned in the event of a conversion error.

Performs the conversion.