Title

Comparison of two torus-based k-coteries

Abstract

We extend a torus-based coterie structure for distributed mutual exclusion to allow k multiple entries in a critical section. In the original coterie, the system nodes are logically arranged in a rectangle, called a torus, in which the last row (column) is followed by the first row (column) using end wraparound. A torus quorum consists of a head and a tail, where the head contains one entire row and the tail contains one node from each of the s succeeding rows, s≥21 is a system parameter. It has been shown that by setting s = [h/2], where h = the number of rows, the collection of torus quorums form an equal-sized, equal-responsibility coterie. In this paper, we propose two extensions to k-coteries: The Div-Torus method divides the system nodes into k clusters and runs a separate instance of a torus coterie in each cluster; the k-Torus method uses quorums of tail s = [h/(k+1)]. We compare the quorum size and quorum availability of the two proposed methods, and against the DIV method which is based on the majority quorums in each of the k divided clusters, assuming the node reliability is a constant. Numerical data demonstrate that DIV and Div-Torus have similar system availability, better than that of the k-Torus, although all 3 methods' availability becomes comparable when the node reliability is higher than 0.9. However, Div-Torus has the smallest quorum size and k-Torus the second smallest, which has the potential of causing less network traffic when requesting permissions from a quorum. We also compare the quorum availability measures of the two proposed k-coteries when the node reliability is not a constant. Numerical data suggest that k-Torus is more robust compared to Div-Torus when nodes of varying reliability are mixed, presumably because clustering makes the system more susceptible to local node failures.

Publication Date

12-1-1998

Publication Title

Proceedings of the Internatoinal Conference on Parallel and Distributed Systems - ICPADS

Number of Pages

300-306

Document Type

Article; Proceedings Paper

Personal Identifier

scopus

Socpus ID

0032291336 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/0032291336

This document is currently not available here.

Share

COinS