IPL, 64 (1997), pp. 9-16.
Divyakant Agrawal, Ömer Egecioglu, and Amr El Abbadi
Billiard Quorums on the Grid
Abstract.
Maekawa considered a simple but suboptimal grid based quorum generation scheme
in 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 large as
finite projective plane based optimal size quorums, it has the advantage of being
simple and geometrically evident. In this paper we construct grid based quorums
which use a modified grid, and paths that resemble billiard ball paths instead of
horizontal and vertical line segments of rows and columns in the grid scheme. The
size of these quorums is $\sqrt{2} \sqrt{N}$. The construction and its properties
are geometrically evident as in the case of Maekawa's grid, and the quorum sets
can be generated efficiently.
omer@cs.ucsb.edu