proving ESL: The Actor Model of Concurrency

Abstract

Actor Model of computation is a mathematical theory of computations that exist to solve the problem of concurrency in distributed systems. The actor serves as a process and communicates with other actors via asynchronous message passing. The actor models can be incorporated into any programing language either sequential or functional using CPS transform. Erlang is the most popular actor model and it has a separate toolkit(AKKA) for the actor model. Overtime, industry’s and technologies such as Twitter, Facebook and Microsoft have leverage on the actor model. Trending technologies like IOT and cloud computing have included the actor model to their technologies. With all these growths, the actor model has its own downside such as lack of inheritance and polymorphism. ESL (actor-based language) is in a growth stage to solve these challenges. System development methodology will be used to advance the ESL technology. 

 

1)   Introduction: Actor Model

“One actor is no actor”. The actor model comes as a system where everything is an actor. The actors communicate by sending an asynchronous message to each other. 

The actor model is a mathematical theory of computation that treats “Actors” as the universal primitives of concurrent digital computation (Hewitt,2010). The actor model was invented by Carl Hewitt in 1973.

Dissimilar to preceding models of computation, Actor model was motivated by physical law. Programming languages like Lisp, Smalltalk, ideas for Petri Nets, capability-based systems and packet switching also motivated the invention of the model.

The actor model had been used as a tool to aid the understanding of concurrency and conceptual implications of concurrent systems.  

The emergence of massive concurrency through client-cloud computing and many-core computer architectures has galvanized interest in the Actor model (Hewitt, 2009).

Before the invention of the actor model, Threads were used for concurrency. Threads faced challenges such as lost update; where different process tries to change the value of a variable at the same time and the use of a lock to solve this problem also created another problem called deadlock; happens when two process tries to obtain two locks at the same time. An algorithm representation is shown below.

Lost Update Process 1 Process 2 a = acc.get() a = a + 100 b = acc.get() b = b + 50 acc.set(b) acc.set(a)

Deadlock Process 1 Process 2 lock(A) lock(B) lock(B) lock(A)

The actor model provides a solution to the above challenges.

2) The Actor model

2.1) Fundamental concept

The actor model is a light-weight entity that has a state, thread of control, mailbox and a supervisor strategy. It is inherently concurrent.

 

2.1.1) The actor model of computation involves

• Autonomous concurrent actor: They are inherently concurrent. Programming languages like Java that uses threads for currency, tends to separate the model of concurrency with the model of the object (Agha, 2013). Actor model unifies these two notion.
• No shared state: To avoid the issue of a data race, race condition and sharing of a variable, the actor model does not implement the sharing of state.
• Asynchronous message passing: primitively, actors communicate asynchronously. They exchange and share information and it aids in synchronization.

2.1.2) Standard actor semantics

• Encapsulation:  The state of the actor model is isolated. The actor is not directly exposed to the environment. Actors do not modify the state of another actor directly. This can only be done indirectly through message passing (Waldron and Nash, 2016)
• Fairness: If an actor sends a message, and the actor receiving the message is not permanently disabled then eventually the message will be received (Agha, 2013).
• Location Transparency: You don’t have to know which memory is processing a certain command. The systems decide which commands needs to be executed by a certain core.
• Mobility: Enhancement of Location transparency.  Actors can move around and the underlying system can take care of where actors are.

2.1.3) Actor anatomy

As shown in the figure below, an actor consists of a mailbox where messages are stored/queue. A thread of control that gets messages from the mailbox for processing. And a state that changes when processing a message.

Actor = Encapsulated state + behaviour + thread of control + mailbox

2.1.4) Messaging

Figure 1 Actor anatomy [1]

Actors can exchange messages to any actor known to them. These actors will only know about another actor if it created it or the actor was sent to it as a message. A message may contain basic data items, collections of data items, actors and function (Clark, n.d.).

Figure 2 Actor model of computation [2]

