A multi-protein module is a collection of proteins exhibiting modularity in their interactions. Multi-protein modules may perform essential functions and be conserved by purifying selection. Detecting essential multi-protein modules that change infrequently during evolution is a challenging algorithmic task. A new linear-time algorithm named Produles offers significant algorithmic advantages over previous approaches. An algorithmic framework for evaluation is presented that facilitates evaluation of algorithms for detecting conserved modularity with respect to their algorithmic goals.