Software Security

CompSci 725 S2C 09
Clark Thomborson
Handout 2: Selection of Oral Presentations

Version 1.1: 20 August 2009

Before the first round:

• All papers are in “category 0”, that is, "y Category(y) = = 0
  Category 0: no one assigned to this paper.
  Category 1: 1 student is assigned to this paper.
  Category 2: 2 students are assigned to this paper.
  Category 3: 3 students are assigned to this paper.
• All students are “type 0”: "x Type(x) = = 0
  Type 0: student is not assigned to any paper.
  Type 1: student is assigned to a category 1 paper.
  Type 2: student is assigned to a category 2 paper.
  Type 3: student is assigned to a category 3 paper.
• All students x have been assigned a unique integer Order(x) in the range 1..N, where N is the number of students enrolled.  The ordering integer determines their priority for paper selection, and it defines the order in which they will present their selected paper to the class.  Students with lower Order() numbers have a greater chance of getting their first-choice paper, however they must present sooner.
• The maximum number of papers M has been fixed by the instructor at approximately 0.4N, so that most papers will have three presenters. For example, if there are N = 36 students enrolled, M = 16.
• Note 1: A student x who enrols at any time after the Order() is fixed will be assigned an ordering integer which is larger than that of any other student in the class.
• Note 2: Papers may be added to the recommended list at any time by the instructor.  Suggestions from students are welcome, however the suggested paper must meet with the instructor's approval.

Actions in Round 1:

The instructor describes each paper y on the list of suggested articles. Let X be the set of students who want to present this paper.  Do:

• x1 = argmin( Order(X) ); Paper(x1) = y; Type(x1) = 2; Category(y) = 2;
• if (X>1) then x2 = argmin( Order(X/x1) ); Paper(x2) = y; Type(x2) = 2;
• if (X>2) then x3 = argmin( Order(X/{x1,x2}) ); Paper(x3) = y; Type(x3) = 2;

Postconditions for Round 1:

• "x Type(x) Î {0, 1, 2, 3}
• "p Category(p) Î {0, 1, 2, 3}
• |{p : Category(p) > 0 }|  ≤ M /* No more than M different papers will be presented. */

Actions in Round 2:

Each student x, in assigned order starting with student #1, chooses any one of the following actions:

  1. If ( |{p : Category(p) > 0}| < M ) then student x may select a paper y in category 0.  Do:

Category(y) = 1; Paper(x) = y; Type(x) = 1;

  2. Student x may select a paper y in category 1 or 2: { Category(y)++; Paper(x) = y; Type(x) = Category(y); }

  3. Student x may “pass” this round.

Actions in Rounds 3, ..., 10:

Each student x, in assigned order starting with student #1, must choose one of the following actions.

• If (Type(x) = = 0) this student must select a paper y in this round. There are three cases:
• If fewer than M papers are selected, then a category-0 paper y may be selected. Category(y) + +; Paper(x) = y; Type(x) = 1.
• Student x may select any paper y in category 1 or 2. Category(y) + +; Paper(x) = y; Type(x) = 1.
• Student x may select a paper y in category 3, but only if one of the students z who is currently assigned to y is willing to move to a different paper w in category 1 or 2. Note: student z can move to a paper w in category 0, if less than M papers have been selected.  If there is more than one student willing to move from u, then the student with the lowest number is the "volunteer" z. Category(w)+ +; Paper(z) = w; Paper(x) = y; Type(x) = 1.
• If (Type(x) > 0), then student x may move from their current paper y = Paper(x), by selecting a different paper u. There are four cases:
• If ( (Category(u) = = 0) && (|{p : Category(p) > 0 }| < M) ) { Category(y) – –; Paper(x) = u; Category(u) + +; } /* Student x may choose a paper u in category 0, only if less than M papers have been selected already.
• If (Category(u) = = 1 or Category(u) == 2) { Category(y) – –; Paper(x) = u; Category(u) + +; } /* There are no restrictions on selecting category-1 or category-2 papers. */
• If ( (Category(u) = = 3) && ($z : Category(Paper(z)) = = v, who is willing to move to another paper v in category 1 or 2) ) { Category(y) – –; Paper(x) = v; Category(v) + +; } /* You may ask for a volunteer z to move from a category-3 paper u to a category-1 or category-2 paper v. */
• If (Category(u) = = 3) && ($z : Category(Paper(z)) = = v && z is willing to move to another paper w in category 0 && (|{p : Category(p) > 0 }| < M) ) ) { Category(y) – –; Category(w) + +; Paper(z) = w; Paper(x) = u; } /* A volunteer z can move from a category-2 paper u to a category-0 paper v, only if there are less than M papers selected. */

Postconditions for Rounds > 2:

• "x Type(x) Î {1, 2, 3} /* All registered students must present a paper. */
• "p Category(p) Î {0, 1, 2, 3}
• |{p : Category(p) > 0 }|  ≤ M

Termination Condition:

• Rounds will continue (to a maximum of 10) until a fixed-point is reached, i.e. until a Round makes no changes to the Paper() assignments.

Note:

• Once a student (even one with the highest order #) is assigned a paper, they cannot be forced to "move" to a different paper.