A tradeoff between safety and liveness for randomized coordinated attack protocols
George Varghese, Nancy Ann Lynch · 1992
We study randomized, synchronous protocols for coordinated attack.Such protocols trade offthe number of rounds (N), the worst case probability of disagreement (U), and the probability that all generals attack (Z).We prove a nearly tight bound on the tradeoff between L and U (L/U ~N) for a strong adversary that destroys any subset of messages.Our techniques may be useful for other problems that allow a nonzero probability of disagreement.