TIGHT LOWER BOUNDS FOR PROBABILISTIC SOLITUDE VERIFICATION ON ANONYMOUS RINGS

A model that captures communication on asynchronous unidirectional rin gs is formalized. Our model incorporates both probabilistic and nondet erministic features and is strictly more powerful than a purely probab ilistic model. Using this model, a collection of tools are developed t hat facilitate studying lower bounds on the expected communication com plexity of Monte Carlo algorithms for language recognition problems on anonymous asynchronous unidirectional rings. The tools are used to es tablish tight lower bounds on the expected bit complexity of the Solit ude Verification problem that asymptotically match upper bounds for th is problem. The bounds demonstrate that, for this problem, the expecte d bit complexity depends subtly on the processors' knowledge of the si ze of the ring and on whether or not processor-detectable termination is required.