Learn

# Rholang vs. the dining philosophers

Rholang is frequently touted as a fully concurrent programming language. It will be blazing fast because it executes things sequentially only when absolutely necessary. It allows us to avoid resource starvations and thread deadlock. And it isn’t even clunky or hard to use, because all of this is built right into its concurrent computational model.
That’s definitely the sexiest programming language I’ve ever heard of, but what does all of that actually mean? Let’s investigate one of rholang’s real-world benefits, inherent concurrency, in the context of a classic computer science problem known as “The Dining Philosophers”.

## The problem setting

Imagine two philosophers sitting across from each other on the east and west sides of a table. They each have a bowl of pasta, but there is only one set of silverware. The knife is on the north, and the fork on the south. Everyone knows it takes both pieces of silverware to eat pasta, so no philosopher can eat until they have both utensils simultaneously. The classic problem is to prescribe a set of actions, so that the philosophers can happily share the silverware and successfully eat their dinner.

## Solutions

A natural first approach is for each philosopher to follow this algorithm.

``````wait for utensil on left
wait for utensil on right
eat for one minute
return both utensils
think for one minute
``````

When working in a fully sequential environment, this program works reasonably well. The first philosopher will follow it, eating for one minute, then the second, and each will take turns eating equitably.
In reality, each philosopher is an independent actor and they can act simultaneously. This reality can be modeled as soon as any parallelism is allowed. The new situation looks something like:

``````each philosopher does:
grab utensil on left
grab utensil on right
eat for one minute
return both utensils
think for one minute
``````

As soon as we allow two philosophers to act simultaneously, we run into problems. For example, each philosopher could grab the left utensil at the same time and be stuck waiting forever for the right utensil to become available. In this deadlock, the philosophers are experiencing a quite-literal starvation issue ;-).
A better algorithm that will allow the philosophers to have dinner even when they can act simultaneously would be:

``````each philosopher does:
wait until both utensils are simultaneously available
grab both utensils
eat for one minute
return both utensils
think for one minute
``````

## Examples in Python

The original algorithm is fairly easy to code in a sequential programming language like python. It is the most natural solution to express in such a language.

``````from threading import Thread, Lock
# Set the table
fork = Lock()
knife = Lock()
# Philosopher 1's plan
def plan1():
fork.acquire(True)
knife.acquire(True)
print("Philosopher 1 is full.")
fork.release()
knife.release()
# Likewise for philosopher 2
def plan2():
knife.acquire(True)
fork.acquire(True)
print("Philosopher 1 is full.")
knife.release()
fork.release()
# Hard to give them a fair start in a sequential language
phil1.start()
phil2.start()``````

Although we did have to import threading separately, this code is not too hard to understand. Especially for all the time we spend bashing sequential languages. But this code does haves the critical flaw discussed above. If it runs on two separate threads, philosopher one will grab the fork, philosopher two will grab the knife, and both will starve. The following python code implements the better second algorithm.

``````from threading import Thread, Lock
# Set the table
fork = Lock()
knife = Lock()
# Philosopher 1's plan
def plan1():
while True:
if fork.acquire(False):
if knife.acquire(False):
print("Philosopher 1 is full.")
knife.release()
fork.release()
# Likewise for philosopher 2
def plan2():
while True:
if knife.acquire(False):
if fork.acquire(False):
print("Philosopher 1 is full.")
fork.release()
knife.release()
# Hard to give them a fair start in a sequential language
phil1.start()
phil2.start()``````

This code does fix the deadlock problem, but it is visibly more complex, more deeply nested, and even requires the programmer to be consciously aware of resource locks. In python, like any sequential language, you have to trade multi-threading vs complexity. Consequently, programmers learn to program the thread-unsafe way first. Indeed in the sequential programming world, multi-threading is a skill often left to a senior developer.

## Examples in Rholang

These rholang examples were originally written by Mike Stay and adapted slightly for this post.
In this first example, the two philosophers follow the first algorithm and reach deadlock just like before. Notice that each philosopher’s plan is indented two levels deep because the philosopher is waiting for first one utensil, then the second.

``````new log(`rho:io:stdout`), north, south, knife, spoon in {
// Set the table
north!(*knife) |
south!(*spoon) |
// Philosopher 1's plan
for (@knf <- north) {
for (@spn <- south) {
log!("Philosopher 1 is full.") |
north!(knf) |
south!(spn)
}
} |
// Likewise for philosopher 2
for (@spn <- south) {
for (@knf <- north) {
log!("Philosopher 2 is full.") |
north!(knf) |
south!(spn)
}
}
}``````

The second version is nearly identical to the first, but the `for` comprehensions that wait for the utensils have been combined together into one using the `;` join operator. Now each philosopher will wait for both utensils to be simultaneously available before taking either. To learn more about the join operator in rholang, check out the lesson in my tutorial.

``````new log(`rho:io:stdout`), north, south, knife, spoon in {
// Set the table
north!(*knife) |
south!(*spoon) |
// Philosopher 1's plan
for (@knf <- north; @spn <- south) {
log!("Philosopher 1 is full.") |
north!(knf) |
south!(spn)
} |
// Likewise for philosopher 2
for (@spn <- south; @knf <- north) {
log!("Philosopher 2 is full.") |
north!(knf) |
south!(spn)
}
}``````

Unlike the python examples, in rholang the code actually got simpler when we implemented the concurrency-friendly version, which lightens the load on the programmer’s mind. Because rholang uses a fully-concurrent computational model, the most natural way to express a program is the “right” way. While the sequential programmer has to navigate deep nesting and explicit locks, such details are hidden away under the hood in rholang, leaving the programmer’s mind unburdened.

## Reflections

We’ve shown that rholang syntax naturally avoids complete deadlock so that all philosophers get to eat their dinner. Rholang programmers don’t suffer additional complexity in order to capitalize on concurrent programming. Rather, the most natural way to express a program is the thread-safe way. Only when intentionally writing sequential code can deadlock be achieved in rholang.
I’ve often wondered how this might play out if the philosophers were competing for their share of a single communal dish. Now that I’m a rholang programmer, I can reallocate the brain-power that used to worry about multi-threading and deadlock to pondering such problems.