This paper investigates the leader-election problem in the perfect-information model of distributed computing. It is shown that for every $\epsilon < \half$, there exist leader-election protocols for n processors that tolerate $\eps n$ faults.

A slightly random source (with bias$\epsilon $) is a sequence $\mathbf{x} = (\mathbf{x}_1 ,\mathbf{x}_2 , \ldots ,\mathbf{x}_n )$ of random bits such that the conditional probability that $\mathbf{x}_i = 1$, given the outcomes of the first $i - 1$ bits, is always between $\frac{1}{2} - \epsilon $ and $\frac{1}{2} + \epsilon $. Given a subset S of $\{ 0,1\} ^n $, define its $\epsilon $-biased probability to be the minimum of $\text{Pr}[ \mathbf{x} \in S ]$ over all slightly random sources $\mathbf{x}$ with bias $\epsilon $. It is shown that, for every fixed $\epsilon < \frac{1}{2}$ and almost every subset S of $\{ 0,1\} ^n $, the $\epsilon $-biased probability of S is bounded away from 0.

Article Free Access Share on The biased coin problem Authors: Ravi B. Boppana View Profile , Babu O. Narayanan View Profile Authors Info & Claims STOC '93: Proceedings of the twenty-fifth annual ACM symposium on Theory of ComputingJune 1993 Pages 252–257https://doi.org/10.1145/167088.167164Published:01 June 1993Publication History 6citation529DownloadsMetricsTotal Citations6Total Downloads529Last 12 Months33Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF