Abstract

A data processing system stores information in tuple space as tuples that are accessible by multiple entities. Methods, apparatus, computer-readable media, and data structures provide efficient extensions to tuple space coordination languages for example Linda, that increase concurrency by lessening tuple removal, without requiring compile time analysis, altering existing primitives, or adding new primitives. Traces are used to analyze tuple space access in distributed systems, resulting in optimizations based upon certain conditions which, if met, enable a tuple to remain visible in tuple space without blocking, so that other processes can continue to read the tuple while a first process is updating the tuple. A run-time optimization modifies the conditions if the execution is in a closed system that is known not to intentionally contain deadlock, further improving performance.

Other References

• “JavaSpaces Specification”, JINI, Sun Microsystems, Version 1.0.1, 1-24, (Nov. 1999).
• Butcher, P., et al., “Global Synchronisation in Linda”, Concurrency: Practice and Experience, Department of Computer Science; University of York; 6(6), 505-516, (1994).
• Carreira, J., et al., “On the Design of Eilean: A Linda-Like Library for MPI”, Technical Report, Universidade de Coimbra, 9 pages, (1994).
• Carriero, N., et al., “A Foundation for Advanced Compile-time Analysis of Linda Programs”, LNCS 589; Language and Computers for Parallel Computing, Yale University, 390-404, (1991).
• Carriero, N., et al., “Linda in Context”, Communications of the ACM, Artificial Intelligence and Language Processing; vol. 32(4), 444-458, (Apr. 1989).
• Carriero, N., et al., “Tuple Analysis and Partial Evaluation Strategies in the Linda Precompiler”, Languages and Compilers for Parallel Computer, Research Monographs in Parallel and Distributed Computing, MIT Press, 114-125, (1990).
• Ciancarini, P., et al., “Coordinating Java agents over the WWW”, World Wide Web Journal, 1(2), 87-99, (1998).
• Ciancarini, P., et al., “Coordinating Multiagent Applications on the WWW: A Reference Architecture”, IEEE Transactions on Software Engineering, 24(5), 362-366, (1998).
• Ciancarini, P., et al., “Coordination Technologies for Internet Agents”, To Appeal Nordic Journal of Computing, 1-24, (1999).
• De Nicola, R., et al., “KLAIM: A Kernel Language for Agents Interaction and Mobility”, IEEE Transactions on Software Engineering, vol. 24, No. 5, 315-330, (May 1998).
• Omicini, A., et al., “Tuple Centres for the Coordination of Internet Agents”, To appeal Autonomous Agents and Multi-agent Systems, Special Issue on Coordination Mechanisms and Patterns for Web Agents, 1-8, (1999).
• Picco, G.P., et al., “LIME: Linda Meets Mobility”, Technical Report—Technical Report WUCS 98-21, Washington University, Department of Computer Science, St. Louis Missouri, 10 pages, (1998).
• Rowston, A., “WCL: A Co-ordination Language for Geographically Distributed”, World Wide Web Journal, 1(3), 167-179, (1998).
• Rowstron, A., “Mobile Co-ordination: Providing fault tolerance in tuple space based co-ordination languages”, Coordination99, vol. 1594 of LNCS, Springer-Verlag, 196-210, (1999).
• Rowstron, A., et al., “Bonita: A set of tuple space primitives for distributed coordination”, HICSS-30, IEEE CS Press, vol. 1, 379-388, (1997).
• Rowstron, A., et al., “Solving the Linda multiple rd problem using the copy-collect primitive”, Science of Computer Programming, Computer Laboratory, University of Cambridge, Department of Computer Science, University of York, 31(2-3), 1-27, (May 6, 1997).
• Wyckoff, P., et al., “T Spaces”, IBM Systems Journal, vol. 37, No. 3, 454-474, (1998).