Concurrency, BFS vs DFS (and a proposal)

Research and Development
14

My name is Eli Guenzburger I am researching with Prof. Cesar Sanchez at the IMDEA Software Institute.

When an operation is marked as Contextual, all of its resulting operations are executed before subsequent operations in the queue. In contrast to the dfs proposal (Point 4 in earlier post), contexts preserve the legacy bfs calling pattern of existing contracts on the blockchain. In this way, if I have an existing contract that I verified as safe assuming a bfs calling pattern, I do not have to worry that anything will break as a result of another contract calling my contract as dfs.

We will mark a Contextual Function (CF) as Contextual.
By default, a function is a Non-Contextual Function (NCF).
An operation that triggers a CF is a Contextual Operation (CO)
And one that triggers a NCF is a Non-Contextual Operation (NCO)

BFS (Status quo)

//exec function takes an operation, executes it and returns the list of generated operations. 
exec : operation -> operation list 

API: BFS([s])

BFS(Queue Q):
While (Q is not empty)
  op = Q.dequeue()
  Q.enqueue(exec(op))

BFS + DFS proposal

API: BFS([s])

BFS(Queue Q):
While (Q is not empty)
  op = Q.dequeue()
  if op is NCO
     Q.enqueue(exec(op))
  else (* op is DFS *)
     DFS([op])

DFS(Stack S):
While (S is not empty)
  op = S.pop()
  S.push(exec(op))

BFS + Context proposal

API: BFS([s])

BFS(Queue Q):
While (Q is not empty)
  op = Q.dequeue()
  if op is NCO
     Q.enqueue(exec(op))
  else (* op is CO *)
     Q'= new Queue()
     BFS(Q'.enqueue(exec(op)))

BFS vs BFS + DFS vs BFS + Context Examples

  1. The first table below describes a set of operations, and the operations they generate respectively. The three tables below it describe the different order of operations that result when operation A is executed using 3 different scheduler algorithms (while marking operation B2 as DFS or Contextual in tables 3 and 4 respectively).
Operation Emissions
A B1 B2
B1 C1 C2
B2 C3 C4
C1 D1
C2 D2
C3 D3
C4 D4
D1
D2
D3
D4
  1. Current Order of Operations (Pure BFS)

Order: A, B1, B2, C1, C2, C3, C4, D1, D2, D3, D4

Executing Queue Q (Post ex)
A B1 B2
B1 B2 C1 C2
B2 C1 C2 C3 C4
C1 C2 C3 C4 D1
C2 C3 C4 D1 D2
C3 C4 D1 D2 D3
C4 D1 D2 D3 D4
D1 D2 D3 D4
D2 D3 D4
D3 D4
D4
  1. B2 labelled Contextual Operation

Order: A, B1, B2, C3, C4, D3, D4, C1, C2, D1, D2

Executing Queue Q (Post ex) Queue Q’ (Post ex)
A B1 B2
B1 B2 C1 C2
B2 C1 C2 C3 C4
C3 C1 C2 C4 D3
C4 C1 C2 D3 D4
D3 C1 C2 D4
D4 C1 C2
C1 C2 D1
C2 D1 D2
D1 D2
D2
  1. B2 Labelled DFS

Order: A, B1, B2, C3, D3, C4, D4, C1, C2, D1, D2

Executing Queue Q (Post ex) Stack S (Post ex)
A B1 B2
B1 B2 C1 C2
B2 C1 C2 C3 C4
C3 C1 C2 D3 C4
D3 C1 C2 C4
C4 C1 C2 D4
D4 C1 C2
C1 C2 D1
C2 D1 D2
D1 D2
D2
4 Likes