Kaplan, F. Simple models of distributed co-ordination. Connection Science, 17(3-4):249-270, 2005.

Sony CSL authors: Frédéric Kaplan


Distributed coordination is the result of dynamical processes enabling independent agents to coordinate their actions without the need of a central coordinator. In the past years, several computational models have illustrated the role played by such dynamics for self-organizing communication systems. In particular, it has been shown that agents could bootstrap shared convention systems based on simple local adaptation rules. Such models have played a pivotal role for our understanding of emergent language processes. However, only few formal or theoretical results were published about such systems. This article discusses deliberately simple computational models in order to make progress in understanding the underlying dynamics responsible for distributed coordination and the scaling laws of such systems. In particular, the article focuses on explaining the convergence speed of those models, a largely underinvestigated issue. Conjectures obtained through empirical and qualitative studies of these simple models are compared with results of more complex simulations and discussed in relation with theoretical models formalized using Markov chains, game theory and Polya processes.

Keywords: distributed co-ordination, self-organizing lexicon, naming game, scaling laws, polya processes, markov chains, stochastic games


[PDF] Adobe Acrobat PDF file

BibTeX entry

@ARTICLE { kaplan:05e, AUTHOR="Kaplan, F.", JOURNAL="Connection Science", NUMBER="3--4", PAGES="249--270", TITLE="Simple models of distributed co-ordination", VOLUME="17", YEAR="2005", }