[brazzy]

Nope, it absolutely could not, because it requires multiple round trips through the entire network to reach a result, which is completely unworkable to do anything useful with exactly in Stross' scenario.

Basically the whole point of Neptune's Brood is that in this scenario, only the most rudimentary consensus protocols are practical at all, and for security you have no choice but to rely entirely on the fact that subverting a node is prohibitively expensive.