Isotach systems are parallel and/or distributed systems designed to provide
synchronization mechanisms with substantially reduced overhead. This is
accomplished by providing strong guarantees regarding message delivery
order. These guarantees provide sequential consistency and atomicity over
the operations performed by parallel programs without the need for more
expensive traditional synchronization methods such as locks and barriers.
Isotach systems achieve event ordering through an extension of Lamport's
notion of logical time: Isotach logical time is represented as an ordered
n-tuple of nonnegative integers. Message logical delivery times satisfy
the isotach invariant, which states that a message sent at time
(i,j,k) will be delivered at time (i+ d, j, k), where d is the logical
distance between the source and destination. Since this invariant guarantees
that messages travel through the network at a constant logical rate, a
process can control the receive time of a message by knowing the logical
distances to destinations, and controlling when messages are emitted into
the network. Logical time is advanced, and the network kept loosely synchronized
(in physical time), through a token passing mechanism. Although Isotach
networks should theoretically achieve greatest efficiency with the help
of special hardware components, they can be built entirely in software
using commercial off-the-shelf hardware. An initial prototype system (dubbed
V1 and described in J. Regehr's Masters thesis, which can be found here)
was built under a DARPA contract by the Isotach group at the University
of Virginia. The three principle system components, the switch interface
unit (SIU), token manager (TM), and shared memory manager (SMM) modules,
were initially implemented in software using a Myrinet
network running Illinois Fast Messages v1.1, and 180 and 200 MHz Pentium
Pro and 166 MHz Pentium machines running Red Hat Linux. In V1, the SIU
code was split between the processors on the Myrinet network interface
boards (LANais) and the corresponding hosts, the TM code ran on
LANai boards attached to hosts whose only purpose was to support the TMs,
and the SMM code ran on each (non TM) host. In the V2 prototype, that
I helped implement, the SIUs and TMs are special hardware devices, with
the SIUs located in-link between the network interface boards and the
switches to which these boards are connected, and the TMs attached directly
to a port on each network switch. My contributions to the Isotach effort
involved implementing a software SIU capable of interoperating with and
testing the hardware SIU, investigating the interplay between various
high performance messaging layers and Isotach primitives, and exploring
general fault tolerance principles in distributed systems and their possible
application to Isotach.
Douglas
C. Szajda, PhD
