Concurrency and the Actor Model¶

1. Concurrency Fundamentals¶

1.1 Introduction to Concurrency¶

Concurrency refers to the execution of multiple tasks or processes simultaneously or interleaved in time. In programming, concurrency allows multiple threads of execution to run independently within the same or different memory spaces. Most programming languages assume sequential execution by default, where statements execute one after another in strict order. However, in concurrent systems, multiple execution flows can run in parallel, introducing complexities in timing, data consistency, and resource management.

1.2 Processes vs Threads¶

Processes: Isolated address spaces with separate memory. Each process has its own data structures and resources. Communication between processes requires Inter-Process Communication (IPC) mechanisms such as pipes, FIFOs, and shared memory.
Threads: Lightweight execution units within the same memory space. Multiple threads can access and modify shared data simultaneously, which introduces synchronization challenges.

1.3 Green Threads vs Native Threads¶

Green Threads: Scheduled and managed by the JVM internally. The JVM controls which thread executes and for how long.
Native Threads: Supported and scheduled by the operating system. Modern Java virtual machines use native threads, allowing the OS to distribute threads across multiple CPU cores for improved performance.

2. Traditional Concurrency Problems in Shared Memory Models¶

2.1 Thread Safety and Data Corruption¶

When multiple threads access shared data simultaneously, data corruption can occur if reads and writes are not properly synchronized. For example, if thread A is reading a variable while thread B is writing to it, thread A may read incomplete or partially updated data. This timing-dependent issue is difficult to test and reproduce.

2.2 Deadlock¶

Definition: A situation where two or more threads are blocked indefinitely, each waiting for a resource held by another thread. This typically happens in circular dependency scenarios.

2.2.1 Circular Locking Dependency Example¶

A classic example occurs when multiple threads attempt to lock multiple objects in different orders:

Thread 1 locks Object 1 and waits for Object 2
Thread 2 locks Object 2 and waits for Object 1
Both threads are now deadlocked, each holding one resource and waiting for the other

2.2.2 Money Transfer Deadlock Example¶

When transferring money between accounts using synchronized blocks on account objects:

public void transferMoney(Account fromAccount, Account toAccount, int amount) {
    synchronized (fromAccount) {
        synchronized (toAccount) {
            if (fromAccount.hasSufficientBalance(amount)) {
                fromAccount.debit(amount);
                toAccount.credit(amount);
            }
        }
    }
}

If Thread 1 calls transferMoney(account1, account2) and Thread 2 calls transferMoney(account2, account1), deadlock can occur:

Thread 1 locks account1 and is pre-empted before locking account2
Thread 2 locks account2 and tries to lock account1 (blocked)
Thread 1 resumes and tries to lock account2 (blocked)
Both threads are now deadlocked

2.2.3 Testing Deadlock Issues¶

Deadlock conditions are extremely difficult to test because they require specific timing characteristics. The pre-emption must occur at precisely the right moment between synchronized blocks. This may happen only rarely or under heavy load, making deadlock bugs difficult to identify during normal testing.

2.2.4 Solutions to Deadlock¶

Ordered Locking: Always lock objects in the same predetermined order (e.g., by account ID). This prevents circular dependencies because all threads follow the same locking sequence.

if (fromAccount.getId() < toAccount.getId()) {
    synchronized(fromAccount) {
        synchronized(toAccount) {
            // call transfer code
        }
    }
} else {
    synchronized(toAccount) {
        synchronized(fromAccount) {
            // call transfer code
        }
    }
}

2.3 Thread Starvation and Fairness Issues¶

Definition: When multiple threads wait on a monitor and the monitor is released, the Java runtime does not guarantee that the thread waiting longest will be awakened. Some threads may continuously be overlooked (starved) while others get execution time.

2.4 Double-Lock Checking Pattern¶

The double-lock checking pattern optimizes synchronized access by checking if synchronization is needed before acquiring the lock:

public class DbaseConnector {
    private static DbaseConnector instance = null;

    public static DbaseConnector getConnector() {
        if (instance == null) {
            synchronized (DbaseConnector.class) {
                if (instance == null) {
                    instance = new DbaseConnector();
                }
            }
        }
        return instance;
    }
}

