Lecture
In computer science, the model of actors is a mathematical model of parallel computing, which treats the concept of “actor” as a universal primitive of parallel numerical calculation: in response to messages that it receives, the actor can make local decisions, create new actors, send their messages, and establish how to respond to subsequent messages. The model of actors appeared in 1973. [1] It was used as a basis for understanding the calculus of processes and as a theoretical basis for a number of practical implementations of parallel systems.
Unlike previous computational models, the emergence of the actor model was stimulated by physics, including the general theory of relativity and quantum mechanics. The process of forming the model was also influenced by the programming languages Lisp, Simula and earlier versions of Smalltalk, as well as methods of parametric protection and packet switching. The development of the model was “motivated by the prospect of highly parallel computers consisting of tens, hundreds and even thousands of independent microprocessors, each with its own local memory and communication processor communicating through a network of high-performance communications”. [2] With the massive proliferation of parallelism, which arose due to the development of multi-core architectures, interest in the model of actors has increased significantly.
Following the publication of Hewitt, Bishop, and Steiger in 1973, Irene Greif developed the operational semantics for the model of actors as part of her doctoral dissertation. [3] Two years later, Henry Baker and Hewitt published many axiomatic laws for actor systems. [4] Other significant milestones include William Klinger's dissertation in 1981, [2] presenting denotative semantics based on domain power, and Guhl Agh's dissertation in 1985, which further developed Klinger's semantic model. [5] As a result of these works, the theory of the actor model was fully developed.
The model of actors proceeds from such a philosophy that everything around is actors . This is similar to the philosophy of object-oriented programming, where everything around is some objects , but differs in that in object-oriented programming, programs are usually executed sequentially, while in the model of actors, the calculations are essentially the same.
The actor is a computational entity that, in response to a received message, can simultaneously:
There may be an arbitrary sequence of the above actions, and all of them can be performed in parallel.
Decoupling the sender and the sent messages was a fundamental achievement of the actor model, which provided asynchronous communication and control of structures as a prototype of message passing. [6]
Message recipients are identified by an address, which is sometimes called a “postal address”. Thus, an actor can interact only with those actors whose addresses it has. He can extract addresses from received messages or know them in advance if the actor is created by himself.
The model of actors is characterized by the inherent parallelism of computations within and between one actor, the dynamic creation of actors, the inclusion of the addresses of actors in messages, and the interaction only through direct asynchronous message exchange without any restrictions on the order of arrival of messages.
Over the past years, several different formal systems have been developed that allow us to describe models of actors. These include:
There are also formalisms that do not fully correspond to the model of actors in the aspect that they do not formalize guaranteed delivery of messages. These include, in particular:
The model of actors can be used as a basis for modeling, understanding and arguing over a wide range of parallel systems, for example:
The model of actors was formed on the basis of the previous models of calculations.
Alonzo Church's Lambda Calculus can be thought of as the very first messaging programming language. [1] (see also Abelson and Sussman 1985). For example, the following lambda expression implements a tree data structure if it is used with the leftSubTree and rightSubTree parameters. If at the input of such a tree we give the message "getLeft" as a parameter, it will return the leftSubTree , and if we give the message "getRight" , then the rightSubTree will return.
λ (leftSubTree, rightSubTree)
λ (message)
if (message == "getLeft") then leftSubTree
else if (message == "getRight") then rightSubTree
The semantics of lambda calculus is expressed using variable substitutions, in which the values of the parameters are replaced in the body of the lambda expressions being called. The substitution model is unsuitable for concurrency because it does not provide for the possibility of sharing resources. Under the influence of lambda calculus, the Lisp programming language interpreter uses data structures called environment, such that parameter values should not be replaced in the body of lambda expressions being run. It shares the effects of updating common data structures, but does not provide concurrency.
Simula was a pioneer in the use of messaging for computing related to discrete event modeling applications. In previous modeling languages, these applications were cumbersome and non-modular. At each time step, it was necessary to execute a large central program and update the states of each modeled object, depending on the state of other objects with which the object interacted at the current modeling step. Kristen Nyugord and Ole-Johan Dahl were the first to develop the idea (first set out at an IFIP seminar in 1967) using methods built into each object that update their own states based on messages from other objects. In addition, they introduced class structures for objects with inheritance. Their innovations have significantly increased the modularity of programs.
However, in the Simula, instead of true parallelism, the coroutines for managing structures were used.
When developing Smalltalk-71, Alan Kay was influenced by the ability to transfer messages in pattern-driven calls to the Planner language. Hewitt was intrigued by Smalltalk-71, but postponed its use due to the complexity of communications, which include calls with many fields, including global , sender , receiver , reply-style , status , reply , operator selector , etc.
In 1972, Kay visited MIT and discussed some of his ideas for Smalltalk-72, based on the capabilities of the Seymour Papert programming language and on the “little man” computing model used to teach children programming. However, messaging in Smalltalk-72 was quite complex. The language code was interpreted by the interpreter simply as a stream of characters. As Dan Ingols later wrote:
The first character encountered in the dynamic context in the program was used to determine the recipient of the subsequent message. The search for a name began with a dictionary type in the current activation. In case of an error, the message was redirected to the creator of the activation, and so on along the chain, up to the sender of the message. When the binding finally found the symbol, its value was assigned to the recipient of the new message, and the interpreter activated the code for the class of this object.
Thus, the transfer of messages in Smalltalk-72 was closely tied to a specific machine model and to the syntax of a programming language that was not adapted for parallelism. In addition, although the system loaded itself, language constructs were not formally defined as objects that respond to Eval messages (see discussion below). This allowed some to conclude that a new mathematical model of parallel computing based on message passing should be simpler than Smalltalk-72.
Subsequent versions of the Smalltalk language have largely evolved along the path of using virtual methods from the Simula language in message transfer program structures. However, in Smalltalk-72, primitives appeared in objects, such as integers, floating point numbers, etc. The authors of the Simula language considered the adoption of such primitives in objects, but refrained from this, mainly for reasons of efficiency. In Java, at first they thought it appropriate to use both primitives and versions of objects of integers, floating-point numbers, etc. In the C # programming language (and later versions of Java, starting with Java 1.5), the less elegant decision was to use packaging and unpacking . previously used in some Lisp implementations.
The Smalltalk system subsequently became very popular and influential, having an innovative impact on raster displays, personal computers, the browser interface and much more. [12] In the meantime, the efforts of the actors ’model developers at MTI have focused on developing the scientific and technical foundations of a higher level of parallelism.
Before the advent of the Petri network actor model, they were widely used to model non-deterministic calculations. However, it was recognized that they have an important limitation: they simulate flow control, but not the data flow itself. Therefore, they were not easily composable, thereby limiting their modularity. Hewitt noted another problem with Petri nets: the complexity of simultaneous actions. The elementary step of calculations in the Petri net is a transition, in which the tokens simultaneously disappear at the transition inputs and appear at its outputs. The physical basis of using primitives with such simultaneity turned out to be dubious. Despite these obvious difficulties, the Petri nets method remains a popular approach to the modeling of parallelism, and is still the subject of active research.
Before the actor model, concurrency was defined in low-level hardware terms through threads, locks, and buffers (channels). It is not by chance, of course, that the implementation of the actor model usually uses these hardware capabilities. However, there is no reason to believe that the model cannot be implemented directly in hardware without equivalent hardware threads and locks. In addition, there is no obligatory connection between actors, threads and locks that may be involved in calculations. Implementations of the actor model are not directly related to threads and locks in all cases compatible with the laws for actors.
Here is what can be said about the semantics of transmitted messages in the model of actors.
Perhaps the first parallel programs were interrupt handlers. In the course of work, as a rule, the computer needs to respond to external events that may occur at a previously unknown point in time (asynchronously, with respect to the program currently running) —for example, to receive information from the outside (characters from the keyboard, packets from the network, and t .d.) The most effective processing of such events is implemented using the so-called interrupts - when an event occurs, the execution of the current program is “interrupted” and the interrupt handler is started, which performs the necessary actions to react to the event (for example, it receives incoming information and stores it into a buffer, from where it can be subsequently read), after which the main program continues their work from the place where it was interrupted.
In the early 1960s, interrupts were used to simulate the simultaneous execution of several programs on a single processor. [13] The presence of concurrency with shared memory led to the problem of concurrency control. Initially, this task was conceived as one of the mutexes on a separate computer. Edsger Dijkstra developed semaphores, and later, between 1971 and 1973, Charles Hoar and Per Hansen developed monitors to solve the problem of mutexes. [14] [15] [16] However, none of these solutions created constructions in programming languages that would encapsulate access to shared resources. Hewitt and Atkinson did the encapsulation later by building a parallel-to-serial converter ([Hewitt, Atkinson 1977, 1979] and [Atkinson 1980]).
The first models of computation (for example, the Turing machine, the Post machine, lambda calculus, etc.) were based on mathematics and used the concept of a global state to determine the computation step (these concepts were later summarized in [McCarthy and Hayes 1969] and [ Dijkstra 1976]). Each computation step went from one global state of computation to the next. The global approach to state was continued in the theory of automata for finite-state machines and machines with a stack, including their non-deterministic versions. Such non-deterministic automata have the property of limited indeterminism. That is, if the machine always faces the transition to the initial state, then there is a limit on the number of states in which it can be.
Edsger Dijkstra further developed an approach with non-deterministic global states. Dijkstra’s model spawned disputes about unlimited indeterminism . Unlimited indeterminism (also called unlimited non-determinism ) is a property of simultaneous calculations where the delay in servicing a request can become unlimited as a result of arbitration rivalry for shared resources, while at the same time it is guaranteed that the request is ultimately served . Hewitt argues that the model of actors should provide guarantees for the provision of services. Although the Dijkstra model cannot have an unlimited amount of time between performing sequential operations on a computer, a parallel program that started its work in a strictly defined state can be interrupted only in a limited number of states [Dijkstra 1976]. Consequently, the Dijkstra model cannot provide a guarantee for the service. Dijkstra argued that it was impossible to realize unlimited indeterminism.
Hewitt argued otherwise: there is no limit on the time that is spent on the work of the area of computing, called the arbitrator for resolving conflicts. Arbitrators deal with the resolution of such situations. The computer clock works asynchronously with external inputs: keyboard input, disk access, network input, etc. So, it can take an unlimited time to receive a message sent to a computer, and during that time the computer can go through an unlimited number of states.
Unlimited indeterminism is a characteristic feature of the actor model, which uses the mathematical model of Bill Klinger, based on the theory of domains. [2] There is no global state in the actor model.
Messages in the actor model are not necessarily buffered. This is its sharp difference with the previous approaches to the model of simultaneous calculations. The lack of buffering caused a great deal of misunderstanding during the development of the model of actors, and this topic is still a subject of controversy. Some researchers claim that messages are buffered in the "air" or "environment." In addition, messages in the actor model are simply sent (for example, packets in IP). There are no requirements for a synchronous handshake with the recipient.
Естественным развитием модели акторов была возможность передачи адресов в сообщениях. Под влиянием сетей с коммутацией пакетов Хьюитт предложил разработать новую модель одновременных вычислений, в которой связь не будет иметь вообще никаких обязательных полей, все они могут быть пустыми. Конечно, если отправитель сообщения желает, чтобы получатель имел доступ к адресам, которых он ещё не имеет, адрес должен быть отправлен в сообщении.
В процессе вычислений, возможно, потребуется отправить сообщение получателю, от которого позже нужно получить ответ. Способ сделать это состоит в том, чтобы отправить сообщение, в котором записан адрес другого актора, называемого возобновлением (иногда его также называют продолжением или стеком вызовов ). Получатель может затем сделать ответное сообщение, которое будет отправлено на возобновление .
Создание акторов плюс включение адресов участников в сообщения означает, что модель акторов имеет потенциально переменную топологию в своих отношениях друг с другом, походя на объекты в языке Симула, которые в своих отношениях друг с другом также имеют переменную топологию.
В отличие от предыдущего подхода, основанного на комбинировании последовательных процессов, модель акторов была разработана как одновременная модель по своей сути. Как написано в теории моделей акторов, последовательность в ней представляет собой особый случай, вытекающий из одновременных вычислений.
Хьюитт был против включения требований о том, что сообщения должны прибывать в том порядке, в котором они отправлены на модель актора. Если желательно упорядочить входящие сообщения, то это можно смоделировать с помощью очереди акторов, которая обеспечивает такую функциональность. Такие очереди акторов упорядочивали бы поступающие сообщения так, чтобы они были получены в порядке FIFO. В общем же случае, если актор X отправляет сообщение M1 актору Y , а затем тот же актор X отправляет другое сообщение M2 к Y , то не существует никаких требований о том, что M1 придёт к Y раньше M2 .
In this regard, the actor model mirrors the packet switching system, which does not guarantee that the packets will be received in the order they are sent. The lack of guarantees for message delivery allows the packet switching system to buffer packets, use several ways to send packets, re-forward damaged packets, and use other optimization methods.
For example, actors can use a message processing pipeline. This means that during the processing of an M1 message, the actor can vary the behavior that will be used to process the next message. In particular, this means that it can begin processing another M2 message before completing M1 processing . On the grounds that the actor has the right to use the message processing pipeline, does not mean that he is obliged to использовать. Будет ли сообщение конвейеризовано или нет — относится к задачам технического компромисса. Как внешний наблюдатель может узнать, что обработка сообщения актора прошла через конвейер? На этот счёт не существует никакой двусмысленности в отношении применения актором возможности конвейеризации. Только если в конкретной реализации выполнение конвейерной оптимизации сделано неправильно, в этом случае может произойти не ожидаемое поведение, а нечто другое.
Другой важной характеристикой модели акторов является локальность. Локальность означает, что при обработке сообщения актор может отправлять сообщения только по тем адресам, которые он получил из этого сообщения, по адресам, которые он уже имел до получения сообщения, и по адресам, которые он создал при обработке сообщения.
Локальность также означает, что не может одновременно произойти несколько изменений адресов. В этом отношении модель акторов отличается от некоторых других моделей параллелизма, например, от сетей Петри, в которых реализации одновременно могут быть удалены из нескольких позиций и размещены по другим адресам.
Идея композиции систем акторов в более крупные образования является важным аспектом модульности, которая была разработана в докторской диссертации Гуля Ага [5] , позже развитой им же вместе с Ианом Мейсоном, Скоттом Смитом и Каролин Талкотт. [7]
Основным новшеством модели акторов было введение понятия поведения , определённое как математическая функция, выражающая действия актора, когда он обрабатывает сообщения, включая определение нового поведения на обработку следующего поступившего сообщения. Поведение обеспечивает функционирование математической модели параллелизма.
Поведение также освобождает модель акторов от деталей реализации, как, например, в Smalltalk-72 это делает маркер интерпретатора потока. Однако, важно понимать, что эффективное внедрение систем, описываемых моделью акторов, требует расширенную оптимизацию.
Другие системы параллелизма (например, исчисление процессов) могут быть смоделированы в модели акторов с использованием двухфазного протокола фиксации. [17]
В модели акторов существует теорема вычислительных представлений для замкнутых систем, в том смысле, что они не получают сообщений извне. В математической записи замкнутая система, обозначаемая как S , строится как наилучшее приближение для начального поведения, называемого ⊥ S , с использованием аппроксимирующей функции поведения progression S , построенной для S следующим образом (согласно публикации Хьюитта 2008 г.):
Denote S ≡ ⊔ i∈ω progression S i (⊥ S )
Таким образом, S может быть математически охарактеризована в терминах всех его возможных поведений (в том числе с учётом неограниченного индетерминизма). Хотя Denote S не является реализацией S , она может быть использована для доказательства обобщения тезиса Чёрча-Тьюринга-Россера-Клини (см. Клини, 1943):
Теорема перечислимости : если примитив актора замкнутой системы акторов являются эффективным, то его возможные выходы рекурсивно перечислимы.Доказательство: непосредственно вытекает из теоремы вычислительных представлений.
Развитие модели акторов имеет интересную связь с математической логикой. Одной из ключевых мотиваций для её развития была необходимость управления аспектами, которые возникли в процессе развития языка программирования Planner. После того как модель акторов была первоначально сформулирована, стало важно определить мощность модели в отношении тезиса Роберта Ковальского о том, что «вычисления могут быть сгруппированы по логическим выводам». Тезис Ковальского оказался ложным для одновременных вычислений в модели акторов. Этот результат всё ещё является спорным, и он противоречит некоторым предыдущим представлениям, поскольку тезис Ковальского верен для последовательных вычислений и даже для некоторых видов параллельных вычислений, например, для лямбда-исчислений.
Тем не менее были предприняты попытки расширения логического программирования для одновременных вычислений. Однако, Хьюитт и Ага в работе 1999 г. утверждают, что результирующая система не является дедуктивной в следующем смысле: вычислительные шаги параллельных систем программирования логики не следуют дедуктивно из предыдущих шагов.
Миграцией в модели акторов называется способность актора изменить своё местоположение. Например, Аки Йонезава в своей диссертации моделировал почтовую службу, в которой акторы-клиенты могли войти, изменить местоположение во время работы и выйти. Актор, который мог мигрировать, моделировался как актор с определённым местом, изменяющемся при миграции актора. Однако достоверность этого моделирования является спорной и служит предметом исследований.
The security of actors can be provided in one of the following ways:
A subtle point in the model of actors is the ability to synthesize the address of the actor. In some cases, the security system may prohibit the synthesis of addresses. Since the address of the actor is just a bit string, then obviously it can be synthesized, although, if the bit string is long enough, finding the address of the actor is rather difficult or even impossible. SOAP uses the URL where the actor is located as the endpoint address. Since the URL is a string of characters, then, obviously, it can be synthesized, although if you use encryption, then pick up the string is almost impossible.
Actor address synthesis is usually modeled using a mapping. The idea is to use the actor system to map to the actual addresses of the actors. For example, the memory structure of a computer can be modeled as an actor system that gives a mapping. In the case of SOAP addresses, this is DNS modeling and URL mapping.
The first of Robin Milner’s published papers on concurrency [18] was remarkable in that it was not based on a composition of sequential processes. His work differed from the model of actors, because it was based on a fixed number of processes of a fixed number of links in the topology of rows used to synchronize communications. The original model of interacting sequential processes (CSP), published by Anthony Hoare [19] , differs from the model of actors, because it is based on the parallel composition of a fixed number of sequential processes connected to a fixed topology and communicating using synchronous message passing based on process names. Later versions of CSP refused to communicate based on process names, adopting the principle of anonymous communication through channels. This approach is also used in Milner’s work on calculus of communicating systems and pi calculus.
These two early models of Milner and Hoare have limited indeterminism. Modern theoretical CSP ([Hoare 1985] and [Roscoe 2005]) explicitly provide for unlimited indeterminism.
Forty years after the publication of Moore's law, the continued increase in the performance of microcircuits is due to the methods of local and global mass parallelism. Local parallelism is used in new chips for 64-bit multi-core microprocessors, in multi-chip modules and high-performance communication systems. Global parallelism is currently involved in new equipment for wired and wireless broadband packet switching of messages (see Wi-Fi and Ultra Wideband). Storage capacity due to both local and global parallelism is growing exponentially.
According to Hewitt (see Carl Hewitt, 2006a), the model of actors poses questions in the field of computers and communications architecture, parallel programming languages, and web services, including the following:
Many of the ideas introduced in actor models are now also used in multi-agent systems for the same reasons (see Hewitt, 2006b, 2007b). The key difference is that the system agent (in most definitions) imposes additional restrictions on the actors, as a rule, requiring them to use commitments and goals.
The actor model is also used in cloud computing clients. [20]
Early programming languages with actors A large number of different programming languages use the model of actors or its variants. Among them:
Libraries and table structures with actors have been developed to provide an actor-like programming style in languages that do not have built-in actors.
Comments
To leave a comment
Highly loaded projects. Theory of parallel computing. Supercomputers. Distributed systems
Terms: Highly loaded projects. Theory of parallel computing. Supercomputers. Distributed systems