How does the spread of behavior affect consensus-based collective decision-making among animals, humans or swarming robots? In prior research, such propagation of behavior on social networks has been found to exhibit a transition from simple contagion—i.e, based on pairwise interactions—to a complex one—i.e., involving social influence and reinforcement. However, this rich phenomenology appears so far limited to threshold-based decision-making processes with binary options. Here, we show theoretically, and experimentally with a multi-robot system, that such a transition from simple to complex contagion can also be observed in an archetypal model of distributed decision-making devoid of any thresholds or nonlinearities. Specifically, we uncover two key results: the nature of the contagion—simple or complex—is tightly related to the intrinsic pace of the behavior that is spreading, and the network topology strongly influences the effectiveness of the behavioral transmission in ways that are reminiscent of threshold-based models. These results offer new directions for the empirical exploration of behavioral contagions in groups, and have significant ramifications for the design of cooperative and networked robot systems.