Exact communication costs for consensus and leader in a tree |
| |
| Authors: | Yefim Dinitz Shlomo Moran Sergio Rajsbaum |
| |
| Institution: | a Department of Computer Science, Ben-Gurion University of the Negev, Israel;b Department of Computer Science, Technion, Israel;c Compaq Cambridge Research Laboratory, MA, USA |
| |
| Abstract: | We continue the study of communication costs of Consensus and Leader initiated in a previous paper. We deal with all scenarios with linear complexity in a tree topology, and prove exact (as opposed to asymptotic) tight bounds for the bit and message complexities. A particular scenario depends on whether the tree size or the size parity is known to the processors. |
| |
| Keywords: | Distributed computing Consensus Leader election Bit complexity Message complexity Communication complexity |
| 本文献已被 ScienceDirect 等数据库收录！ |
