2019/11/12 by Quan Nguyen, Nguyen, Quan, André Cronje +3
Computer Science · #Caching and Content Delivery #Data Structures and Algorithms (cs.DS) #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Parallel #Peer-to-Peer Network Technologies #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1911.04629
openalex publication_date 2019/11/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The problem of peer selection, which randomly selects a peer from a set, is commonplace in Proof-of-Stake (PoS) protocols. In PoS, peers are chosen randomly with probability proportional to the amount of stake that they possess. This paper presents an approach that relates PoS peer selection to Roulette-wheel selection, which is frequently used in genetic and evolutionary algorithms or complex network modelling. In particular, we introduce the use of stochastic acceptance algorithm [6] for fast peer selection. The roulette-wheel selection algorithm [6] achieves O(1) complexity based on stochastic acceptance, whereas searching based algorithms may take O(N ) or O(logN ) complexity in a network of N peers.