Granular Synchrony Timing Model

1

Granular Synchrony Authored by: Neil Giridharan, Ittai Abraham, Petah Tikva, Natacha Crooks, Kartik Nayak, Ling Ren Presented by J. Demore 2

Introduction - Timing models: - Synchronous: Message arrives before known upper bound - Partially Synchronous: Unknown, finite Global Stabilization Time (GST) - Network is Asynchronous before GST, Synchronous afterwards - Asynchronous: Messages arrive in any finite amount of time - Synchronous models consider sender or recipient faulty after a single violation Asynchronous protocol to tolerate even just a single crash fault must have an infinite execution [FLP Impossibility] Partially Synchronous models try to balance, but is too close to asynchronous with the same fault tolerance - - 3

Problem - Current distributed system timing models are too coarse grained - Synchronous / Partially synchronous / Asynchronous - Causes models to make assumptions that are too strong, or too weak - Consensus algorithms must still tolerate crash/Byzantine faults 4

Proposed Solution Granular Synchrony timing model - Modeled via graph - Mixture of synchronous, partially synchronous, and asynchronous links - Each of the three current timing models are extreme cases , this model servers as an intermediate between synchrony and partial synchrony. - CFT of f n/2, or BFT of f n/3, without full synchrony - Reaches consensus if conditions are satisfied within communication graph instead - Graph agnostic: does not assume knowledge of the graph - Digital signatures assumed for Byzantine Tolerances 5

Variants: Granular Partial Synchrony - CFT: iff quorum |n-f| nodes communicates synchronously - BFT: iff any set { n - 2f } correct nodes can communicate synchronously - Both require min f+1 nodes, despite faulty nodes 6

Variants: Granular Asynchrony - CFT - requires < n-f nodes outside largest connected component of graph following removal of crashed nodes, asynchronous edges - Passes FLP Impossibility in undirected graphs due to weaker conditions (discussed later) - BFT - requires a correct node, with partially synchronous paths to at least f correct nodes. - Deterministic BFT in graph agnostic algorithms only - Requires use of randomization - Does not consider algorithms that are not graph agnostic 7

Algorithm: Granular Synchrony [CFT] Round Robin leader selection, terminates after consensus reached by honest leader - Initially locked, and updates lock to current view and proposed value from leader, when leader does Propose - Every node sends STATUS message to leader, starts timer for view - Leader sends Propose after n-1 STATUS received. Status messages contain the view(v). Propose updates v to highest v received - Commits after n-f VOTE received, or single COMMIT, val - Single Commit due to CFT process, no Byzantines - Changes view after timer expires with no commit, sends NewView to other nodes requesting a view change. Waits for max 2d , which is worst-case round trip delay to send NewView and receive LOCKED 8

Algorithm: Granular Asynchrony [CFT] Can be adapted iff Theorem 5 and 10 hold (discussed later). Theorem 10 required for liveness as Async has no GST - Initially locked, each node broadcasts STATUS, view, lock to all, and forwards a set of all STATUS messages after receiving n-f. Starts 3d . Locks and votes for Proposal - View change requested if no Propose message received within 3d timer. Broadcasts ViewChange to all nodes. If n-f ViewChange for current view are received, sends NewView to all nodes, which is a confirmation of view change that updates the view. Other protocols follow Granular Synchrony 9

Algorithm: Granular Partial Synchrony [BFT] Extended from Granular Synchrony and Granular Asynchrony protocols, achieves external validity, but leverages graph condition of Theorem 10 to achieve f+1 tolerance. - View starts, each node sends STATUS to leader and starts view timer - Leader proposes after set S of n-f STATUS messages, of highest val - When a node receives Propose, checks if val is the highest in the set. Proposes this value and starts timer d to receive conflicting Propose within same view, which indicates faulty leader. - If faulty leader, ViewChange is proposed. - Otherwise, broadcasts VOTE-1 - Locks val, v as L and sends VOTE-2 after n-f VOTE-1. This redundancy guarantees locked value is unique. - Sends COMMIT after a set C of n-f VOTE-2, or commits and terminates if COMMIT, C received - View Change done if f+1 processes propose ViewChange, nodes stop sending VOTE-1 and VOTE-2, broadcasts Lock, and waits 2d to enter new view. Timer is sufficient for the lock broadcast to send/receive. 10

Algorithm: Granular Asynchrony [BFT] Similar to Partial Synchrony, with adapted Status and View Change steps - Adapts status to send to ALL nodes, vs. only Leader - Stores these as a set, and broadcasts set after n-f received. Starts 3d , then starts propose, vote and commit steps from previous. - Leader suspected faulty if no propose received before timer expires. n-f ViewChange must be received (Granular Partial Asynchrony is f+1 to initiate). Starts timer of 2d (Same as Granular Synchrony) 11

Algorithm: BFT with Unanimity Validity Unanimity is complete agreement by every pair of processors - In short, modifies the algorithm to lock in correct values before the first view starts - Uses a timer, receives inputs and unions the set of inputs. Forwards the set when timer to all. - When n-f forwarded input sets are received, locks the value if correct for f+1 messages 12

Definitions - D1: Synchronous Path. Node a has synchronous path to Node b, if there exists a sequence of synchronous edges (a, i1), (ik, b) where every intermediate node ijis correct. D2: Set of nodes A have a synchronous path to set of nodes B, if for every node b in B, there exists some node a in A such that a has a synchronous path to b. D3: Length of a path is the number of edges in it. If a has a synchronous path to b, the distance is the length of the shortest synchronous path between them. D4: Standard Consensus. Every node has initial input, must decide a value that satisfies agreement, termination, and validity. - - - 13

Theorems T5and T13specify the bounds for which a non-Byzantine set, A, and a larger non-Byzantine set, B, will maintain a synchronous or partially synchronous message bounds On the right, proof (Contradiction) supposes there would be an algorithm to solve CFT under disjoint sets. Here, (a) can agree v=1, while (b) and (c) could agree on v=0. 14

Theorems Proof by Lemma 6: No node will be able to commit a different value, since v (val) = v (val) - - Round-robin leader election means there is a correct leader eventually When nodes eventually enter view within time bound GST + 2d , all correct nodes will receive the message, vote, and commit within the view timer 4 15

Theorems - After removing asynchronous edges and faulty nodes from the graph, followed by removing the largest connected component, there are fewer than n-f nodes. This restriction circumvents FLP Impossibility - 16

Theorems - These are all fairly intuitive following the others. 17

Theorems 18

Thank You! 19