Practical utility of knowledge-based analyses: optimizations and optimality for an implementation of asynchronous, fail-stop processes
Aleta M. Ricciardi · 1992
The Group Membership Problem is concerned with propagating changes in the membership of a group of processes to the members of that group. A restricted version of this problem allows one to implement a fail-stop failure model of processes in an asynchronous environment assuming a crash failure model. While the Isls Toolkit relies on this for its Failure Detector, the current specification of GMP sheds no light on how to implement it. We present a knowledge-based formulation, cast as a commit-style problem, that is not only easier to understand, but also makes clear where optimizations to the Isls implementation are and are not possible. In addition, the epistemic formulation allows us to use the elegant results of knowledge-acquisition theory to discover a lower bound on the required number of messages, construct a minimal protocol, and discuss the tradeoffs between the message-minimal protocol and the optimized Isls implementation. 1 In t roduct ion Process groups have found widespread use in distributed systems; they arise whenever processes cooperate to perform a task, provide replication for fault-tolerance, tc.. Processes join a group when they recover or desire to participate in the group's activity, and leave a group when they fail. The general Group Membership