Abstract

This work presents a deterministic asynchronous membership protocol (AMP). Conceptually a membership algorithm provides a means of recruiting members (machines) in a distributed system. Currently most of the research in membership recruiting emphasizes how to obtain the members after a machine fail-stop has occurred during the system operation, and the membership algorithms proposed arc non-deterministic. This work extends the research to develop a deterministic membership algorithm to recruit machines dynamically at the system cold-start. Once it is possible to recruit machines at system cold-start, then it is trivial to recruit members after a machine fail-stop has occurred during the system operation.

AMP is to obtain a membership table listing the names and addresses of active machines in the network. The deterministic membership protocol is actually a consensus algorithm; every active machine tries to agree upon the identical membership table. Since it is impossible to tolerate failures in an asynchronous consensus algorithm, an analysis on AMP is presented to show that AMP is an asynchronous consensus algorithm which does not tolerate failures.

To show the correctness of AMP, an algorithm was developed and formally proved. The algorithm was implemented within 7 days and a thorough test was performed to show the correctness of the algorithm as well as the sequential proof. During the implementation only two errors in the original design, and two errors in the original sequential proof, were found and corrected. The errors found in implementation exposed the flaws in the proof system used and the need for automatic proving tools to avoid human mistakes.

Department(s)

Computer Science

Comments

The first and third Authors are Graduate Students.

This report is substantially the M.S. thesis of the first author, completed Summer 1994.

Report Number

CSc-94-14

Document Type

Technical Report

Document Version

Final Version

File Type

text

Language(s)

English

Rights

© 1994 University of Missouri - Rolla, All rights reserved

Publication Date

1 June, 1994

Download

Share

 
COinS