The paper studies how a group of N agents reaches agreement when they repeatedly update their opinions by sampling others and applying a fixed rule. At each step, a randomly chosen agent looks at r other randomly chosen agents and sets its own state to whatever a given aggregation function outputs. The question is: how long does it take until everyone agrees? The aggregation function is "monotone," meaning that if more people hold a certain opinion, it can only make the output weakly more likely to favor that opinion. Examples include majority voting, requiring unanimous agreement among sampled agents, or simply copying one specific agent (the dictator rule).
The answer turns out to depend critically on two numbers associated with the rule, called endpoint degrees. These measure how the rule behaves at the extremes: how easily it produces a "1" output when almost everyone holds opinion 0, and vice versa. When neither of these endpoint degrees equals 1, consensus is reached quickly, in time proportional to N times the logarithm of N at most, regardless of the starting configuration. This is relatively fast. When the rule is a dictator, the dynamics mimic the classical "voter model," and consensus takes much longer, on the order of N squared times a factor related to how evenly split the initial opinions are.
The most interesting intermediate case arises when exactly one endpoint degree equals 1 and the other equals 0. This covers rules like requiring all sampled agents to agree before updating. Here, the consensus time falls between the fast logarithmic regime and the slow quadratic regime, scaling as N raised to a power strictly between 1 and 2. The exact exponent depends on a structural property of the rule called its "residual rule," specifically the minimum number of sampled agents that can force the output to a particular value. The paper provides matching upper and lower bounds throughout, giving a fairly complete picture of how the shape of the aggregation rule determines the speed of reaching consensus.