Efficient adaptive collect using randomization |
| |
Authors: | Hagit Attiya Fabian Kuhn C. Greg Plaxton Mirjam Wattenhofer Roger Wattenhofer |
| |
Affiliation: | (1) Department of Computer Science, The Technion, Haifa, 32000, Israel;(2) Deptartment of Information Technology and Electrical Engineering, ETH Zurich, 8092, Zurich, Switzerland;(3) Department of Computer Science, University of Texas at Austin, 1 University Station C0500, Austin, 78712-0233, Texas;(4) Akamai Technologies, Inc., Cambridge, 02142, MA;(5) Deptartment of Computer Science, ETH Zurich, 8092, Zurich, Switzerland |
| |
Abstract: | An adaptive algorithm, whose step complexity adjusts to the number of active processes, is attractive for distributed systems with a highly-variable number of processes. The cornerstone of many adaptive algorithms is an adaptive mechanism to collect up-to-date information from all participating processes. To date, all known collect algorithms either have non-linear step complexity or they are impractical because of unrealistic memory overhead. This paper presents new randomized collect algorithms with asymptotically optimal O(k) step complexity and linear memory overhead only. In addition we present a new deterministic collect algorithm that beats the best step complexity for previous polynomial-memory algorithms. Partially supported by NSF Grants CCR–0310970 and ANI–0326001. A preliminary version of this paper appeared in the Proceedings of the 18th Annual Conference on Distributed Computing (DISC) 2004 [10]. |
| |
Keywords: | Adaptive algorithms Total contention Randomization |
本文献已被 SpringerLink 等数据库收录! |
|