WaterSluice Software Engineering Methodology

In this section, a family of theorems are presented that pertain to the WaterSluice software engineering methodology. The WaterSluice software engineering methodology will find solutions in static environments and dynamic environments including dynamic environments that have the non-monotonic property. If a solution exists and the WaterSluice software engineering methodology finds the solution, the best case performance is O(1), the worst case performance is O(N), while the average case performance is an order-of-magnitude less than N where N is the total number of steps in the environment.

   

Theorem 4 (WaterSluice: Static Complete)   The WaterSluice software engineering methodology is static complete.  

 

Let $a_1, a_2, a_3, \ldots, a_{n{_a}}$ be the n_a steps leading to the possible analysis A with a₁ being the initial problem statement. Let $d_1, d_2, \ldots, d_{n{_d}}$ be the n_d steps leading to the possible design D. Let $i_1, i_2, \ldots, i_{n{_i}}$ be the n_i steps leading to the possible implementation I. Let $t_1, t_2, \ldots, t_{n{_t}}$ be the n_t steps leading to the possible testing T with t_n<<1931>>4 being the final system acceptance test. Define an environment that consists of the four planes of analysis, design, implementation, and testing with each lower plane being a refinement of the higher planes. In this environment priorities are represented as different in the size of a step. A larger circle represents a higher priority than a smaller circle. Define the solution as the tree, or in a more general sense, the directed acyclic graph, of all steps from all four planes used in the final system. Define a priority queue of possible next steps PQ. Initially the priority queue PQ contains the initial step a₁ represented by the sequence S¹. Define a function, next, over all possible steps, which generates all possible next steps given the current solution sequence, evaluates the total value, and pushes the ordered result onto the priority queue PQ. Only high priority steps are keep in the queue PQ. See Figure 5.13 on page for a visual representation of the space. Here a larger circle represents a higher priority step. See figures 5.13, 5.15, 5.16, 5.17, and 5.18 on pages through for a visual guide of the reasoning. The numbers associated with the steps represent the order visited by the methodology.

  

Figure 5.13: Priority Based Space

  

Figure 5.14: WaterSluice: Proof of Principle

  

Figure 5.15: WaterSluice: Prototype

  

Figure 5.16: WaterSluice: Alpha

  

Figure 5.17: WaterSluice: Beta

  

Figure 5.18: WaterSluice: Product

Proof 4.1  

The WaterSluice methodology leads to this sequence of steps.

step 1: Initial set up. PQ & = & a₁

step 2: Remove a₁ from the priority queue PQ. Expand all alternative steps near a₁ using the function next and push them onto the priority queue PQ.

$$\begin{eqnarray*}PQ & = & a_2 , a_3 \\ S^1 & = & a_1 \end{eqnarray*}$$

At this stage there are two alternative next steps. Pick the next step with the highest priority. For clarity, assume this step is a₂.

step 3:

$$\begin{eqnarray*}PQ & = & a_3, a_4 \\ S^2 & = & a_1, a_2 \end{eqnarray*}$$

$\vdots$

step 11: The methodology is now at the proof of principle stage.

$$\begin{eqnarray*}PQ & = & a_{12} \\ S^{11} & = & a_1, a_2, a_3, d_4, i_5, t_6, d_7, t_8, i_9 , t_{10}, t_{11} \end{eqnarray*}$$

$\vdots$

step 15: The methodology is now at the prototype stage.

$$\begin{eqnarray*}PQ & = & a_{16}, a_{21} \\ S^{15} & = & a_1, a_2, a_3, d_4, i_... ... & & \hspace{0.25in}i_9 , t_{10}, t_{11}, d_{12}, i_{13}, t_{14} \end{eqnarray*}$$

$\vdots$

step 24: The methodology is now at the alpha stage.

$$\begin{eqnarray*}PQ & = & i_{26}, i_{28}, i_{29}, i_{30} \\ S^{15} & = & a_1, a... ..., i_{20}, \\ & & \hspace{0.25in}a_{21} , d_{22}, t_{23}, t_{24} \end{eqnarray*}$$

$\vdots$

step 32: The methodology is now at the beta stage.

$$\begin{eqnarray*}PQ & = & t_{33} \\ S^{15} & = & a_1, a_2, a_3, d_4, i_5, t_6, ... ..., i_{28}, \\ & & \hspace{0.25in}i_{29} , i_{30}, t_{31}, t_{32} \end{eqnarray*}$$

$\vdots$

step n_a + n_d + n_i + n_t: The priority queue contains the last step of the final system acceptance test.

Thus, the WaterSluice software engineering methodology is static complete.

