Coherence Protocols for Bus-Based and Scalable Multiprocessors, Internet, and Wireless Distributed Computing Environments: A Survey

Caching has been widely used in many diverse computer applications to improve performance. Although these applications often utilize diverse platforms due to their inherent natures and scope of applicability, there are elements of the caching scheme and the coherence protocol operations that are common to all implementations, regardless of the differences in implementation. This paper attempts to take a wide survey of caching applications to illustrate both the common and the differing elements of caching implementations. Widely researched, traditional caching applications using snoopy (bus-based) and directory protocols will be reviewed, then the relatively newer problems of web caching and the unique implementation issues of wireless networking will be considered. This analysis will be utilized to build a characterization of the various caching implementations, specifically considering the order of complexity in memory requirements, message complexity, message size, and synchronization delay. These parameters will be used to suggest that the underlying network topology, the sharing characteristics and the granularity of the data items being cached strongly affect the performance of coherence protocols.