As shown illustrated in the figure above, actors do not have a shared state. They communicate via asynchronous message passing. An actor sends a message to another actor and continues without being blocked. The receiving actor stores the message sent to it in its mailbox. From which he processes messages one at a time in a single atomic step. The single atomic step execution of a message in an actor enables the macro-step semantics which is crucial in reasoning about actor systems passing (Shali, 2010).

In response to a message that an actor receives, an actor can concurrently

• Send a finite number of messages to other actors.
• Create a finite number of new actors.
• Designate the behaviour to be used for the next message it receives.

There is no specific order to how the above actions are carried out and they could be carried out concurrently. In addition, two messages sent concurrently can arrive in either order (Hewitt, 2010).  

2.2) Technologies that implements Actor model

With the growing number of acceptance for the actor model in software development, programming languages and other technologies, actor model is being implemented in all technological sector. Programming Languages like Scala (Runs on the JVM platform) had implemented Actor as parts of its core language in the early days of actor invention. Scala has a separate toolkit dedicated for concurrency computation with more emphasis on the actor model. Erlang which initially started as a fault tolerance library for Prolog which subsequently became a programming language contains a library(AKKA) for the actor model. Other languages like SALSA, Kilim, Jetlang and JavAct also implemented the actor model in its language. Some of these languages break the rules of the actor semantics while trying to achieve some certain language objectives. 

Figure 3 Actor languages comparison [1]

The figure above shows different languages and the trade-offs they have while trying to implement the actor model. Actor Foundry(AF) a programming language developed at the University of Illinois is one of the actor languages that adhere to all the actor semantic.

Another actor based model language currently being developed at Aston University is ESL. ESL is an actor-based functional language that aims to provide abstractions over an application that requires a high degree of concurrency (Clark, n.d.). It is a statically typed language. ESL provides extensions over the standard Actor Model, including shared state and access to the underlying Java platform, for practical application development (Clark, n.d.).

2.3) Practical implementation of the actor model

The actor model has gained popularity and has been implemented in many systems around the globe. Some of its implementations are in

• Emergent behaviour: ESL actor-based language was used to simulate emergent behaviour in termite; system behaviour can be observed as a result of many simple individual behaviours even though each individual behaviour has no knowledge of the whole. The termite work in such a way that they walk around at random until they find a twig that is not in contact with other twigs. The termites pick the twig walk at random until they find another twig that is next to other twigs. The termites drop the twig and loop the process (Clark, n.d.). Each termite in this simulation is represented by an actor.

Figure 4 Termites emergent behaviour  [2]

• IoT: For building the all-interconnected Internet-of-things (IoT), one computational model stands out from the rest(Cheung,2017).  IoT involves a large number of managed devices each of which consists of changing internal state (Cheung, 2017). These devices work independently and sometimes needs to communicate with other devices. Such “minimalist” autonomously align well with the actor model. The lightweight of an actor model also makes it possible to scale without consuming much computing power. Another significant feature of the actor model is its loose-coupling in nature by means of non-blocking communications via message passing. These attributes make them suitable for building distributed computing systems(Cheung,2017).

The most significant aspect of the actor model is their inherent capability of maintaining their internal state in a virtual private thread isolated from the rest of the system. This makes actors superb for simulating IOT devices, each of which consists of its own state and control logic(Cheung, 2017).

Other implementation of actor model includes Molecular dynamics Charmm, Twitter, Image processing in Ms visual, Facebook chat system and a paper (Barat et al., 2017)that justifies how actor model could have been used to predict the effects of the demonization initiative in Indian.

Conclusion

The actor model is gradually gaining popularity. One question to ask is that if the actor model is so great why isn’t it trending while it had been invented more than four decades ago?

Just like any other system, the actor model has its own weakness. Important programming aspect such as inheritance and polymorphism is something that needs to be worked on.  The ability of an actor to create multiple actors which may lead to spaghetti code makes it difficult to understand and testing becomes cumbersome.

