#Number
TR-PDS-1997-013

#Title 
A Knowledge-Theoretic Analysis of Partitionable Coordination

#Author
Aleta Ricciardi

#Abstract
We apply knowledge-theoretic analyses to the common problem of uniformly
coordinating remote processes in an asynchronous distributed system in
which processes can crash.  In contrast to previous work, we do not assume
a known <i> a priori </i> bound on the number of processes that may crash;
removing that assumption is important for large-scale distributed systems,
and has significant consequences for solvability.  We generalize {\em
exemptions} from coordination and examine specific instantiations.  When
only faulty processes are exempt from coordinating (the usual statement),
our central theorem shows that, in the absence of a known bound on the
number of process failures, uniform coordination requires <i> perfect
failure detection. </i> We define an exemption, called sim-crash, which is
weaker than crashing and, significantly, knowable by processes in these
systems.  We show that it is uniquely responsible for <i> primary partition
behavior.</i> These results, together with the generalization of
exemptions, suggest a direct and formal way in which to define coordination
problems that can make <i> safe </i> progress in minority partitions.  We
give examples of exemptions that are weaker than sim-crash and that lead to
safe partitionable distributed coordination.


#Bib
@techreport{TR9713
        author = {A. Ricciardi},
        title = {{A Knowledge-Theoretic Analysis of Partitionable
Coordination}},  
        institution = {UT Austin},
        number = {PDS-1997-013},
        year = {1997}
}