Methods implemented in an electronic device are disclosed for checkpoint and rollback recovery in a SDN system. The method utilizes message identifiers to indicate an order of consistent states of forwarding tables of a plurality of network elements of the SDN system. The SDN controller of the SDN system receives a request to recover the network to a previous state, and identifies a consistent state of forwarding table for each of the plurality of network elements utilizing the message identifiers associated the consistent states, where the identified consistent states represent the previous state of the network without the identified consistent states being captured at the same time at the plurality of network elements. The SDN controller indicates the identified consistent state for each of the plurality of the network elements to a corresponding network element, where the corresponding network element makes its forwarding table consistent with the identified consistent state.