Probabilistic techniques for large-scale coordination and clustering

This is a study of probabilistic methods used in coordination and clustering problems that arise in operations research. Specifically, we focus on infinite graph and infinite point process methods to analyze the dynamics of blockchains, the Hegselmann--Krause model, and a stochastic dynamic clustering model for data science. For blockchains, we show that the $t \to \infty$ limit is crucial for understanding how and when consensus occurs. Specifically, we use a randomly delayed recursion to capture the network dynamics, and show that in this model, an asymptotic criterion called one-endedness of the limiting blockchain is crucial to achieving consensus. We then study the distribution of the time to consensus. For the Hegselmann--Krause and dynamic clustering models, we show how stationarity and other symmetries of point processes shed insights into the nature of the fixed points. Included here is a formal statement and partial resolution of the $2R$-Conjecture for the Hegselmann--Krause model, which has been open (without a formal statement) since 2007. Our dynamic clustering model is also new and directly addresses the problem on an infinite dataset, rather than treating it as a limit of pre-limiting finite datasets. We show that this model has a unique stationary measure, with strong implications for the question of when to accept the clusters produced by a dynamic clustering algorithm.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Industrial Engineering

Grantor

University of Illinois Urbana-Champaign

Year dc:date

2025

Author dc:creator

• Gopalan, Aditya S.

Contributors dc:contributor

• Dey, Partha S
• Etesami, S. Rasoul
• Sowers, Richard B
• Subramanian, Vijay G

• Blockchain
• Hegselmann--Krause
• Clustering
• Distributed Averaging
• Consensus

Statement dc:rights

• Copyright 2025 Aditya Gopalan

Language dc:language

en

Handle dc:identifier

https://hdl.handle.net/2142/132551

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/132551