Billiard quorums on the grid

被引:11
作者
Agrawal, D [1 ]
Egecioglu, O [1 ]
ElAbbadi, A [1 ]
机构
[1] UNIV CALIF SANTA BARBARA,DEPT COMP SCI,SANTA BARBARA,CA 93106
关键词
distributed system; mutual exclusion; coterie; quorum;
D O I
10.1016/S0020-0190(97)00145-2
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
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 root N x root N grid, and the quorum sets are row-column pairs. Even though the quorum size 2 root 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 root 2 root 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. (C) 1997 Elsevier Science B.V.
引用
收藏
页码:9 / 16
页数:8
相关论文
共 21 条
[1]  
AGRAWAL D, 1991, ACM T COMPUT SYST, P1
[2]  
Albert A, 1968, An Introduction to Finite Projective Planes
[3]  
CARVALHO OSF, 1983, COMMUN ACM, V26, P146
[4]   THE GRID PROTOCOL - A HIGH-PERFORMANCE SCHEME FOR MAINTAINING REPLICATED DATA [J].
CHEUNG, SY ;
AMMAR, MH ;
AHAMAD, M .
IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, 1992, 4 (06) :582-592
[5]   HOW TO ASSIGN VOTES IN A DISTRIBUTED SYSTEM [J].
GARCIAMOLINA, H ;
BARBARA, D .
JOURNAL OF THE ACM, 1985, 32 (04) :841-860
[6]  
GIFFORD DK, 1979, 7TH P S OP SYST PRIN, P150
[7]   A DISTRIBUTED ALGORITHM FOR MUTUAL EXCLUSION IN AN ARBITRARY NETWORK [J].
HELARY, JM ;
PLOUZEAU, N ;
RAYNAL, M .
COMPUTER JOURNAL, 1988, 31 (04) :289-295
[8]   HIERARCHICAL QUORUM CONSENSUS - A NEW ALGORITHM FOR MANAGING REPLICATED DATA [J].
KUMAR, A .
IEEE TRANSACTIONS ON COMPUTERS, 1991, 40 (09) :996-1004
[9]   A HIGH AVAILABILITY N-SQUARE-ROOT HIERARCHICAL GRID ALGORITHM FOR REPLICATED DATA [J].
KUMAR, A ;
CHEUNG, SY .
INFORMATION PROCESSING LETTERS, 1991, 40 (06) :311-316
[10]   TIME, CLOCKS, AND ORDERING OF EVENTS IN A DISTRIBUTED SYSTEM [J].
LAMPORT, L .
COMMUNICATIONS OF THE ACM, 1978, 21 (07) :558-565