Actors can only do poly work in poly time

[mostawe...@gmail.com]

Hey,

This is a sort of obvious little lemma, but I haven't seen anybody
mention it before. Suppose that an actor has only finitely many behavior-clauses in its script and only finitely many references. Now imagine O(n**k) actors in a network. Given O(t**k) ticks of time, how much work can be done?

Each actor can emit one message per turn per behavior-clause per target reference, so we have O(nt**k) possible messages sent in total. (Actors can't gain additional behavior by having more than one reference to any particular object, so there's only O(n**k) references held by any particular actor.) This is still polynomial.

Note that nothing magical happens compared to other poly-time analyses. The complete analysis of an actor network is in PSPACE if done deterministically, since one would have to build up a table of all of the possible messages sent in order to analyze all of the possible execution paths. This is in line with the idea that actors require non-determinism, and that would put them in NP, which is known to lie in PSPACE.

Note also that P vs NP applies as usual. If we choose a poly-time random oracle, then we can simulate runs of an actor network using CSPRNGs and physical wiring, and this suggests that maybe actors are in BPP, or that some problems could be in BPP when expressed using actors. But in the typical case, we do not have the ability to reliably guess correctly, so we cannot realize NP machines just by appealing to randomness.

This should put to bed whether we need a polynomial-actors complexity class; no, we want that:

* When running with a pseudo-deterministic scheduler on real hardware, actors are in P

* When running with idealized randomness, actors are in BPP

* When running with constraint solvers through all paths, actors are in NP

* When analyzed statically like a chess game, actors are in PSPACE

Peace,

~ C.

[Tony Arcieri]

This general line of reasoning touches upon why modern zero-knowledge proofs are so intriguing: polylogarithmic verification time.

[Tristan Slominski]

"Each actor can emit one message per turn per behavior-clause per target reference."

Not sure if it matters to the argument or not, but this is not true. An actor can emit more than one message to the same target per turn.

On Wed, Feb 10, 2021, 10:20 Tony Arcieri <bas...@gmail.com> wrote:

This general line of reasoning touches upon why modern zero-knowledge proofs are so intriguing: polylogarithmic verification time.

--
You received this message because you are subscribed to the Google Groups "cap-talk" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cap-talk+u...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/cap-talk/CAHOTMV%2BxQmrUDwTGc5r7oWsH7VKstVY1a_hRKusU%2B1kfb2k1vQ%40mail.gmail.com.

[Mike Stay]

Seems relevant:

https://lipn.univ-paris13.fr/~mazza/papers/ChurchCookLevin.pdf

To view this discussion on the web visit https://groups.google.com/d/msgid/cap-talk/CAOXxbHxGJ6SVAO-XoptF3pBER0TrD%3DDbaFdcvHT38eezP6%3D89A%40mail.gmail.com.

--

Mike Stay - meta...@gmail.com
http://math.ucr.edu/~mike
https://reperiendi.wordpress.com

[mostawe...@gmail.com]

You're right and my wording was not clear enough. IIUC Hewitt's actors can't loop within themselves; in order to loop, they have to send themselves a message and wait a tick to be recursively invoked. So ActorScript happens to omit the machinery necessary to have an unbounded number of behaviors get invoked within a single message-handling behavior. Instead, each "behavior-clause" can only run once. I think I meant here that each received message can only run finitely many clauses, and each of those can only send off a single message.

This can definitely be made more rigorous. The idea is that when an actor receives a message, the number of total messages generated are bounded, and moreover they're poly-bounded. This isn't true in some practical ocap systems, like E or Monte, where it's possible to have a while-true loop. But it should be the case for ActorScript as it has been described.

We can double-check the top-level argument, too. If we map out the entire possibility-space for an actor network by writing down the *possible* messages, then do we only need poly-space to do it, or does the number explode and grow exponentially (or worse!?)

Thanks,

~ C.

[mostawe...@gmail.com]

Oh wow! That was a fun read. Definitely relevant and worth coming back to. I'll share another paper which is nearly tangent to the discussion: https://www.researchgate.net/publication/266217730_Pola_a_language_for_PTIME_programming

[Mike Stay]

Strange that they don't cite https://arxiv.org/abs/cs/0402059

> To view this discussion on the web visit https://groups.google.com/d/msgid/cap-talk/cec27615-5470-416b-8e1c-b9b11a005705n%40googlegroups.com.

[Carl Hewitt]

The following Actor program attempts to loop within itself.

In practice, the system will automatically generate an exception when

a go message has not responded in an acceptable time.

ZeroOrLoopsForever:[ ]→N   ≡

   [ ] ↦

      aBuggyCounting←BuggyCounting_∎[ ],     // Bind aBuggyCounting to a newly created BuggyCounting

     aBuggyCounting_∎go|||                                               // Send aBuggyCounting a go message while concurrently

     aBuggyCounting_∎stop▮                                                     // sending aBuggyCounting a stop message

 

BuggyCounting :[ ]→Interface go→Void, stop→Natural |  

 ≡  [ ]  ↦↦                                                                  // Constructor has no arguments

 count := 0,                         // The variable count is initially 0

 continue := False|           // The variable continue is intially False

  go   ↦                  // Override handling of a go message from Counting, so

        continue cases                  // cases for continue are as follows:  

               True then                             // If continue is True,  

                    +1;         // then increment count and afterward

                  (This BuggyCounting)_∎go         // while holding onto the region of mutual exclusion,

                                                                                                    // send a go message to this instance of BuggyCounting  which loops forever counting up

       else Void     // If continue is False, then return Void

         stop  ↦ 

             continue := False;

             count

Regards,

Carl

https://professorhewitt.blogspot.com/

To view this discussion on the web visit https://groups.google.com/d/msgid/cap-talk/2289cd26-fe4d-43b1-8e00-1e9b3597f364n%40googlegroups.com.