This reduces synchronization overhead by checking the condition outside the synchronized block first.

2.5 Race Conditions¶

Definition: A bug that depends on specific timing characteristics of code execution. The behavior changes based on the relative timing of different execution threads. Race conditions are inherent to the shared memory concurrency model and are difficult to detect through conventional testing.

2.6 Summary of Shared Memory Model Issues¶

The traditional thread-shared model is inherently prone to:

Deadlocks
Unfairness and thread starvation
Data corruption issues
Race conditions
Complex synchronization logic that must be carefully designed

These problems are not accidental but are inherent in the shared memory model itself and require careful architectural decisions to avoid.

3. The Actor Model¶

3.1 Overview and Core Principles¶

The Actor model is a simplified approach to concurrency that eliminates the problems inherent in shared memory models. Instead of sharing data between threads, each actor maintains its own private state and independent thread of execution. Actors communicate exclusively through asynchronous message passing, making deadlock impossible.

3.2 Fundamental Characteristics of Actors¶

3.2.1 Independent State and Threading¶

Each actor has its own internal data/state which cannot be directly accessed by other actors
Each actor has its own dedicated working thread that processes incoming messages
Only the actor's own thread can read or write the actor's internal state
No data sharing means no need for synchronization locks

3.2.2 Message-Based Communication¶

Actors communicate by sending messages to other actors
An actor receives messages in an inbox (message queue)
Messages are processed sequentially as they arrive
Messages are immutable - they cannot be modified after sending

3.3 Actor Capabilities¶

Actors can perform the following operations:

Create other Actors - An actor can instantiate and spawn new actors as needed
Send messages - An actor can send messages to other actors (local or remote)
Receive and act on incoming messages - An actor's thread reads messages from its inbox and processes them

3.4 Actor Communication Patterns¶

3.4.1 Basic Message Exchange¶

When Actor A wants to communicate with Actor B:

Actor A sends a message to Actor B's inbox
The send operation returns immediately (non-blocking, asynchronous)
Actor A does not wait for a response
Actor B's thread eventually processes the message from its inbox
When appropriate, Actor B sends a reply message back to Actor A

3.4.2 Practical Example: Account Balance Request¶

Client Actor -> "Request Balance" -> Account Actor inbox
Account Actor processes message and sends reply:
Account Actor -> "Balance: $1000" -> Client Actor inbox

3.4.3 Example: Money Transfer Between Accounts¶

Client creates a unique transaction ID
Client Actor -> "TransferAmount(Account1, Account2, amount, transactionId)" -> Account1 Actor
Account1 Actor checks balance, debits the account, sends debit confirmation
Account1 Actor -> "AddAmount(Client, amount, transactionId)" -> Account2 Actor
Account2 Actor credits the account
Account2 Actor -> "ConfirmTransfer(transactionId)" -> Client Actor

The transaction ID (typically concatenation of ClientID, Account1 ID, Account2 ID, and timestamp) allows clients to verify transactions.

3.5 Message Handling in Actor Model¶

3.5.1 Asynchronous Communication¶

All messages are sent asynchronously (non-blocking)
Sending a message returns immediately; no waiting for response
This is fundamentally different from traditional synchronous method calls
Introduces callback-like behavior where responses arrive later

3.5.2 Message Ordering¶

Messages do not necessarily arrive in the order they were sent when using datagram-based protocols
The actor model does not guarantee message ordering over networks
Applications using the actor model must not assume ordered delivery
Messages may need to be resent if delivery is uncertain

3.5.3 Message Immutability¶

Messages must be immutable - their contents cannot be changed after creation. This ensures that multiple parties cannot corrupt shared message state.

3.6 Message Passing Approaches¶

3.6.1 Pass by Reference (Zero Copy)¶

Fastest approach: sends a pointer/reference to the message object
The receiving actor gets a reference to the same object in memory
Only viable when both actors are on the same machine
Requires that the message object be immutable to prevent unintended state changes
Problems arise when actors are on different physical systems (remote actors)

3.6.2 Pass by Value (Deep Copy)¶

Creates a complete copy of the message object and transfers the copy
Necessary when actors are on separate machines connected via network
The sending actor and receiving actor have independent copies
No shared state between sender and receiver
Can be slower, especially for large messages

