Source-linked AI summary
Actor Model of Computation: Scalable Robust Information Systems
Carl Hewitt
TL;DR
Information integration must handle heterogeneous, overlapping, and inconsistent information while tracking provenance. The paper presents the Actor Model’s asynchronous, concurrent computation and information-system principles as a foundation for inconsistency-robust integration.
Problem
Information integration must connect heterogeneous, overlapping, and often inconsistent information while carefully recording its provenance.
Method
The paper characterizes computation through concurrent Actors that interact by direct asynchronous message passing and applies persistence, concurrency, quasi-commutativity, sponsorship, pluralism, and provenance principles.
Results
The Actor Model is presented as a foundation for inconsistency-robust information integration.
Takeaways & Limitations
Actor-based information systems can link diverse information while preserving concurrency, pluralism, and provenance.
Takeaways & Limitations
Runtime infrastructures cannot guarantee message acknowledgement, reception, or response, and cleanup proceeds on a best-effort basis.
Abstract
from arXiv · showhide
The Actor model is a mathematical theory that treats "Actors" as the universal primitives of concurrent digital computation. The model has been used both as a framework for a theoretical understanding of concurrency, and as the theoretical basis for several practical implementations of concurrent systems. Unlike previous models of computation, the Actor model was inspired by physical laws. It was also influenced by the programming languages Lisp, Simula 67 and Smalltalk-72, as well as ideas for Petri Nets, capability-based systems and packet switching. The advent of massive concurrency through client-cloud computing and many-core computer architectures has galvanized interest in the Actor model. Actor technology will see significant application for integrating all kinds of digital information for individuals, groups, and organizations so their information usefully links together. Information integration needs to make use of the following information system principles: * Persistence. Information is collected and indexed. * Concurrency: Work proceeds interactively and concurrently, overlapping in time. * Quasi-commutativity: Information can be used regardless of whether it initiates new work or become relevant to ongoing work. * Sponsorship: Sponsors provide resources for computation, i.e., processing, storage, and communications. * Pluralism: Information is heterogeneous, overlapping and often inconsistent. * Provenance: The provenance of information is carefully tracked and recorded The Actor Model is intended to provide a foundation for inconsistency robust information integration
Fundamental concepts
The Actor Model defines concurrent computation through Actors that communicate asynchronously by messages, create Actors, and control their future behavior. Its abstraction permits indeterminate message reception, best-effort failure handling, and implementations independent of specific low-level mechanisms.
- Actor primitives: Actors concurrently send messages to addressed Actors, create new Actors, and designate how to handle their next received message.Communication is restricted to Actors whose addresses are available to the communicating Actor.
- Actor primitives: The model is characterized by inherent concurrency, dynamic Actor creation, Actor addresses in messages, and direct asynchronous message passing without restricting message reception order.Decoupling senders from communications enabled asynchronous communication and message-passing control structures.
- Applications: The model provides a framework for modeling concurrent systems including e-mail, Web Services, and objects with locks.Mail accounts, email addresses, SOAP endpoints, and locked objects can be represented as Actors or Actor addresses.
- Asynchronous communication: One-way asynchronous messages are decoupled from senders and delivered on a best-efforts basis, with no required buffers, queues, mailboxes, or other communication overhead.Implementations may use threads, locks, tasks, queues, and related hardware capabilities, but the model does not require exposing them or tying Actors to them.
- Behavior and failures: Message reception order can affect future behavior, so the Actor Model supports indeterminacy; runtime infrastructures handle failures and clean up consequences on a best-effort basis.Message acknowledgement, reception, and response cannot be guaranteed.
Inconsistency by Design for iOrgs
iOrgs treat inconsistency as a manageable feature of organizational information systems, where differing departmental views can be negotiated. The Actor Model provides a computational foundation for inconsistency robustness through scalable organizational structures and principles such as pluralism and provenance.
- Inconsistency by Design for iOrgs: Departmental inconsistencies, such as disagreements between Sales and Accounting about transaction booking, can be negotiated among iOrgs.
- Inconsistency by Design for iOrgs: A fundamental goal of Inconsistency Robustness is reasoning effectively about large amounts of information at high degrees of abstraction.
- Inconsistency by Design for iOrgs: The Actor Model can provide a computational foundation for Inconsistency Robustness in iOrgs.iOrgs address hierarchy, authority, accountability, scalability, and robustness through methods analogous to human organizations.
- Inconsistency by Design for iOrgs: iOrgs scale by mirroring human organizational structures, delegating authority downward and escalating issues upward when necessary.
- Inconsistency by Design for iOrgs: Inconsistency-robust information integration depends on persistence, concurrency, quasi-commutativity, sponsorship, pluralism, and provenance.Pluralism explicitly accommodates heterogeneous, overlapping, and often inconsistent information, while provenance tracks its origins.
Appendix 1. Historical background16
The Actor Model builds on nondeterministic computation models and recasts computation as configurations whose information may be indeterminate. Its relationship to lambda calculus supports modular, extensible concurrent implementations, though purely functional simulation can be exponentially slower.
- Actors represent computation as configurations with potentially indeterminate information, unlike Turing Machines, which use global states determining all computation information.
- Lambda calculus: Lambda-calculus identifiers correspond to Actor addresses, while beta reduction corresponds to message reception with argument addresses replacing substitution.
- Lambda calculus: ActorScript’s lambda-calculus definition makes operations local, modular, extensible, operationalizable for efficient concurrency, and compatible with many-core and distributed frameworks.
- Lambda calculus: The lambda calculus can be implemented in ActorScript through Actor definitions for identifiers, procedure calls, and lambdas with environment-based evaluation.
- Simulating an Actor system with lambda expressions using purely functional programming is exponentially slower in many practical applications.
Petri nets
Petri nets were widely used to model nondeterministic computation, but their control-flow focus limited data-flow modeling and composability, while their simultaneous-transition primitive raised physical-basis concerns.
- Petri nets: Petri nets modeled control flow but not data flow, limiting their composability and modularity.This limitation made Petri nets not readily composable.
- Petri nets: Petri-net transitions simultaneously remove tokens from input places and add them to output places, a physical basis Hewitt questioned.Despite this concern, Petri nets remain popular for modeling nondeterminism and continue to be actively researched.
Capability Actor Systems
Capability systems provide tokens containing Actor addresses and related authorization information for message sending. Actor systems support revocation, delegation, and extensible access-control abstractions, while security levels require additional schemes.
- Capability Actor Systems: Actor Model development clarified capability use, but the terms capability and capability system lacked axiomatizations and denotational semantics, causing ambiguity.Earlier capability addresses were allocated in private operating-system memory, making capabilities awkward to use.
- Capability Actor Systems: Capabilities are tokens containing an Actor address and other information used to send messages to that Actor.Examples include WebKeys and Actor addresses paired with lists of permitted message types.
- Capability Actor Systems: Actors support revocation through proxies or direct communication, and delegation by passing Actor addresses in messages.Actors do not inherently provide security levels, although separate security schemes can be implemented.
- Capability Actor Systems: Access-control systems should extend base protection mechanisms with abstractions that expand the vocabulary for expressing policies.Miller’s analysis argues that evaluating a model requires examining how well it supports extending its own expressiveness.
Simula
Simula pioneered nondeterministic discrete-event simulation, later improving modularity through class inheritance. Simula 67 modeled quasi-parallel processes, but despite its nondeterminism it lacked concurrency.
- Simula: Simula 1 pioneered nondeterministic discrete-event simulation using a global clock.Its early model used a fixed number of active stations, each controlled by a program.
- Simula: Simula modeled systems as stations with queues of customers, where station programs processed, transferred, discarded, or generated customers.Stations could update global, station-local, and customer-local variables before transferring customers to other queues.
- Simula: Simula 67 improved simulation modularity by organizing objects into classes and subclasses that inherit methods from superclasses.This class structure was developed by Kristen Nygaard and Ole-Johan Dahl and first described at an IFIP workshop in 1967.
- Simula: Simula objects acted as quasi-parallel processes that could suspend execution, transfer control, and later resume from their previous position.Each process maintained its own procedure-call stack, enabling simulations to represent independent sequences of events.
- Simula: Although Simula had nondeterminism, it did not have concurrency; its classes named implementations rather than interface types.This contrasts Simula with ActorScript, where types are interfaces that do not name their implementation.
Planner
Planner combined procedural and logical paradigms by invoking procedural plans through patterns in assertions and goals. Its approach contrasted with uniform resolution and with earlier message-passing models that were not well suited to concurrency.
- Planner: Planner hybridized the procedural paradigm of Lisp recursive procedures with the logical paradigm of uniform resolution theorem provers.Implications were procedurally interpreted, rather than handled solely through uniform logical resolution.
- Planner: Planner was the first programming language to invoke procedural plans through patterns in assertions and goals, rejecting uniform resolution as its proof procedure paradigm.Its rules mapped assertions and goals such as P, Q, not Q, and not P to assertions or subgoals.
- Planner: Smalltalk-72’s message passing was tied to machine-model and language-syntax details that did not lend themselves to concurrency, unlike the ActorScript object model.Its interpreter resolved tokens through dynamic context and activation sender chains, while its constructs were not formally defined as objects responding to eval messages.
Actors
The Actor Model frames computation as asynchronous message passing among distributed Actors whose behavior is local, nondeterministic, and influenced by multiple prior computational ideas. Its locality rules constrain stored and communicated addresses while permitting Actor creation, messaging, and state updates.
- Actors communicate asynchronously through addresses, with computation distributed in space rather than represented by a single well-defined global state.The sender of a message is not intrinsic to communication semantics.
- In response to messages, an Actor can create Actors, send messages to permitted addresses, and update local storage for subsequent messages.Permitted addresses come from the received message, local storage, or Actors created by the Actor.
- Actor computation is indeterminate because message-processing arbitration cannot realistically be observed without affecting outcomes, so analysis awaits externally visible results.Arbiters may remain metastable for an unbounded period before asserting either output.
- The Actor Model integrates lambda calculus, interrupts, blocking invocation, locks, capability systems, co-routines, packet networks, email, Petri nets, Smalltalk-72, Simula-67, and Planner.The paper identifies these influences as part of the model’s development.
Indeterminacy in Concurrent Computation
The section argues that sequential global-state models cannot capture essential forms of concurrent computation, including unbounded nondeterminism. Actor semantics instead support physically indeterminate computation, servers that eventually serve every client, and a representation of concurrency without sequential processes.
- Global-State Models: Sequential global-state models represent computation as transitions between global states, while execution prefixes of nondeterministic programs form finitely branching trees analyzed using König's lemma.The supplied discussion concludes that the corresponding proof applies to Abstract State Machines, which therefore are not really models of concurrency.
- Actor Computability: Actor systems implement nondeterministic computable integer functions that nondeterministic Turing machines cannot implement.The supplied proof also states that simulating an Actor system with a Turing machine is exponentially slower in many practical applications.
- Indeterminacy: Actor-counter decision making exhibits physical indeterminacy, unlike the internal decision making of a nondeterministic Turing machine.Unbounded nondeterminism requires guaranteed halting while permitting an output greater than every integer threshold.
- Unbounded Nondeterminism: Actor systems can implement servers that provide service to every client and consequently realize unbounded nondeterminism.The comparison states that nondeterministic Turing machines and logic programs cannot implement unbounded nondeterminism, whereas Actor systems can.
- Actor Semantics: The Computational Representation Theorem characterizes Actor-system semantics without relying on sequential processes, addressing deeper problems caused by nondeterministic global-state foundations.The section presents unbounded nondeterminism as a symptom of those underlying issues in sequential-process models.
Actor Model versus Classical Object Models
The Actor Model differs from Classical Object Models in its computational-physics foundation, support for multiple interfaces, and message-based interaction. Its semantics replace hairy control structures with message-passing techniques while retaining ordering and constructs not reducible to continuation-passing style.
- Actors can implement multiple interfaces and receive messages, whereas Classical Objects belong to class hierarchies and are operated on through virtual procedures.
- The Actor Model’s message-reception ordering is a crucial aspect missed by a reductionist approach based on process primitives.
- Actor semantics enable control structures to be analyzed or synthesized as message-passing patterns, avoiding the paraphernalia of hairy control structure.
- Some Actor programming-language constructs cannot be reduced to continuation-passing style, despite calculations being expressible through continuations.
- Using Actors for computations such as same-fringe obviates explicit coroutine primitives such as yield in C# and JavaScript.
Cosmic Cube
The Cosmic Cube, developed at Caltech by Chuck Seitz and colleagues, provided architectural support for Actor systems through message passing rather than shared variables.
- Cosmic Cube: The Cosmic Cube was a multiple-instruction, multiple-data machine whose hardware and operating system reflected explicit message passing between concurrent processes.This architecture distinguished it from most other parallel processors, which used shared variables for communication.
Communicating Sequential Processes
Communicating Sequential Processes (CSP) addressed concurrency through communicating parallel processes and nondeterministic selection, but its semantics specified bounded nondeterminism. This structure conflicted with the Actor Model’s advocacy of unbounded nondeterminism and guarantees of service.
- CSP specified bounded nondeterminism because Hoare accepted Dijkstra’s argument that unbounded nondeterminism was impossible to implement.
- A CSP example uses three parallel processes whose signal timing creates global nondeterminism and determines whether Z stops or increments n.Process X sends a stop message, process Y repeatedly sends go messages and receives guard values, and process Z nondeterministically accepts either message.
- CSP implementations were encouraged to approximate unbounded nondeterminism, but nondeterministic select statements made that difficult.The select structure chooses between guarded inputs such as X?stop() and Y?go().
- CSP’s communication structure was fundamentally at odds with guaranteeing service, making formal proofs of such guarantees impossible under its stated semantics.
π-Calculus Actors
Milner’s π-calculus work built on the Actor Model by removing restrictions involving process count, message contents, topology, communication timing, and nondeterminism. It also pursued a homogeneous process calculus in which values, operators, and processes are all Actors.
- π-Calculus Actors: Earlier π-calculus-related work used a fixed number of processes, whereas the Actor Model allows the number of Actors to vary dynamically.
- π-Calculus Actors: Milner’s process calculus initially restricted messages to integers and strings, unlike the Actor Model, which allows Actor addresses to be passed in messages.
- π-Calculus Actors: The π-calculus removed restrictions that distinguished Milner’s earlier concurrency work from the Actor Model, including fixed process counts, message contents, topology, synchronous communication, and bounded nondeterminism.The Actor Model permits dynamically varying Actors and topology, passes Actor addresses in messages, allows unbounded delays between sending and receiving, and includes reception ordering.
- π-Calculus Actors: Milner sought a homogeneous process calculus in which values, operators on values, and processes are all the same kind of thing: an Actor.
However, some fundamental differences remain between the Actor Model and the π–calculus … End Notes
The section contrasts Actor-based systems with process calculi and surveys Actor implementations, emphasizing message-based concurrency, practical tradeoffs, and the Actor Model’s renewed relevance as architectures and industry adoption changed. It also records formal results about event ordering and message delivery.
- However, some fundamental differences remain between the Actor Model and the π–calculus: The Actor Model differs from the π–calculus in its physics-based foundations, address-based communication, and message-ordering semantics rather than algebraic equivalence and channel-based communication.The π–calculus can be implemented in Actor systems using two-phase commit, but its communication overhead complicates practical applications.
- J–Machine: The J–Machine provided Actor-oriented architectural support through asynchronous messaging, uniform local and nonlocal addresses, and Actor pipelining, with Concurrent Smalltalk used for programming.These features supported concurrent messaging independently of recipient location and enabled pipelined Actor execution.
- “Fog Cutter” Actors: Fog Cutter Actors model message turns with mailboxes, threads, local state, and programs, but practical Actor systems favor garbage collection, concurrent message processing, and behavior over rigid sequential state machines.Their mailbox structure creates an infinite regress if mailboxes are themselves Actors, while their termination and state assumptions do not fully fit distributed or entangled Actors.
- Erlang Actors: Erlang Actors avoid shared memory and support selective mailbox reception, but impose ordered message delivery and rely on process failure propagation and explicit Actor termination instead of exception handling and garbage collection.Erlang has nevertheless been used in high-performance applications, including Ericsson’s worldwide 3G mobile networks.
- Sqeak: Squeak extends Smalltalk-80 with islands, asynchronous messaging, players, costumes, language extensions, projects, and tile scripting while retaining a class-based object system.Its user interface is programmed as though the object system were prototype-based.
- Orleans Actors: Orleans transparently distributes Actors across computers for scalability and reliability, but single-threaded turns, retained storage, globally unique identifiers, and thread occupancy create memory and performance inefficiencies.The system’s design advances the goal of hiding low-level details from application programmers and has supported high-performance applications, including multiplayer games, despite difficult robustness-performance tradeoffs.
- JavaScript Actors: JavaScript Actors use promises, await, and workers to express asynchronous computation, but worker execution lacks parallel message processing, preemption, and efficient nonlocal communication because messages and addresses must be blobs.A naïve promise composition can fail to execute two Actor calls concurrently, whereas the proposed future await form expresses concurrent calls.
- Was the Actor Model premature / End Notes: The Actor Model was initially neglected while hardware favored faster sequential threads and lacked cross-organizational data standards, but many-core computing, improved intercomputer messaging, and industry adoption made it potentially “before its time.”The End Notes also establish that combined activation and reception order need not be discrete, and that messages need not be delivered in send order, enabling packet-switching optimizations and pipelining.