Billiard quorums on the grid

✍ Scribed by Divyakant Agrawal; Ömer Eğecioğlu; Amr El Abbadi

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 646 KB
• Volume: 64
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(97)00145-2

✦ Synopsis

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 fi x fi grid, and the quorum sets are row-column pairs. Even though the quorum size 2fi

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 fiti.

The construction and its properties are geometrically evident as in the case of Maekawa's grid, and the quorum sets can be generated efficiently. @ 1997 Elsevier Science B.V.