The WaterSluice software engineering methodology uses priority to guide the process combined with the iterative mechanism found in a cyclical methodology and governed by the steady progression found in a sequential methodology. If the environment is static, then all steps in the environment are known before the WaterSluice software engineering methodology begins. The WaterSluice software engineering methodology first discovers high priority steps from the analysis plane, the design plane, the implementation plane, and the testing plane. As higher priority steps are discovered and visited, they are eventually exhausted. This allows the lower priority steps to be visited. The WaterSluice software engineering methodology continues until the only remaining step to visit is the lowest possible priority step.

   

Corollary 4.1 (WaterSluice: Dynamic Complete)   The WaterSluice software engineering methodology is dynamic complete.  

Proof 4.1.1   The WaterSluice software engineering methodology allows for the introduction of new information at every step and the removal of information that is no longer needed. Recall the presence of the priority queue. When steps are placed on the priority queue, the queue is rearranged. Low priority steps migrate to the end of the queue while high priority steps migrate to the beginning of the queue. Regardless of when a high priority item is discovered, the methodology will be able to react. For a dynamic environment, the WaterSluice software engineering methodology will eventually find the solution.

   

Corollary 4.2 (WaterSluice: Non-monotonic Complete)   The WaterSluice software engineering methodology is non-monotonic complete.  

Proof 4.2.1   The WaterSluice software engineering methodology allows for the introduction of new information at every step and the removal of information that is no longer needed. Define a priority function that takes into account non-monotonic steps. Consistent steps are assigned similar high priority. Non-consistent steps are assigned lower priority. When steps are placed on the priority queue, the queue is rearranged. Low priority steps migrate to the end of the queue while high priority steps migrate to the beginning of the queue. Regardless of when a high priority item is discovered, the methodology will be able to react. For a non-monotonic space, the WaterSluice software engineering methodology will eventually find the solution leaving behind the conflicting steps.

   

Corollary 4.3 (WaterSluice: Best Case)   The best case performance of the WaterSluice software engineering methodology is O(1).  

Proof 4.3.1   Let the environment consist of n_a analysis steps, n_d design steps, n_i implementation steps, and n_t testing steps. Let the correct analysis step be the very first step a₁. Let the correct design step be the very first step d₁. Let the correct implementation step be the very first step i₁. Let the system acceptance test be the very first step t₁. To satisfy the problem statement would require one analysis, one design, one implementation, and one testing step. In this environment the WaterSluice software engineering methodology will require only four steps. Thus the performance is O(1).

   

Corollary 4.4 (WaterSluice: Worst Case)   The worst case performance of the WaterSluice software engineering methodology is O(N) where N is the size of the environment.  

Proof 4.4.1   Let the environment consist of n_a analysis steps, n_d design steps, n_i implementation steps, and n_t testing steps. Let the system acceptance test be the lowest priority step t_n<<2119>>t. The number of steps to find a solution is n_a + n_d + n_i + n_t which is O(N).

   

Corollary 4.5 (WaterSluice: Average Case)   The average case performance of the WaterSluice software engineering methodology is an order-of-magnitude less than N where N is the size of the environment.  

Proof 4.5.1  

Let d be the depth of the space. In the special case of this space d is 4. Let b be the average fan out of a step in the space if there was no priority function. If the space has N steps then

$$\begin{eqnarray*}N & = & b^0 + b^1 + b^2 + \cdots + b^{d}. \end{eqnarray*}$$

To a reasonable approximation, only the last term is significant and

$$\begin{eqnarray*}N & \approx & b^{d}. \end{eqnarray*}$$

Consider the addition of a priority function. The best case priority function would guide the algorithm directly to a solution. In this case, the fan out would be 1 and the total number of steps would be O(1). A worst case priority function would not guide the algorithm. Thus the fan out would be b and the total number of steps would be O(N). In the average case, the priority function would trim the fan out by half. Thus

$$\begin{eqnarray*}N_{average} & \approx & {\left( \frac{b}{2} \right) }^d \\ & \approx & \frac{b^d}{2^d} \\ & \approx & \frac{N}{2^d} \end{eqnarray*}$$

On average the performance of the algorithm is an order-of-magnitude less than N.

 

Table 5.1: Summary of Completeness

Methodology	Static Complete	Dynamic Complete	Non-monotonic Complete
sequential	yes	no	no
cyclical	yes	yes	no
WaterSluice	yes	yes	yes

 

 

Table 5.2: Summary of Performance

Methodology	Best	Worst	Average
sequential	O(N)	O(N)	O(N)
cyclical	O(1)	O(N)	O(N)
WaterSluice	O(1)	O(N)	order-of-magnitude less than N