PhD defense Yue Bi: Fundamental Limits and Practical Algorithms for Wireless Distributed Computation and Estimation Systems
Shanghai Jiao Tong University (800 Dongchuan Road, 200240 Shanghai, Software Building, Room 5205) and in videoconferencing
Jury
- Mr. Eduard JORSWIECK, Professor, Technische Universität Braunschweig, Germany (Reviewer)
- Mrs. Angela Yingjun ZHANG, Professor, The Chinese University of Hong Kong, China (Reviewer)
- Mrs. Inbar FIJALKOW, Professor, École Nationale Supérieure de l’Électronique et de ses Applications, France (Rewiewer)
- Mrs. Derya MALAK, Associate Professor, Eurecom, France (Examiner)
- Mr. Cunqing HUA, Professor, Shanghai Jiao Tong University, China (Examiner)
- Mr. Xin WANG, Professor, Fudan University, China (Examiner)
- Mr. Philippe CIBLAT, Professor, Télécom Paris, France (Supervisor)
- Mr. Yue WU, Professor, Shanghai Jiao Tong University, China (Co-supervisor)
Abstract
Distributed systems form the backbone of modern computing applications, enabling collaborative and efficient task execution across multiple networked components. However, the physical separation of system components introduces significant challenges in terms of communication efficiency. This thesis addresses these challenges by investigating information-theoretic limits and proposing practical schemes to enhance the performance of two types of systems: distributed computing (DC) systems and distributed estimation systems. DC systems exploit task parallelization to significantly reduce execution time of computationally intensive tasks.
… divides computation into three phases: map, shuffle, and reduce. The shuffle phase, which involves transferring intermediate values between nodes, is often the bottleneck in terms of execution time. While various coding schemes have been proposed to optimize the shuffle phase in wired networks, the growing adoption of wireless DC systems, necessitates new solutions tailored to wireless environments. Distributed estimation systems, on the other hand, aim to estimate a shared parameter collaboratively across multiple nodes. These systems are widely used in sensor networks, environmental monitoring, and distributed machine learning. Communication efficiency is essential for accurate data fusion, since inaccurate data loss can degrade system performance. This thesis focuses on two scenarios: systems with a fusion center and those without. The main contributions of this thesis are as follows:
1. The thesis investigates partially connected wireless networks, introducing new coding schemes that optimize the computation-communication tradeoff for MapReduce frameworks. Specifically, by analyzing the sum degrees of freedom (SDoF) of partially connected channels, the work derives achievable lower bounds using interference alignment (IA). An information-theoretic analysis is also provided in partially connected wireless networks.
2. The thesis extends IA techniques to optimize wireless MapReduce systems operating over full-duplex interference channels. By designing schemes tailored for specific network configurations, the proposed methods achieve significant improvements in execution time compared to traditional approaches. The work also establishes theoretical upper and lower bounds for the computation-communication tradeoff.
3. For distributed estimation systems requiring a fusion center, the thesis develops a framework to design multi-bit quantizers that minimize the Cramér-Rao bound under worst-case conditions. By applying signomial geometric programming, the proposed quantizers outperform existing methods, particularly in the mid-to-high signal-to-noise ratio regime.
4. The thesis explores distributed estimation in graph-connected networks where nodes exchange information with their neighbors to reach consensus. A synchronous algorithm with stochastic activation is proposed, where nodes activate probabilistically to minimize data collisions while ensuring convergence. By optimizing the activation probability using theoretical bounds, the algorithm achieves a balance between convergence rate and communication efficiency.
In summary, these findings advance the understanding of information-theoretic limits and practical coding strategies, enhancing the performance of distributed systems across diverse applications.