Skip to main content
SpringerLink
Log in

Solving CSPs with Naming Games

  • Conference paper
Recent Advances in Constraints (CSCLP 2008)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 5655))

Abstract

Constraint solving problems (CSPs) represent a formalization of an important class of problems in computer science. We propose here a solving methodology based on the naming games. The naming game was introduced to represent N agents that have to bootstrap an agreement on a name to give to an object. The agents do not have a hierarchy and use a minimal protocol. Still they converge to a consistent state by using a distributed strategy. For this reason the naming game can be used to untangle distributed constraint solving problems (DCSPs). Moreover it represents a good starting point for a systematic study of DCSP methods, which can be seen as further improvement of this approach.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. Gosti, G.: Resolving CSP with Naming Games. In: Garcia de la Banda, M., Pontelli, E. (eds.) ICLP 2008. LNCS, vol. 5366, pp. 807–808. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  2. Dijkstra, E.W.: Self-Stabilizing Systems in Spite of Distributed Control. Communications of the ACM 17(11), 643–644 (1974)

    Article  MATH  Google Scholar 

  3. Ramanathan, R., Lloyes, E.L.: Scheduling Algorithms for Multi-Hop Radio Networks. In: Proceedings of the SIGCOMM 1992, Communication Architectures and Protocols, pp. 211–222. ACM Press, New York (1992)

    Google Scholar 

  4. Lessr, V.R.: An Overview of DAI: Viewing Distributed AI as Distributed Search. Japanese Society for Artificial Intelligence 5(4) (1990)

    Google Scholar 

  5. Yokoo, M., Durfee, E.H., Ishida, T., Kuwabara, K.: Distributed Constraint Satisfaction for Formalizing Distributed Problem Solving. In: 12th International Conference on Distributed Computing Systems (ICDCS 1992), pp. 614–621 (1992)

    Google Scholar 

  6. Collin, Z., Dechter, R., Katz, S.: On the Feasibility of Distributed Constraint Satisfaction. In: Proceedings of the Twelfth International Joint Conference of Artificial Intelligence (IJCAI 1991) (1991)

    Google Scholar 

  7. Baronchelli, A., Felici, M., Caglioti, E., Loreto, V., Steels, L.: Sharp Transition Toward Shared Vocabularies in Multi-Agent Systems. Journal of Statistical Mechanics, P06014 (2006)

    Google Scholar 

  8. Baronchelli, A., Dall’Asta, L., Barrat, A., Loreto, V.: Topology Induced Coarsening in Language Games Language. Phys. Rev. E 73, 015102(R) (2006)

    Google Scholar 

  9. Steels, L.: Self-Organizing Vocabularies. In: Langton, C., Shimohara, K. (eds.) Artificial Life V: Proceeding of the Fifth International Workshop on the Synthesis and Simulation of Living Systems, pp. 179–184 (1996)

    Google Scholar 

  10. Nowak, M.A., Plotkin, J.B., Krakauer, J.D.: The Evolutionary Language Game. Journal of Theoretical Biology 200, 147 (1999)

    Article  Google Scholar 

  11. Nowak, M.A., Komarova, N.L., Niyogi, P.: Computational and Evolutionary Aspects of Language. Nature 417, 611–617 (2002)

    Article  Google Scholar 

  12. Lenaerts, T., Jansen, B., Tuyls, K., de Vylder, B.: The Evolutionary Language Game: An orthogonal approach. Journal of Theoretical Biology 235(4), 566–582 (2005)

    Article  MathSciNet  Google Scholar 

  13. Grinstead, C.M., Snel, J.L.: Introduction to Probability. American Mathematical Society, Providence (2003)

    Google Scholar 

  14. Trick, M.: Network Resources for Coloring a Graph, http://mat.gsia.cmu.edu/COLOR/color.html

  15. Mycielski, J.: Sur le coloriage des graphes. Colloq. Math. 3, 161–162 (1955)

    MathSciNet  MATH  Google Scholar 

  16. Weisstein, E.W.: Mycielski Graph. MathWorld–A Wolfram Web Resource, http://mathworld.wolfram.com/MycielskiGraph.html

  17. Leighton, F.T.: A Graph Coloring Algorithm for Large Scheduling Problems. Journal of Research of the National Bureau of Standards 84, 489–505 (1979)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dipartimento di Scienze, Università “G. d’Annunzio” di Chieti-Pescara, Italy

    Stefano Bistarelli

  2. Institute of Informatics and Telematics (IIT-CNR) Pisa, Italy

    Stefano Bistarelli

  3. Dipartimento di Matematica e Informatica, Università degli Studi di Perugia, Italy

    Stefano Bistarelli & Giorgio Gosti

Authors
  1. Stefano Bistarelli
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Giorgio Gosti
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. ISTC-CNR, Institute for Cognitive Science and Technology, National Research Council of Italy, Via San Martino della Battaglia 44, 00185, Rome, Italy

    Angelo Oddi

  2. INRIA Rocquencourt, BP 105, 78153, Le Chesnay Cedex, France

    François Fages

  3. Department of Pure and Applied Mathematics, University of Padova, Via Trieste 63, 35121, Padova, Italy

    Francesca Rossi

Rights and permissions

Reprints and permissions

Copyright information

© 2009 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Bistarelli, S., Gosti, G. (2009). Solving CSPs with Naming Games. In: Oddi, A., Fages, F., Rossi, F. (eds) Recent Advances in Constraints. CSCLP 2008. Lecture Notes in Computer Science(), vol 5655. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-03251-6_2

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-03251-6_2

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-03250-9

  • Online ISBN: 978-3-642-03251-6

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation