Lower Bounds on Common Knowledge in Distributed Algorithms
Eli M. Gafni, Michael C. Loui, Prasoon Tiwari, Douglas B. West, Shmuel Zaks · McGill-Queen's University Press eBooks · 1986
A B S T R A C T (Continue on reverse if necessary and identify by block number)We establish lower bounds on the communication complexity of several distributed algorithms that achieve common knowledge.On a ring of N processors every comparison algorithm that solves the plurality problem or the distinctness problem requires ft (N2) messages.On a ring of N processors every algorithm that solves the distinctness problem requires iKN log (L/N)) bits among its messages.We include precise definitions of distributed algorithms and their executions.