3.6.3 Implementation Techniques¶

Cloning: Use Java's clone() method to create independent copies of message objects

Message myMess = new Message("Hello!");
myActor.sendMessage(myMess.clone());  // Send copy, not reference

Immutable Objects: Use objects with no setters (e.g., Java String class)
Linear Types (in languages that support them): Ensure only one reference exists to an object at a time. When one variable gets the object, the previous reference becomes invalid.

3.7 Key Benefits and Features of the Actor Model¶

3.7.1 Elimination of Deadlock¶

Since actors never share data and never lock resources, deadlock is impossible. Deadlock requires circular dependencies in resource allocation; the actor model prevents this by eliminating shared resources.

3.7.2 Fair Scheduling¶

Definition: A fair scheduler ensures that every non-blocked actor eventually gets execution time. An actor is non-blocked if:

It is currently processing a message, OR
It has messages waiting in its inbox

A fair scheduler guarantees:

No actor is starved of CPU time
All non-blocked actors will eventually execute
Makes it easier to reason about program behavior and performance

3.7.3 Location Transparency¶

Addressing is the same whether the sender and receiver are:

Local (on the same machine)
Remote (on different machines)

Developers need not know or care about the physical location of actors. The framework handles network communication transparently using:

Message brokers
Naming services (e.g., DNS for internet-based actors)
Object Request Brokers (CORBA)

3.7.4 Scalability¶

The actor model makes it easy to build massively scalable systems because:

Actors can be distributed across multiple machines
If more processing power is needed, additional hardware can be added
New actors can be deployed on new machines without changing application code
Processing load can be spread across a large number of physical systems

3.7.5 Redundancy and Reliability¶

Actors can be moved between machines for reliability purposes
If a machine fails, actors can be migrated to healthy machines
Supports automatic failover and recovery mechanisms

3.8 Actor Addressing and Delivery Guarantees¶

3.8.1 Message Delivery Assumptions¶

The actor model assumes:

All messages are eventually delivered to their destination
All delivered messages are eventually processed
These assumptions help prevent deadlock and starvation

3.8.2 Sources of Actor Addresses¶

An actor can obtain another actor's address through:

Receiving a message: When Actor A sends a message to Actor B, Actor B can see Actor A's address (return address) and reply to it
Actor creation: When an actor creates a new actor, it receives the created actor's address immediately
Configuration: Addresses can be provided at startup or through configuration files

3.8.3 Address Format and Transparency¶

Addresses typically use URL-based schemes for internet applications
Domain Name Systems (DNS) can be used to resolve actor addresses
Addresses work transparently whether actors are local or remote

3.9 Actor Mobility¶

3.9.1 Motivation for Mobility¶

Locality of Reference: Moving actors closer together (possibly to the same machine) reduces latency and bandwidth consumption
Load Balancing: Moving actors from heavily loaded machines to less loaded ones
Reliability: Moving actors from malfunctioning machines to healthy ones
Hardware Updates: Moving actors to accommodate hardware changes without service interruption
Mobile Environments: Moving actors to mobile devices as needed

3.9.2 Strong Mobility¶

Involves transferring both the actor code and its complete execution state
The actor can be moved while processing a message or while active
Full state transfer ensures no loss of processing context
More overhead but provides complete transparency

3.9.3 Weak Mobility¶

Involves transferring actor code and optional initialization state
Typically used for idle actors (empty message queue, not currently processing)
Less overhead than strong mobility
Suitable for moving inactive actors to less busy machines

3.9.4 Steps for Actor Migration¶

The actor framework must perform the following steps transparently:

Stop the actor from processing
Capture the actor's complete internal state
Create a new actor instance on the destination machine
Restore the saved state to the new actor instance
Delete the old actor from the source machine
Handle addressing - redirect future messages to the new location

All these steps should be transparent to application code.

3.10 Synchronization Constraints¶

Sometimes an actor needs to defer message processing due to resource constraints or service unavailability.

3.10.1 Constraint Implementation¶

If an actor cannot process a message (e.g., required service is offline), it can defer processing
The message is stored in a saved message queue
When the constraint is no longer active, the actor retrieves and processes saved messages
Example: A balance request when the database is offline

