Upon inserting a TransactionCoordinator, the catalog registers a continuation on the coordinator to remove it from the catalog when it completes. If the coordinator's deadline is too short, it is possible that the coordinator inserted is already completed, which would lead the _remove method getting invoked while still under the lock held by insert, which leads to an invariant.
As part of discovering this issue, I also realized that there is another race condition where the TransactionCoordinatorService's scheduler is shut down and the coordinator catalog stepped down just after the new TransactionCoordinator is constructed, the coordinator will not complete, because the deadline task will not run.