indexAbout Isotach Systems

 What is an Isotach system?

 An isotach system is a parallel or distributed computer system that maintains isotach logical time. Isotach logical time extends Lamport's logical time system by relating the logical time required for a message to travel to its destination with the logical distance the message travels.

Thus in an isotach system, the logical time at which a message is received is determined by the logical time it is sent and the logical distance it travels. Assuming that it knows the logical distance its messages travel, a sender can predict and control the logical times at which its messages is received.

In the implementation described here, the logical distance a message travels is the number of switches through which the message travels, but alternative definitions of logical distance are possible. Most applications of isotach systems (causal message delivery is an exception) require that each node know the logical distance or at least an upper bound on the logical distance to each node to which it sends messages.

 Why are Isotach systems useful?

The ability to control the logical time at which messages are received is a powerful coordination mechanism in a distributed or parallel system. A sender that knows the logical distances its messages travel can ensure that a group of messages it sends are received at the same logical time or that they are received is a specified order. The process that issues the messages does not itself have to know the logical distance. This knowledge can be localized in switch interface units (SIUs) that export the services of the isotach system to the application. The SIUs also enforce the rules about sending messages so that they appear to be executed isochronously or in a specified sequence. The application tells the SIU what ordering properties it wants the SIU to enforce, but not how to enforce those properties.

The ordering properties enforced by an isotach system are

These properties are basic to shared memory model computations as well as to message based model computations and to many special applications such as distributed databases, parallel rule-based systems, and distributed control systems.

Although applications can use isotach guarantees without knowledge of how they are implemented, the implementation is important for two reasons: 1) performance issues, including scalability; and 2) additional capabilities that may be offered by the specific implementation.

 How are Isotach systems implemented?

The definition of an isotach system given above leaves room for many different implementations of isotach systems. The prototype system currently being built uses Intel PCs and Myricom's Myrinet, but isotach systems can be implemented on a wide range of computer/network technologies.

Isotach systems can be implemented in many ways, though the performance or scalability will naturally differ with the implementation. Isotach systems can be implemented using entirely commodity parts and without any support for token exchange at the switches.

The pulse component of isotach logical time can be maintained is a distributed way using a simple synchronizer algorithm [Awerbuch, B., Complexity of network synchronization, J. ACM 32 (1985), 804-823]. Initially each device (SIU or switch) sends token wave 1, i.e., it sends a token to each neighbor (immediately adjacent SIU or switch). Thereafter each device sends token wave i+1 when it has received the ith token from each neighbor. This exchange of tokens marks pulse boundaries: the pulse component of the logical time local to a given device is the number of token waves sent by that device.

Between tokens, an SIU sends and receives messages on behalf of its host. It timestamps each message sent with the desired logical receive time, always assigning a TS greater or equal to the current time plus the distance the message travels. Assuming tokens do not overtake messages, a message that is sent in pulse i and travels through d switches is received at the destination SIU before that SIU receives token i+d+1.  The destination SIU sorts the incoming messages in buckets by timestamp. It can safely deliver to the host the sorted bucket for pulse i when it receives the i+1st token because it is guaranteed to have already received all messages with a TS of i or less.

Implementation-specific capabilities

An isotach system that provides hardware support for the exchange of tokens between neighboring devices can easily also provide hardware support for a fast error detection mechanism by piggybacking the error detected signal on tokens. Other system or application level signals can also be piggybacked on tokens. Tokens can also be used to implement a fast barrier mechanism.

[Main Page][About][Papers][People][Projects]