Nominated Proof-of-Stake

• Intro to Nominated Proof-of-Stake
  • Validators and nominators
  • The NPoS scheme
  • The election process
• 1. Overview of results for the NPoS election problem
  • Problem statement and notation
  • Operational concerns
    • Efficient algorithms
    • Who elects the committee?
    • Committee-finding algorithm (off-chain)
    • Committee-comparing algorithm (on-chain)
  • Objectives
    • Balance
    • Support
    • Fair representation
  • Overview of our results
    • Committee finding
    • Committee-comparing
• 2. The min-norm max-flow problem
  • 1. Notation
  • 2. The min-norm max-flow problem (MNMF)
  • 3. Overview of algorithms for MNMF
  • 4. Technique using parametric flow algorithms
  • 5. The star balancing heuristic
• 3. The maximin support problem
  • 1. Definitions and notation
  • 2. The algorithm
    • Analysis of approximation factor
    • Analysis of running time
  • 3. Properties of the maximin support objective
• 4. Sequential Phragmén’s method.
  • 1. Notation
  • 2. Algorithm
  • 3. Axiomatic properties
• 5. A Phragmén-like Heuristic
  • Notation
  • The basic heuristic
  • (Parameterised) Proportional Justified Representation.
  • Local Search for provable PJR
  • Factor 3.15 approximation algorithm
    • Analysis