3.10.2 Disabling Message Processing¶

Using constraint annotations (e.g., in Scala/Akka):

@Disable(messageName = "put")
public Boolean disablePut(Integer x) {
    if (bufferReady) {
        return (tail == bufferSize);
    } else {
        return true;
    }
}

This prevents the actor from accepting certain messages when specified conditions are met.

4. Actor Frameworks and Languages¶

4.1 Actor Foundry (Java)¶

Actor Foundry is a Java API for implementing the actor model with the following features:

Safe messaging: Supports both pass-by-copy (safe) and pass-by-reference (efficient) messaging
Message ordering: Local synchronization constraints allow ordered message delivery when needed
Pattern matching: Multiple dispatch based on message types
Fair scheduling: Guarantees fair scheduling of non-blocked actors
Mobility support: Full support for actor migration
Location independence: Transparent local/remote communication

4.2 Erlang¶

Erlang is a functional programming language developed by Ericsson for telecommunications systems.

4.2.1 Characteristics¶

Functional language: Based on functional programming principles, not object-oriented
Built-in concurrency: The actor model is integral to the language
High performance: Designed for massive concurrency in telecom applications
Hot swap: Modules can be changed without recompiling or stopping the system
Location independence: Actors communicate transparently across machines

4.2.2 Variable Binding (Single Assignment)¶

In Erlang, variables work differently than in imperative languages:

A = 5      % A is now bound to 5
B = A      % B is now bound to 5
A = 10     % ERROR: A is already bound to 5, cannot rebind
A = 5      % OK: Just verifies that A equals 5

Once a variable is bound to a value, it cannot be changed. This ensures consistency and prevents certain classes of bugs.

4.2.3 Referential Transparency¶

Every time a function is called with the same arguments, it returns the same result. This property:

Eliminates side effects
Makes code behavior predictable
Is valuable for systems like routers where consistent behavior is critical
Simplifies compiler optimization and code verification

4.2.4 Tail Recursion¶

Erlang supports tail recursion that doesn't grow the call stack:

function(State) ->
    NewState = compute(State),
    function(NewState).  % Tail recursive call, no stack growth

The tail recursive call doesn't push a stack frame; instead, it replaces the current frame. This allows indefinite recursion without stack overflow, effectively creating a loop mechanism.

4.3 Scala¶

Scala is a hybrid functional/object-oriented language integrated with Java.

4.3.1 Characteristics¶

Functional + OOP: Combines functional and object-oriented paradigms
Java Integration: Fully interoperable with Java JDK libraries
Built-in Actor Support: The actor model is available through Scala's actor library
Highly Scalable: Designed for building large-scale concurrent systems
Dynamic Typing: Type inference reduces need for explicit type declarations
Used by Twitter: The actor model implementation in Scala powers Twitter's platform

4.3.2 Scala Syntax Basics¶

object HelloWorld {
    def main(args: Array[String]): Unit = {
        var hello = "Hello World..."
        val myValue = "Freddy"
        println(hello + myValue)
    }
}

Type comes after the variable name (unlike Java)
var for mutable variables, val for immutable values
Type inference is automatic when not specified
Unit is equivalent to void in Java

4.3.3 Scala Class Definition¶

class Person(val surname: String, val forename: String) {
    var weight = 0f

    def fn: String = forename + surname

    def setWeight(w: Float): Unit = {
        this.weight = w
    }

    def getWeight(metric: Boolean): Double = {
        if (metric) 
            weight
        else 
            weight * 2.2
    }
}

4.3.4 Actor Implementation in Scala¶

import scala.actors.Actor
import scala.actors.Actor._

class EmailClient(val username: String) extends Actor {
    def act() {
        while (true) {
            receive {
                case incoming: EmailMessage =>
                    println("Got message for " + username + 
                    "message is " + incoming.message)
            }
        }
    }
}

4.3.5 Scala Message Sending¶

// The ! operator sends a message asynchronously
userclient ! incoming

// Example:
val client = new EmailClient("Seb")
val mb = new Mailbox(client)
mb.start()
client.start()
mb ! new EmailMessage("Hello how are you?")

