Ah tiens, je découvre que ce problème a un nom : Two General's Problem.
C'est notamment ce qu'il se passe dans les commit-à-deux-phases des bases de données distribuées (et ACID) ou plus fréquemment sur les négociations via TCP.
C'est un problème démontré comme non calculable.