Probabilistic techniques for large-scale coordination and clustering

Gopalan, Aditya S.

Permalink

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

Description

Title

Probabilistic techniques for large-scale coordination and clustering

Author(s)

Gopalan, Aditya S.

Issue Date

2025-12-01

Director of Research (if dissertation) or Advisor (if thesis)

Dey, Partha S

Doctoral Committee Chair(s)

Dey, Partha S

Committee Member(s)

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

Department of Study

Industrial&Enterprise Sys Eng

Discipline

Industrial Engineering

Degree Granting Institution

University of Illinois Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

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

Abstract

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.

Graduation Semester

2025-12

Type of Resource

Thesis

Handle URL

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

Copyright and License Information

Copyright 2025 Aditya Gopalan

Owning Collections