Billiard Quorums on the Grid

Maekawa considered a simple but suboptimal grid based quorum generation schemein which $N$ sites in a network are logically organized in the form of a$\\sqrt{N} \\times \\sqrt{N}$ grid, and the quorum sets are row-column pairs.Even though the quorum size $2 \\sqrt{N}$ of the grid scheme is twice as largeas finite projective plane based optimal size quorums, it has the advantage ofbeing simple and geometrically evident. In this paper we construct grid basedquorums which use a modified grid, and paths that resemble billiard ball pathsinstead of horizontal and vertical line segments of rows and columns in thegrid scheme. The size of these quorums is $\\sqrt{2} \\sqrt{N}$. Theconstruction and its properties are geometrically evident as in the case ofMaekawa\'s grid, and the quorum sets can be generated efficiently.