What's the best way to track updates when syncing data from MySQL remote server to local SQLite database?

I'm making an iOS App, well, two actually. App A will be able to write TO-DOs to a remote MySQL database, and App B will be able to read what App A has written/modified. App B needs to be always up-to-date and there can be more than one instance of App B running on different iDevices. App B stored the almost-exact copy of what App A has written on the remote MySQL DB, in a local SQLite DB. MySQL operations are handled by a simple PHP script. The problem is how to update App B' local DB when something changes on the remote MySQL database (that is, when App A writes something new or modifies something existing). I came up with two possible solutions: The first is to tell the PHP the last_row_id (the id of the last row that App B has got from the server) so that the PHP can ask MySQL to get all the rows with a greater ID (ID is an auto increment value on MySQL table).

But... This won't help to discover the changed items.

The second solution I thought was to put a "last_updated" column on the MySQL with a timestamp and update it every time the row changes. App B should store the timestamp of the last sync, and report back this value to PHP so that the it can request the MySQL all the rows that have a timestamp greater than the one it receives from App B.

But... Both solutions fail when the MySQL is sharded and clustered. The auto-increment id approach fails because it will no longer be progressive (see auto_increment_offset and auto_increment_increment), and the timestamp approach would be unreliable because the clock can be out of sync on any MySQL server.

How would you solve this problem in a reliable way?