Distributed Isomorph-free Exhaustive Generation of Anti-Pasch Partial Triple Systems

Abstract

Anti-Pasch partial Steiner triple systems (anti-Pasch PSTSs) arise in erasure codes, extremal set systems, and combinatorial design theory. Maximal anti-Pasch PSTSs correspond to erasure-resilient codes that are used for handling failures in large disk arrays. These codes support the failure of any set of 3 disks and most sets of 4 disks while having the smallest possible update penalty and check-disk overhead.

In this article, we apply a general algorithm for isomorph-free exhaustive generation of incidence structures to the specific case of anti-Pasch PSTSs. We develop and implement a distributed version of the algorithm, which is experimentally analyzed. Using this implementation, we obtain a complete, isomorph-free catalogue of the maximal anti-Pasch PSTSs of order $v$, for $v\le 15$. The enumeration and classification results for $10\le v\le 14$ are new and computationally nontrivial.