Decentralized group formation

Anna Chmielowiec, Spyros Voulgaris, Maarten van Steen* (Corresponding Author)

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

4 Citations (Scopus)
23 Downloads (Pure)


Imagine a network of entities, being it replica servers aiming to minimize the probability of data loss, players of online team-based games and tournaments, or companies that look into co-branding opportunities. The objective of each entity in any of these scenarios is to find a few suitable partners to help them achieve a shared goal: replication of the data for fault tolerance, winning the game, successful marketing campaign. All information attainable by the entities is limited to the profiles of other entities that can be used to assess the pairwise fitness. How can they create teams without help of any centralized component and without going into each other’s way? We propose a decentralized algorithm that helps nodes in the network to form groups of a specific size. The protocol works by finding an approximation of a weighted k-clique matching of the underlying graph of assessments. We discuss the basic version of the protocol, and explain how dissemination via gossiping helps in improving its scalability. We evaluate its performance through extensive simulations.

Original languageEnglish
Article number12
Number of pages18
JournalJournal of internet services and applications
Issue number1
Publication statusPublished - 1 Jan 2014
Externally publishedYes


  • Distributed clique formation
  • Web service composition


Dive into the research topics of 'Decentralized group formation'. Together they form a unique fingerprint.

Cite this