×

zbMATH — the first resource for mathematics

Virtual time and virtual space. (English) Zbl 0774.68026
Summary: We present a new distributed logic programming model and discuss its implementation. A distributed program is represented by a virtual space - - a set of process which are logical representations of system objects, and is evaluated with respect to virtual time – a temporal coordinate which is used to measure computational progress and specify synchronization. The major focus of the implementation is the ability to accomplish global backtracking. The implementation collects global knowledge through interprocess communication, controls global backtracking distributedly according to virtual time and dependency relations, and capture heuristics in that earlier synchronizations may make subsequent synchronizations more likely to succeed.
As compared with other distributed logic programming systems, our system provides a simpler syntax, well-defined semantics, and an efficient implementation.
MSC:
68N17 Logic programming
68W15 Distributed algorithms
Software:
Prolog; CS-Prolog
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] X. Li, CSP*?A Distributed Logic Programming Language for Discrete Event Simulation, PhD Thesis, University of Calgary (1989).
[2] D. R. Jefferson, Virtual Time,ACM Transactions on Programming Languages and Systems,7(3):404-425 (July 1985).
[3] J. Cleary, B. Unger, and X. Li, A Distributed and Parallel Backtracking Algorithm using Virtual Time,Distributed Simulation, SCS, pp. 177-82 (1988).
[4] I. Futo, Distributed Simulation on Prolog Basis,Distributed Simulation, SCS, pp. 160-165 (1988).
[5] P. Kacsuk, I. Futo, and SZ. Ferenczi Implementing Cs-prolog on a Communicating Process Architecture,J. of Microcomputer Appl.,13:19-41 (1990).
[6] L. M. Pereira and R. Nasr, Delta-prolog: A Distributed Logic Programming Language,The Int’l. Conf. on Fifth Generation Comput. Syst. ICOT (1984).
[7] J. C. Cunhaet al. Delta prolog: A Distributed Logic Programming Language and Its Implementation on Distributed Memory Multiprocessors.Implementations of Distributed Prolog, P. Kacsuk and M. Wise (eds.), John Wiley and Sons, pp. 335-356 (1992).
[8] V. Ambriola, P. Ciancarni, and M. Danelutto, Design and Distributed Implementation of the Parallel Logic Language Shared Prolog,ACM Sigplan Notices,25(3) (March 1990).
[9] J. W. Lloyd,Programming in Logic, Springer Verlag (1984). · Zbl 0547.68005
[10] L. Lamport, Time, Clocks, and the Ordering of Events in a Distributed System,CACM,21(7) (July 1978). · Zbl 0378.68027
[11] M. Abadi and Z. Manna, Temporal Logic Programming,Symp. on Logic Programming, IEEE, pp. 4-16 (1987).
[12] L. Sterling and E. Shapiro,The Art of Prolog, The MIT Press (1986). · Zbl 0605.68002
[13] I. Futo and J. Szeredi, T-prolog: A Very High-level Simulation System, Tech. Rep. Computer Research Institue, H-1015 Budapest Donati, u., pp. 35-45 (1982).
[14] Z. Xiao, B. Cleary, G. Lomow, X. Li, and K. Slind, Jade Virtual time Implementation Manual, Res. Rep. 86/242/16, The University of Calgary, 2500 University Drive NW, Calgary, Alberta, Canada, T2N 1N4 (October 1986).
[15] K. M. Chandy and J. Misra, Distributed simulation: A case study in design and verification of distributed programs,IEEE Tran. on Software Engineering,SE5(5):440-452 (September 1979). · Zbl 05341658
[16] D. Jefferson aand H. Sowizral, Fast Concurrent Simulation Using the Time Warp Mechanism, part I: Local Control, Tech. Rep. The Rand Corporation (December 1982).
[17] J. Y. Halpern and Y. Moses, Knowledge and Common Knowledge in a Distributed Environment,The 3rd Ann. ACM Symp. on Principles of Distributed Computing, ACM, pp. 50-61 (August. 1984).
[18] X. Li, B. Unger, and J. Cleary, Communicating Sequential Prolog,Distributed Simulation, SCS, pp. 166-170 (1988).
[19] B. Unger, G. Birtwistle, J. Cleary, and A. Dewar, A Distributed Software Prototyping and Simulation Environment: Jade.SCS Conf. on Intelligent Simulation Environments, SCS (1986).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.