Bounds on data limits for all-to-all comparison from combinatorial designs

Area of Science:

• Combinatorics
• Computer Science
• Data Storage

Background:

• Efficient data distribution is crucial for large-scale computations requiring all-to-all comparisons.
• The all-to-all comparison (ATAC) data limit quantifies the maximum data fraction on any single machine for optimal distribution.
• Evaluating and minimizing this data limit is key to resource allocation in distributed systems.

Purpose of the Study:

• To further investigate and establish theoretical limits for data distribution in all-to-all comparison scenarios.
• To explore the efficacy of specific combinatorial designs in achieving optimal data distribution.
• To derive improved lower bounds for the ATAC data limit.

Main Methods:

• Analysis of data distribution strategies using combinatorial designs, specifically transversal designs and projective Hjelmslev planes.
• Investigation of relationships between ATAC data limits and established combinatorial parameters like fractional matching numbers and covering numbers.
• Development and proof of a new lower bound for the ATAC data limit.

Main Results:

• Demonstrated achievable data limits using specific combinatorial designs.
• Identified connections between ATAC data limits and fractional matching/covering numbers.
• Established a novel lower bound for the ATAC data limit, improving upon existing bounds.

Conclusions:

• Combinatorial designs offer effective strategies for optimizing data distribution and minimizing the ATAC data limit.
• The study provides a tighter theoretical bound for data distribution efficiency in distributed computing.
• Further analysis of special cases reveals conditions for achieving equality in the derived lower bound.