News Archives

[Colloquium] Criticality Metrics on Sorting Algorithms

March 6, 2014

Watch Colloquium: 

MOV file

  • Date: Thursday, March 6, 2014
  • Time: 11:00 am - 12:00 pm 
  • Place: Mechanical Engineering 218

Thomas B. Jones
PhD Candidate
University of New Mexico
Department of Computer Science

Criticality Metrics on Sorting Algorithms

Traditional computation assumes all faults must be suppressed, but now programs operate in environments where faults are inevitable. Faults can cause a computation to return incorrect results, but little is known about which faults are likely to cause the worst damage. This talk will introduce a measure called criticality to formalize that notion. I measure the degree of damage caused in a sorting algorithm’s output by faults in each comparison. The criticality score of each comparison fault is then used to aid in the discovery of points where programs can be armored against faults. I also show that an attacker can use this criticality information to plan an attack against sorting algorithms that will do more damage than a random attack.