Efficient logic variables for distributed computing

We define a practical algorithm for distributed rational tree unification a nd prove its correctness in both the off-line and on-line cases. We derive the distributed algorithm from a centralized one, showing clearly the trade -offs between local and distributed execution. The algorithm is used to rea lize logic variables in the Mozart Programming System, which implements the Oz language (see http://www.mozart-oz.org). Oz appears to the programmer a s a concurrent object-oriented language with dataflow synchronization Logic variables implement the dataflow behavior. We show that logic variables ca n easily be added to the more restricted models of Java and ML, thus provid ing an alternative way to do concurrent programming in these languages. We present common distributed programming idioms in a network-transparent way using logic variables. We show that in common cases the algorithm maintains the same message latency as explicit message passing. In addition, it is a ble to handle uncommon cases that arise from the properties of latency tole rance and third-party independence. This is evidence that using logic varia bles in distributed computing is beneficial at both the system and language levels. At the system level, they improve latency tolerance and third-part y independence. At the language level, they help make network-transparent d istribution practical.