We present the first Monte Carlo simulations of kinetic oscillations in heterogeneous catalytic reaction with one of the key reaction steps occurring on the boundaries between the islands formed due to adsorbate-induced surface restructuring. Specifically, we treat NO reduction by CO on the Pt(100) surface with NO decomposition on the interface between the "hex" and (1 x 1) phases. For this scenario, in agreement with experiment, our model predicts damped oscillations with correlation between broad maxima in the CO2-formation rate and minima in the (1 x 1) area.