Los protocolos de coherencia de caché basados en tokens son capaces de ofrecer
simultáneamente las principales ventajas de los dos esquemas que tradicionalmente
se han utilizado para implementar los protocolos de coherencia: baja
latencia en los fallos de caché (como en los protocolos basados en snooping) y
no dependencia de redes de interconexión totalmente ordenadas (como en los
protocolos basados en directorio). Los protocolos basados en tokens pueden
aunar esas características gracias en gran parte a la utilización de peticiones no
ordenadas. Desafortunadamente, las peticiones no ordenadas introducen un
problema nuevo, ya que, en caso de competir por un mismo bloque de memoria,
pueden generar carreras de protocolo, lo que impide la resolución de los
fallos de caché. Para eliminar las carreras de protocolo y poder asegurar que
todas las peticiones son finalmente completadas (asegurando así la resolución
de todos los fallos de caché), los protocolos basados en tokens requieren la
utilización de un mecanismo de prevención de inanición.

Los problemas más significativos de los protocolos de coherencia basados
en tokens son causados principalmente por el mecanismo de prevención
de inanición. Aunque hasta ahora se han propuesto varias alternativas para
implementar estos mecanismos, siguen presentando problemas importantes:
primero, son demasiado ineficientes; segundo, consumen unos recursos de almacenamiento
en cada nodo que crecen proporcionalmente con el tamaño del
sistema; y tercero, requieren la utilización de mensajes broadcast. Todos estos
problemas comprometen la escalabilidad de los protocolos basados en tokens
porque, conforme crece el tamaño del sistema, el rendimiento del protocolo
empeora, la cantidad de recursos de almacenamiento requeridos en cada nodo
crece significativamente y el tráfico en la red de interconexión crece de forma
exponencial debido a los mensajes broadcast, lo que causa su congestión. Sin
embargo, éstos no son los únicos problemas serios que comprometen la escalabilidad
del protocolo, ya que ésta también se ve afectada por la utilización de
invalidaciones no silenciosas (non-silent invalidations).

Mientras continue la tendencia a aumentar el número de nodos en los
sistemas multiprocesadores de memoria compartida, se seguirá requiriendo la
utilización de protocolos de coherencia de caché que sean eficientes y escalables.
Teniendo en cuenta ésto, las contribuciones aportadas por esta tesis van dirigidas
a mejorar el rendimiento y la escalabilidad de los protocolos de coherencia
basados en tokens. Para conseguirlo, esta tesis aborda tanto los aspectos más
negativos de los mecanismos de prevencion de inanición como los de las invalidaciones
no silenciosas. La contribución más destacada es la observación de
que ciertos algoritmos de encaminamiento pueden evitar de forma natural que
los protocolos que no están basados en redes totalmente ordenadas ni en directorios
generen carreras de protocolo. Así, mediante la utilización de técnicas
de encaminamiento basadas en caminos ordenados, podemos crear fácilmente
un mecanismo de prevención de inanición eficiente y flexible. Además, esos algoritmos
de encaminamiento nos permiten desarrollar técnicas que mejoren la
escalabilidad del protocolo, reduciendo tanto los recursos de almacenamiento
requeridos por el mecanismo de prevención de inanición como el tráfico de red
generado por los mensajes broadcast. Adicionalmente, estas técnicas se pueden
utilizar también para mejorar la parte de las invalidaciones no silenciosas.