Practical Utility of Knowledge-Based Analyses: Optimizations and Optimality for an Implementation of Asynchronous, Fail-Stop Processes (Extended Abstract).
Ricciardi, Aleta M.
The Group Membership Problem is concered 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 ISIS 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 ISIS 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 ISIS implementation.
computer science; technical report
Previously Published As