Popularity Labellings for Steiner Systems
Steiner systems and their duals are widely used for data layout in distributed storage systems. In practice, mapping data items to storage units often ignores the long-term popularity of the items, which can cause a significant imbalance in traffic to storage units. In addressing popularity, two main problems arise:
1. Label the $v$ points of a design with $\{0, 1, ..., v - 1\}$, computing each block sum as the sum of the labels of points contained in that block. The block difference sum is the difference between the largest and smallest block sums. Popularity point labelling seeks to minimize the block difference sum.
2. Label the $b$ blocks of a design with $\{0, 1, ..., b - 1\}$, computing each point sum as the sum of the labels of blocks containing that point. The point difference sum is the difference between the largest and smallest point sums. Popularity block labelling seeks to minimize the point difference sum.
We first derive lower bounds on the difference sums for Steiner systems $S(t, k, v)$. We then outline constructions that yield 'small' difference sums. Finally, we mention some open problems that deserve more attention.
Bio: Charles J. Colbourn was born in Toronto in 1953. He completed his B.Sc. (Toronto), M.Math. (Waterloo), and Ph.D. (Toronto), all in computer science. He held faculty positions at the University of Saskatchewan, the University of Waterloo, and the University of Vermont, and has been a Professor of Computer Science and Engineering at Arizona State University since 2001.
He is co-editor of the Handbook of Combinatorial Designs and author of Triple Systems and The Combinatorics of Network Reliability. He is editor-in-chief of the Journal of Combinatorial Designs. His research concerns applications of combinatorial designs in networking, computing, and Communications.