Phasor Measurement Unit (PMU) sensors are commonly used nowadays for sensing different line parameters of the grid for making it more efficient and reliable. However, they are costly to procure and maintain. Also, they may fail and produce measurements with errors. Towards these issues, a novel optimizationmodel and a polynomial time algorithm are developed that solve these issues with respect to minimal PMU deployment in the grid. These techniques are compared and tested on the standard IEEE 5, 14, 30, 57 and 118 bus systems. For achieving cross-validation and robustness ability in the grid, the developed optimization model and algorithm deploy about 70% and 141% less number of additional PMUs, respectively, as compared with the baseline approach. The results indicate that the developed techniques are very pragmatic and holistic since they take minimal time for allocating minimum PMU sensors while solving problems of cross-validation of PMU measurements and robustness against PMU outages.