## Model Assumptions.

• Asynchronous:

Messages can be arbitrarily delayed; no synchronized clocks.

• Crash Failures:

No failure detection, but no arbitrary and malicious behavior either.

## Consensus Protocol $$P$$

### where each process is made of

• Unbounded storage.
• One bit input register $$x_p$$.
• One bit output register $$y_p$$ (write-once).
• Transition Functions.

### A consensus protocol $$P$$ is partially correct if

1. $$P$$ never decides on two different decision values at the same time.
2. both decision values are possible under $$P$$.

## Example: Synod

### Asynchronous System of $$N = (f + 1) + (2f + 1)$$ processes.

• $$f+1$$ leaders. (both proposers and learners).
• $$2f+1$$ acceptors.

• ballot_num
• wait_for
• proposal

• ballot_num
• accepted

### Input output registers

1. $$x_p$$ is the leader's proposal.
2. $$y_p$$ is the leader's decision on the proposal.
• For acceptors:
1. $$x_p$$ is ignored.
2. $$y_p$$ is never decided.

## Example: Synod

• T1: on start, do send($$\alpha$$, (p1a, self, b)) message to all acceptors for a p1b (promise).
• T2: On receiving a (p1b, $$\alpha$$, b', pval), if b==b', remove $$\alpha$$ from the wait list of acceptors, and update the proposal to pval if it is set. If more than half of the acceptors have responded, do a send($$\alpha$$, (p2a, proposal, self, b)). Otherwise, update the ballot number b and do a send ($$\alpha$$, (p1a, self, b)).
• T3: On receiving a (p2b, $$\alpha$$, b'), if b==b', remove $$\alpha$$ from the wait list of acceptors. If more than half of the acceptors have responded, commit to the proposed value. Otherwise, update the ballot number b and do a send($$\alpha$$, (p1a, self, b)).

## Example: Synod

### Transition functions: Acceptors

• T1: On receiving a (p1a, $$\lambda$$, b), if b > ballot_num, update the ballot number and reply with a send($$\lambda$$, (p1b, self, ballot_num, pval)).
• T2: On receiving a (p2a, proposal $$\lambda$$, b), if b==ballot_num, accept the proposal and do a send($$\lambda$$, (p2b, self, ballot_num)).

## The Message Buffer.

### All the messages that are in flight.

• send(p, m) adds a message to the buffer.
• receive(p) removes a message from the buffer and deliver it to $$p$$. The message can be $$\emptyset$$. If called infinite amount of time, all messages will be delivered.
 $$A_1$$ $$\emptyset$$ $$A_2$$ (p1a, $$L_1$$, 0) (p1a, $$L_2$$, 0) $$A_3$$ (p1a, $$L_2$$, 0) $$L_1$$ (p1b, $$A_1$$, 0, null) $$L_2$$ $$\emptyset$$

## Configuration and Step

### Step: one process $$p$$ receives a message $$m$$, makes a transition, and sends some messages.

 $$A_1$$ $$\emptyset$$ $$A_2$$ (p1a, $$L_1$$, 0) (p1a, $$L_2$$, 0) $$A_3$$ (p1a, $$L_2$$, 0) $$L_1$$ (p1b, $$A_1$$, 0, null) $$L_2$$ $$\emptyset$$

## Configuration and Step

### Accessible configuration: a configuration is accessible if there is a run that arrives at it.

 $$A_1$$ (p2a, 0, $$L_1$$, 0) $$A_2$$ (p1a, $$L_1$$, 0) (p1a, $$L_2$$, 0) $$A_3$$ (p1a, $$L_2$$, 0) $$L_1$$ $$\emptyset$$ $$L_2$$ $$\emptyset$$

## Run

• All messages send to nonfaulty processes are eventually received.
• At most one process is faulty.
• Nonfaulty means the process takes infinite number of steps.

## Partially correct

1. No accessible configuration has more than one decision value, $$y_p$$. In Synod, this means that leaders decision register $$y_p$$ never disagree.
2. For each possible $$v \in \{0, 1\}$$, some accessible configuration decides on $$v$$. In Synod, this means either decisions are possible.

## Valence

• 0-valent: A configuration is 0-valent if there is a reachable configuration that has the decision value 0.
• 1-valent: A configuration is 1-valent if there is a reachable configuration that has the decision value 1.
• univalent: either 0-valent or 1-valent.
• bivalent: both 0-valent and 1-valent.

## Lemma 2

### Observation: When the initial configurations are ordered by grey code, neighboring configurations share valent values.

$$x_1$$ $$x_2$$ $$x_3$$ $$v$$
0 0 0 0
0 0 1 0
0 1 1 0
0 1 0 0
1 1 0 0
1 1 1 0
1 0 1 0
1 0 0 0

## Lemma 2 Example: Synod

### Synod have bivalent initial configurations, although it is not even close to "every admissible run is deciding".

$$x_1$$ $$x_2$$ $$v$$
0 0 0
0 1 0 & 1
1 1 1
1 0 0 & 1

## Lemma 3

• Let $$C$$ be a bivalent configuration of $$P$$,
• and let $$e=(p, m)$$ be an event that is applicable to $$C$$.
• Let $$\mathcal{C}$$ be the set of configurations reachable from $$C$$ without applying $$e$$,
• and let $$\mathcal{D} = e(\mathcal{C}) = \{e(E) | E \in \mathcal{C} \text{ and } e \text{ is applicable to } E\}$$.

## Remarks

### More than $$1$$ bit of output.

Just find one bit for which both values can be reached (partial correctness).

## Thanks

• Daniel Amir for the feedback.
• Julia Len for the reference slides.

/