Despite all this, the field is growing rapidly and big tech practitioners such as Twitter Facebook and linked built their systems on actor model and they found it to be very robust.

Another breakthrough which I am studying is the ESL language. Its currently the only language that is built using the actor model. Every aspect of it. This will give others a very good perspective on the strength of the language. With ESL a programmer will have to write way too less code that they have to write using other languages. ESL is still in its growth stage and it needs more work for it to compete with other development environment but with its features and rapid growth, the feature seems to be promising for both actors and ESL.

References

[1] Agha, G. (2013). Gul Agha on The Actor Model: Foundations, Languages and Open Problems. [image] Available at: https://www.youtube.com/watch?v=LSjm9vkbFDg [Accessed 28 Dec. 2018].

[2] Clark, T. (n.d.). ESL Reference Guide [Accessed 17 Dec. 2018].

[3] Hewitt, C. (2010). Actor Model Of Computation. ArXiv. [online] Available at: http://arxiv.org/abs/1008.1459 [Accessed 31 Dec. 2018].

[4] En.wikipedia.org. (2018). Actor model. [online] Available at: https://en.wikipedia.org/w/index.php?title=Actor_model&oldid=867832845 [Accessed 23 Dec. 2018].

 [5] Il Song, S., Ho Kim, Y. and Soo Yoo, J. (2004). An enhanced concurrency control scheme for multidimensional index structures. IEEE Transactions on Knowledge and Data Engineering, 16(1), pp.97-111.

[6] Vermeersch, R. (2019). Concurrency in Erlang & Scala: The Actor Model · Ruben Vermeersch (rubenv). [online] Rocketeer.be. Available at: https://rocketeer.be/articles/concurrency-in-erlang-scala/ [Accessed 3 Jan. 2019].

 [7] Cheung, L. (2017). Why Akka and the actor model shine for IoT applications. [online] InfoWorld. Available at: https://www.infoworld.com/article/3209728/internet-of-things/why-akka-and-the-actor-model-shine-for-iot-applications.html [Accessed 3 Jan. 2019].

[8] Mackay, P. (n.d.). Why has the actor model not succeeded?. [online] Doc.ic.ac.uk. Available at: https://www.doc.ic.ac.uk/~nd/surprise_97/journal/vol2/pjm2/ [Accessed 30 Dec. 2018].

[9] Barat, S., Kulkarni, V., Clark, T. and Barn, B. (2017). AN ACTOR-MODEL BASED BOTTOM-UP SIMULATION – AN EXPERIMENT ON INDIAN DEMONETISATION INITIATIVE. Proceedings of the 2017 Winter Simulation Conference. [online] Available at: https://bit.ly/2VsVOe1 [Accessed 23 Dec. 2018].

[10] Waldron, W. and Nash, M. (2016). Applied Akka Patterns. [online] O’Reilly | Safari. Available at: https://www.oreilly.com/library/view/applied-akka-patterns/9781491934876/ch01.html [Accessed 13 Dec. 2018].

[11] Hewitt, C. (1993). The Actor Model. MIT.

[12] Garnock-Jones, T. (2016). [online] Seas.harvard.edu. Available at: https://www.seas.harvard.edu/courses/cs252/2016fa/12.pdf [Accessed 3 Jan. 2019].

[13] AGHA, G., MASON, I., SMITH, S. and TALCOTT, C. (1997). A foundation for actor computation. Journal of Functional Programming, 7(1), pp.1-72.

[14] Jaksa’s Blog. (2015). What’s Wrong with the Actor Model. [online] Available at: https://jaksa.wordpress.com/2015/10/13/whats-wrong-with-the-actor-model/ [Accessed 29 Dec. 2018].

[15] Chiusano, P. (2010). Actors are not a good concurrency model. [online] Pchiusano.blogspot.com. Available at: http://pchiusano.blogspot.com/2010/01/actors-are-not-good-concurrency-model.html [Accessed 3 Jan. 2019].