ISOTACH NETWORKS

We introduce a class of networks called isotach networks designed to r educe the cost of synchronization in parallel computations. Isotach ne tworks maintain an invariant that allows each process to control the l ogical times at which its messages are received and consequently execu ted. This control allows processes to pipeline operations without sacr ificing sequential consistency and to send isochrons, groups of operat ions that appear to be received and executed as an indivisible unit. I sochrons allow processes to execute atomic actions without locks. Othe r uses of isotach networks include ensuring causal message delivery an d consistency among replicated data. Isotach networks are characterize d by this invariant, not by their topology. They can be implemented in a wide variety of configurations, including NUMA (nonuniform memory a ccess) multiprocessors. Empirical and analytic studies of isotach sync hronization techniques show that they outperform conventional techniqu es, in some cases by an order of magnitude or more. Results presented here assume fault-free systems; we are exploring extension to selected failure models.