Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!ucbvax!wisdom.weizmann.ac.IL!udi
From: udi@wisdom.weizmann.ac.IL (Udi Shapiro)
Newsgroups: comp.lang.prolog
Subject: RE: CP, Linda and Multiple Producers.
Message-ID: <8905100742.AA08499@daya.wisdom.weizmann.ac.il>
Date: 10 May 89 07:42:36 GMT
Sender: daemon@ucbvax.BERKELEY.EDU
Lines: 37


        A simulation of Linda's features in CP, appeared in this group
        which was inefficient.
        In fact the complexity of executing n Linda operations seems
        to be n*n.

This was the simplest possible program.  Adding an argument to 'out'
that returns the tail of the Tuple Space incomplete list
and garbage collecting deleted tuples by 'in' would make
a single producer and single consumer communicate  via a Tuple Space
in constant time per operation.  In general the overhead will be linear in
the number of producers/consumers, rather than the number of tuples
they consume or produce.

Using binary search trees can reduce to overhead of any operation to
be logarithmic in the number of operations (or active tuples, if rebalancing
after tuple delection takes place).  Using hash tables an algorithm similar
to (what I think) Linda uses for non-shared memory machines would result.

        It seems to me that an efficient implementation of Linda on any
        concurrent logic programming language would require
        a "linda monitor" but also lots of "merge" invocations.
        Thus, making that Linda Implementation almost impractical.

See my previous answer.

        I believe that one of the problems that CLP languages must face
        in the future is the ability to handle
        multiple producers (of a stream of messages),
        in a simple, efficient and fair way (direct messages to objects?),
        avoiding the ever needed (often unfair) explicit merge invocations
        and the inefficient n*n solution (above).

Fair constant time mergers are known for some time (see the Concurernt
Prolog book), and are used everyone in the Logix system and in applications.

Udi