•   When: Thursday, December 03, 2020 from 09:00 AM to 11:00 AM
•   Speakers: Ivan Avramovic
•   Location: Virtual
•   Export to iCal

Abstract

This research investigates two problems in information dissemination with combinatorial complexity – the first of which is consensus sorting.  Consensus sorting is a randomized algorithm which uses a hill-climbing approach to achieve sortedness.  It uses large data sets with sorting guided by a fitness function derived from a data consensus, as an abstraction of problems using large public data sets. The dissertation compares actual sorting behavior to the ideal, explaining the disparity between empirical results and theoretical results.  It constructs a model describing empirical convergence, develops conditions under which the model will hold, and provides in-depth analysis of two of effective sorting metrics.

The second problem, perpetual gossiping, is an all-to-all information dissemination problem on a network which has applicability both in social networks and in distributed systems such as RAIDS. A gossiping sequence ensures that every node in the network is able to reach every other node via a sequence of calls. The aim is to design infinite schemes such that information which arises at any time will reach all other nodes efficiently. Optimal perpetual gossiping solutions have long proven difficult to find. This research contributes by demonstrating a general optimal solution algorithm; producing optimal solutions for several classes of tree networks; proving NP-completeness optimal walk-around schemes; and providing a toolkit of propositions relating to the significance of contiguity in optimal schemes.