The ! operator sends a message to an actor without blocking.

5. Concurrency Solutions: Dining Philosophers Problem¶

5.1 Problem Definition¶

The Dining Philosophers problem is a classic concurrency problem used to analyze solutions to resource contention. Five philosophers sit around a table with one chopstick between each pair. To eat, a philosopher needs two chopsticks (left and right). The challenge is to design an algorithm that allows philosophers to eat without deadlock or starvation.

Key principles:

Philosophers alternate between thinking and eating
Limited resources (chopsticks)
Multiple competing threads (philosophers)
Real-world analogy: threads competing for shared resources like data structures

5.2 Naive Solution: Potential Deadlock¶

Each philosopher picks up the left chopstick, then tries to pick up the right chopstick:

1. Pick up left chopstick
2. Pick up right chopstick
3. Eat
4. Put down right chopstick
5. Put down left chopstick

Problem: If all philosophers pick up their left chopstick simultaneously, all are blocked waiting for their right chopstick, resulting in deadlock.

5.3 Solution 1: Table Lock with Dijkstra Signaling¶

Acquire a lock on the entire table
Check if both chopsticks are available
If available: pick up both chopsticks and proceed
If unavailable: release the lock and wait for a signal
When a philosopher finishes eating, they signal waiting philosophers

Characteristics:

Prevents deadlock through global synchronization
Allows starvation of waiting philosophers
Relatively inefficient due to global locking

5.4 Solution 2: Asymmetric Approach (No Locking)¶

Philosophers check availability and retry on failure:

1. Pick up left chopstick
2. Check if right chopstick is available
3. If yes: pick it up and eat
4. If no: put down left chopstick and go back to thinking
5. After random thinking time, retry

Characteristics:

No deadlock possible (no circular waiting)
Uses exponential backoff similar to media access protocols
Allows other philosophers to proceed if a chopstick is unavailable
Some inefficiency due to repeated attempts

5.5 Solution 3: Global Ordering (Ordered Locking)¶

Assign a total order to all chopsticks and always acquire them in order:

1. Identify the lowest-numbered chopstick among your two
2. Always pick up the lowest number first
3. Then pick up the higher number
4. All philosophers follow this ordering

Characteristics:

Completely prevents deadlock
Deadlock-free guarantee: if two philosophers contend for the same chopstick, one will proceed
Most efficient solution
Assumes resources have a natural ordering (not always possible)

5.6 Comparison of Solutions¶

Solution	Deadlock	Starvation	Efficiency	Complexity
Naive	Yes	Possible	Low	Low
Table Lock	No	Possible	Medium	Medium
Asymmetric	No	Possible	Low	Medium
Ordered Lock	No	No	High	Medium

6. Futures and Concurrent Computation¶

6.1 Overview of Futures¶

Definition: A future is a placeholder for a value that will be computed in the future. Rather than blocking while waiting for a slow operation to complete, a future allows the current thread to continue executing other tasks while computation happens concurrently.

6.2 Motivation: Sequential vs Concurrent Processing¶

Consider a workflow:

1. Download data from URL1 (2 seconds)
2. Encrypt the data (1 second)
3. Download template from URL2 (2 milliseconds)
4. Upload encrypted data to URL3 (500 milliseconds)

6.2.1 Sequential Execution Problem¶

If executed sequentially:

Total time = 2s + 1s + 0.002s + 0.5s = 3.502 seconds
While downloading from URL1, CPU sits idle
While uploading, CPU sits idle
Inefficient use of processing power

6.2.2 Concurrent Execution with Futures¶

Start URL1 download in one thread
While URL1 is downloading, start URL2 download
While both downloads proceed, start encryption on any completed data
While encryption proceeds, start upload
Total time ≈ 2.5 seconds (limited by slowest operation)

6.3 Java Future Implementation¶

public abstract class Future<V> extends Thread {
    private V value;

    public Future() {
        this.value = null;
    }

    public abstract V calculate();

    public void run() {
        value = calculate();  // Long-running computation
    }

    public V resolve() {
        // Wait for computation to complete
        // This thread blocks until value is available
        try {
            this.join();  // Wait for thread to complete
        } catch (InterruptedException e) {}
        return value;
    }
}

