Communication and Consensus Protocols in Synchronous and Asynchronous Networks

Permissioned setting

Known fixed set of nodes N={1,...,n}

Pairwise authenticated network

Receiver knows the true sender identity

Message sender s

Node sending a message

Message recipient r

Intended receiver of message

Message contents m

Payload or data being sent

Message time t

Timestamp only used when global time exists

Sync message format

(s,r,m,t)

Async message format

(s,r,m)

Global notion of time

All nodes know the current round

Round-based model

Time advances in discrete rounds

Maximum message delay Δ

Known upper bound on delivery time

Δ=1 assumption

Used without loss of generality for simplicity

End-of-round send

Messages produced at round end

Beginning-of-round receive

Messages delivered at start of round

Sync example delivery

Sent at round 7 arrives at start of round 8

Protocol Π

Decision rule describing node actions

Sync protocol inputs

Round number + message history + private info

Private info examples

Private values transactions or variables

Asynchronous setting

No global time and unbounded delays

Async delivery guarantee

Messages eventually delivered

Message pool M

Set of pending messages awaiting delivery

Dummy message (⊥

i,⊥),Starts local protocol execution

Main message loop

Repeatedly choose and deliver a message from M

Async execution

Defined by delivery order choices

Node reaction in async

Can add finite new messages to pool

Async constraint

Only eventual delivery is guaranteed

Async ordering

No guaranteed delivery order

Self messages

Nodes may send messages to themselves

Self message limitation

Does not create meaningful time

Event-based protocol

Actions triggered by message arrival

Async protocol inputs

Message history + private info

Partial synchrony

Eventually synchronous after unknown delay

Shared global clock

All nodes know current round

Clock skew variant

Equivalent model with bounded clock drift

GST definition

Global Stabilization Time chosen by adversary

Before GST

Messages may be arbitrarily delayed

After GST

Messages delivered within known Δ

Unknown GST

Nodes do not know when stability begins

Partial sync delivery bound

Delivery ≤ max{t,GST}+Δ

Message adversary controls

GST duration and delivery ordering

Partial sync protocol

Round-based like synchronous protocols

Partial sync timeout use

Protocols may depend on known Δ

Cannot plan for GST

GST unknown so no fixed scheduling

Consensus settings

Problems solved using communication models

Byzantine Broadcast (BB)

Single designated sender broadcasts a value

BB designated sender

Node 1 is expected sender

BB initial value

b1* belongs to value set V

BB termination

All honest nodes eventually output a value

BB agreement

Honest nodes never output different values

BB validity

If sender honest output equals sender value

Fault tolerance parameter f

Maximum number of tolerated faulty nodes

Byzantine faults

Faulty nodes may act arbitrarily and collude

Byzantine Agreement (BA)

All nodes start with private values

BA initial values

Each node has bi* in V

BA termination

All honest nodes eventually output a value

BA agreement

Honest outputs must match

BA validity

If all honest inputs equal outputs equal that value

BB vs BA validity

BB depends on sender BA depends on unanimous input

State Machine Replication (SMR)

Agree on ordered transaction history

Pending transaction set PTXi

Transactions waiting to be processed

Transaction notation txℓ

Index only distinguishes transactions

Transaction semantics

No assumptions about functionality

Sync SMR tx delivery

Finite set may arrive at beginning of round

SMR pending update

New tx added to PTX set upon delivery

History Hi

Local append-only ordered transaction list

History in sync Hi^t

History at end of round t

History ordering symbol

≺ denotes transaction order

Example history

H3={tx5≺tx1≺tx10≺tx2}

Async tx model

Transactions treated as messages

Main message/tx loop

Loop handles both messages and transactions

Async node action

May send messages or process transactions

History updates

Occurs when receiving message or transaction

SMR safety (consistency)

One honest history is prefix of another

Prefix relation

Hi ⪯ Hj means Hi is prefix of Hj

Safety intuition

Honest nodes never disagree on order

Invalid history example

Different relative order violates safety

SMR liveness

Transactions reaching one honest node reach all

Sync liveness phrasing

Eventually included by some round

Async liveness phrasing

Eventually included in some loop iteration

SMR fault tolerance

Tolerates up to f faulty nodes

Consensus termination meaning

Honest nodes eventually decide

Consensus agreement meaning

No divergence among honest outputs

Consensus validity meaning

Output reflects correct initial condition

Execution definition

Specific message delivery schedule

Adversarial scheduling

Worst-case message ordering allowed

Honest node

Node that follows protocol Π

Faulty node

Node deviating from protocol

Message history

All messages received so far

Round number dependence

Allowed in sync and partial sync

No timers in async

Protocols cannot rely on time

Timeout logic

Possible only when Δ known

Global vs local time

Global in sync partial absent in async

Event-driven computation

Core idea of asynchronous protocols

Delivery bound importance

Enables reasoning about progress

Unknown delays problem

Hardest aspect of async consensus

Consensus goal summary

Termination + Agreement + Validity

SMR goal summary

Safety + Liveness

History append-only

Transactions never removed or reordered

Prefix safety intuition

Nodes may lag but not conflict

Transaction propagation

Eventually reaches all honest histories