Sometimes one plus one doesn't add up to two.
One: OS X's Time Machine can back up a drive to any other drive physically connected to your Mac, internal or external. It can also back up to Apple's Time Capsule--a device that is essentially an AirPort Extreme with a hard drive built in. The advantage of Time Capsule is that its drive is accessible to any Mac on your local network, allowing you to simultaneously back up multiple Macs to the same drive.
Plus one: AirPort Extreme supports adding a hard drive to its USB port. Once connected, you can enable file sharing, allowing multiple users to share data from the drive.
Equals: You would think this adds up to a straight-forward conclusion: Time Machine can back up to a USB drive connected to an AirPort Extreme.
Yes, it seems quite reasonable. But you would be wrong. Apple states: "Time Machine can't backup to an external drive that's connected to an AirPort Extreme...."
This admonition hasn't stopped people from trying to do it anyway. The good news is that, over the years, many users have successfully gotten Time Machine to play nice with a networked USB drive connected to an AirPort Extreme. Many... but far from all. Apple has never clearly spelled out why the setup is unreliable. It just warns against doing it.
I have been one of the lucky ones. More precisely, as I will explain in a moment, I have been half-lucky. On my first try, I was able to successfully get my wife's iMac to back up to a USB drive connected to our AirPort Extreme. This was several years ago. It has performed flawlessly ever since. I wish I could offer some secret tip that accounts for my instant success. But I don't know what it is. It just worked.
However, this success had only limited value for me. If I just wanted to back up my wife's iMac, I could more easily have connected the USB drive directly to her iMac--avoiding the potential AirPort hassles. The real advantage of the AirPort setup would be if I could use the same USB drive to hold Time Machine backups from multiple Macs, especially my Mac Pro.
Unfortunately, every time I enabled Time Machine on my Mac Pro, adding it to the iMac backup already in play, Time Machine failed. Not only did it fail on my Mac Pro but it ultimately brought down the iMac backup as well. The precise error messages varied, but the end result was always the same: I had to trash the Time Machine sparsebundles and start over. Eventually, I gave up and returned to just backing up the iMac.
Recently, speculating that updated software may have improved matters, I retried the multiple Mac setup that had previously failed. Matters had not improved. Adding my Mac Pro still caused a collapse on both Macs. This time, however, the error messages remained consistent: "Time Machine completed a verification of your backups. To improve reliability, Time Machine must create a new backup for you."
As explained in a helpful web article, the message means that the relevant sparsebundles are corrupt. Sometimes, attempting to repair the drive with Disk Utility may get things rolling again. It didn't do so for me. As before, I had to delete the backup files and start over. While the Verification message teases that starting over may prove successful, such was not the case. The error inevitably returned within a day or two.
Searching Apple Support Communities, I found several threads (such as Time Machine Verification Issue) that offered various suggestions on how to deal with this error, including how to potentially reconnect to an existing sparsebundle file rather than starting over from scratch. I was skeptical of this rather involved set of steps, as I suspected the data might still be corrupt even if the reconnect succeeded. So I never gave it a try. None of the other suggestions that I tried had any effect.
I was about ready to give up yet again. I had one remaining idea. Given that backing up just one Mac worked, I reasoned that the corruption was somehow precipitated by attempting to backup two Macs to the same drive. Perhaps, if I partitioned the drive, and backed up each Mac to a separate partition, Time Machine would consider this to be like one Mac per drive--and the error would be avoided. While a few forum postings suggested that partitioning would be more likely to cause trouble than eliminate it, I decided to give it a go. What the hell! If it failed, I would be no worse off than I already was.
It worked! I have now gone a month without any Verification (or any other) Time Machine errors. I've tested out restoring files from the Time Machine backups--and they succeed.
I can't offer any guarantees. I may still get an error tomorrow--or six months from now. However, given past history, I'm optimistic that I'm now home free. So... if you've been unable to get an AirPort-Extreme-connected drive to work with Time Machine and multiple Macs, partitioning may be the solution. Just make sure you have a secondary backup before you start experimenting.