6.4 Usage Examples¶

6.4.1 Simple String Future¶

class StringFuture extends Future<String> {
    public String calculate() {
        return "Hello World";
    }
}

// Usage
StringFuture future = new StringFuture();
future.start();  // Start computation in background
String result = future.resolve();  // Wait and get result

6.4.2 URL Download Future¶

class URLDownloadFuture extends Future<String> {
    private String url;

    public URLDownloadFuture(String url) {
        this.url = url;
    }

    public String calculate() {
        // Download data from URL
        // This may take several seconds
        return downloadFromURL(url);
    }
}

// Usage
URLDownloadFuture future1 = new URLDownloadFuture("http://example.com/data1");
URLDownloadFuture future2 = new URLDownloadFuture("http://example.com/data2");

future1.start();  // Start first download
future2.start();  // Start second download immediately

String data1 = future1.resolve();  // Wait for first download
String data2 = future2.resolve();  // Wait for second download

6.5 Benefits of Futures¶

Parallel Execution: Multiple slow operations can run concurrently
Better CPU Utilization: CPU doesn't sit idle waiting for I/O
Improved Responsiveness: Application can continue processing while waiting for results
Simplified Threading: Encapsulates threading logic in reusable future class

6.6 Key Characteristics¶

Futures are created and started in the background
The calling thread can continue with other work
When the result is needed, resolve() blocks until computation completes
Multiple futures can run in parallel if system has multiple processors/cores

7. Comparison: Traditional Threading vs Actor Model¶

7.1 Shared Memory Model (Traditional Threading)¶

Data Access:

All threads share common memory space
Direct access to shared data structures
Requires synchronization (locks, monitors)

Communication:

Implicit through shared variable modification
Synchronous method calls with direct return values

Concurrency Issues:

Deadlock possible through circular lock dependencies
Race conditions from timing-dependent behavior
Thread starvation from unfair scheduling
Complex synchronization logic required

7.2 Actor Model¶

Data Access:

Each actor has isolated state
No direct data sharing
No synchronization needed

Communication:

Explicit message passing
Asynchronous, non-blocking sends

Concurrency Advantages:

Deadlock impossible (no shared resources)
No race conditions on actor state
Fair scheduling eliminates starvation
Simple, predictable behavior

8. Real-World Applications¶

8.1 Twitter¶

Twitter's platform is implemented using Scala actors. The actor model allows Twitter to:

Handle millions of concurrent users
Process high-volume message streams
Scale horizontally by distributing actors across servers
Maintain reliability through actor migration and failover

8.2 Ericsson Telecom Systems¶

Erlang (developed by Ericsson) is used extensively for:

Mobile network routing
Call processing
Real-time telecommunications
Systems requiring extreme reliability and uptime

8.3 Financial Systems¶

The actor model is increasingly used in:

High-frequency trading systems
Distributed financial transactions
Systems requiring guaranteed message delivery
Scalable data processing pipelines

9. Conclusion¶

The actor model represents a fundamental shift in how we approach concurrency in software systems. By eliminating shared mutable state and using explicit message passing, the actor model makes it possible to:

Build systems without deadlock
Scale to massive numbers of concurrent tasks
Move computation transparently across networks
Write correct concurrent code more easily

While traditional thread-based concurrency will continue to have a role, the actor model is increasingly recognized as the preferred approach for building highly concurrent, scalable, and reliable distributed systems.

Quick Reference: Key Definitions¶

Term	Definition	Key Point for Exams
Deadlock	Two or more threads blocked forever, each waiting for a resource held by another	Requires circular dependency of locks
Race Condition	Bug where behavior depends on timing of thread execution	Hard to test; occurs under load
Thread Starvation	Thread continuously overlooked for execution time	Violates fairness in scheduling
Fair Scheduling	All non-blocked actors eventually get execution time	Prevents starvation in actor model
Location Transparency	Same addressing whether actors local or remote	Key advantage for distributed systems
Message Immutability	Messages cannot be modified after creation	Prevents shared state corruption
Actor Mobility	Ability to move actors between machines	Enables load balancing and failover
Future	Placeholder for value computed in future	Enables parallel concurrent operations