For randomized distributed protocols, the adversary specifies how nondeterminism (e.g. scheduling decisions, failures, which messages get lost, etc.) interacts with randomness. The adversary is essentially a function that chooses the outcome of all nondeterministic events at time t based on the history of the system before time t. Various degrees of adversary power are used in different situations:

Naturally, for maximally intimidating upper bound results, you want to work with an adaptive adversary. But it's often impossible (or just slow) to solve many problems with an adaptive adversary, so a strategic retreat to a weaker adversary allows you to say something positive.

Conversely, for lower bound results, the weaker the adversary the better the result.

It's important when reading (or writing) about randomized distributed protocols to be careful about the power of the adversary. Assuming too weak an adversary may be both mathematically unsatisfying and practically unrealistic.


CategoryDistributedComputingNotes

TypesOfAdversaries (last edited 2007-12-25 23:42:07 by localhost)