I’m not sure this is quite true for S3, but for the general case, once there’s consensus that a record is eligible to be deleted, you don’t require consensus to delete them. You can do it any time after the drop dead date. Once a month for instance.
One of the consensus algorithms Google was bragging about a few years back was built on very high precision hardware clocks that set a ridiculously short timeframe to achieve consensus on new data. After a few hundred milliseconds you could be certain a record had settled and make business decisions based off of it. It’s the same basic idea, but three orders of magnitude faster.
Under the hood most db's do this as well (vacuum, repair database, etc).
At this point I've learned this lesson the hard way enough that I'd need to hear some really good reasons to NOT do it this way.