I've also read this paper with great interest.
in reply to Remote MySQL table comparison
Although there are a few potential bugs in the algorithms and in the implementations presented, the idea is both simple and efficient.
Thus I've implemented a new version which hopefully solves some of the weaknesses I found and has a better theoretical behavior. It is dedicated to PostgreSQL, but
may be adapted to other databases.
It is called pg_comparator, a tool for network and time efficient database table content comparison.
http://www.coelho.net/pg_comparator/ for the