• Overview & Motivation
• CSP vs Actor Model
• Core Building Blocks in CSP
  • Code examples in PyCSP
• Travelling Salesman Problem in PyCSP

• A paradigm for expressing concurrency
  • Based on message-passing
• First described in a 1978 paper by Tony Hoare
  • (Actor model first described in 1973)
• Key concepts
  • Sequential processes
  • Synchronous communication through channels
  • Multiplexing of channels with alternation

• Shared Memory
  • Threads
  • Locks
  • Mutexes

• Message Passing (CSP and Actor Model)
  • Processes
  • Messages
  • No shared data

Program crash in critical region corrupts memory
• • Difficult to reason about
  • Hard to recover from failure

Where is shared memory physically located?
• • Even harder to recover from failure

• Overview & Motivation
• CSP vs Actor Model
• Core Building Blocks in CSP
  • Code examples in PyCSP
• Travelling Salesman Problem in PyCSP

• Overview & Motivation
• CSP vs Actor Model
• Core Building Blocks in CSP
  • Code examples in PyCSP
• Travelling Salesman Problem in PyCSP

• Python library that implements core CSP primitives
• Development started in 2006. Still under active development
• Transparent distributed communication using standard python modules

@process
def Process1():
    time.sleep(1)  # Sleep 1 second
    print 'process1 exiting'

@process
def Process2():
    time.sleep(2)  # Sleep 2 seconds
    print 'process2 exiting'

Parallel(Process1(), Process2())  # Blocks
print 'program terminating'

process1 exiting
process2 exiting
program exiting

@process
def Worker(input_chan):
    (output_chan, work_func) = input_chan()
    result = work_func()
    output_chan(result)

def work():
    return 2 * 2

input_chan = Channel()
Spawn(Worker(input_chan.reader()))

result_chan = Channel()
msg = (result_chan.writer(), work)  # Careful, 'work' is shared reference

input_chan.writer()(msg)
result = result_chan.reader()()  # Get result

@process
def Process1(input_chan, output_chan):
    input_guard = InputGuard(input_chan)
    output_guard = OutputGuard(output_chan, msg='hello from process1')
    (chan, msg) = AltSelect(input_guard, output_guard)
    if chan == input_chan:
        print 'input read: ', msg
    elif chan == output_chan:
        print 'output written'

input, output = Channel(), Channel()
Spawn(Process1(input.reader(), output.writer()))

if random.choice([True, False]):
    input.writer()('hello process1')
else:
    output.reader()()

@process
def Process1(input_chan):
    guards = [InputGuard(input_chan), SkipGuard()]
    (chan, msg) = PriSelect(guards)  # Always perform skip guard last
    if chan == input_chan:
        print 'input read: ', msg
    else:
        print 'no input'

input = Channel()
Spawn(Process1(input.reader()))

guard = OutputGuard(input.writer(), msg='hello process1')
PriSelect(guard, TimeoutGuard(seconds=1))

• Overview & Motivation
• CSP vs Actor Model
• Core Building Blocks in CSP
  • Code examples in PyCSP
• Travelling Salesman Problem in PyCSP

• Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?
• 
  Can be modeled as an complete, undirected weighted graph
• 
  Complexity for brute force approach: O(n!)

• Discard sub-routes that already are longer than current shortest route