Agencies were to establish these performance management systems by their 2001 senior executive performance appraisal cycles.
They didn't have to establish performance management systems of any kind. 
mnli hypothesis: They didn't have to establish performance management systems of any kind.  premise: Agencies were to establish these performance management systems by their 2001 senior executive performance appraisal cycles.