[FrontPage] [TitleIndex] [WordIndex

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

For more up-to-date notes see http://www.cs.yale.edu/homes/aspnes/classes/465/notes.pdf.

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.


2014-06-17 11:58