The Influence of Placement on Transmission in Distributed Computing of Boolean Functions

2024/06/11 by Ahmad Tanha, Tanha, Ahmad, Derya Malak +1
Biochemistry, Genetics and Molecular Biology · Computer Science · #DNA and Biological Computing #FOS: Computer and information sciences #Information Theory (cs.IT) #Neural Networks and Applications #Quantum Computing Algorithms and Architecture

paper · pdf · doi:10.48550/arxiv.2406.07088

openalex publication_date 2024/06/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this paper, we explore a distributed setting, where a user seeks to compute a linearly-separable Boolean function of degree M from N servers, each with a cache size M. Exploiting the fundamental concepts of sensitivity and influences of Boolean functions, we devise a novel approach to capture the interplay between dataset placement across servers and server transmissions and to determine the optimal solution for dataset placement that minimizes the communication cost. In particular, we showcase the achievability of the minimum average joint sensitivity, \fracN2^M-1, as a measure for the communication cost.

Related

• Optimal ordering of transmissions for computing Boolean threhold functions
• Fundamental Limits of Distributed Computing for Linearly Separable Functions
• On Distributed Computing for Functions with Certain Structures
• Multi-Server Multi-Function Distributed Computation
• Optimal strategies for computing symmetric Boolean functions in collocated networks