{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,26]],"date-time":"2025-09-26T00:15:10Z","timestamp":1758845710240},"reference-count":30,"publisher":"Sociedade Brasileira de Computacao - SB","issue":"1","license":[{"start":{"date-parts":[[2014,10,9]],"date-time":"2014-10-09T00:00:00Z","timestamp":1412812800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Internet Serv Appl"],"published-print":{"date-parts":[[2014,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>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\u2019s 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 <jats:italic>k<\/jats:italic>-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.<\/jats:p>","DOI":"10.1186\/s13174-014-0012-2","type":"journal-article","created":{"date-parts":[[2014,10,8]],"date-time":"2014-10-08T01:29:35Z","timestamp":1412731775000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Decentralized group formation"],"prefix":"10.5753","volume":"5","author":[{"given":"Anna","family":"Chmielowiec","sequence":"first","affiliation":[]},{"given":"Spyros","family":"Voulgaris","sequence":"additional","affiliation":[]},{"given":"Maarten van","family":"Steen","sequence":"additional","affiliation":[]}],"member":"3742","published-online":{"date-parts":[[2014,10,9]]},"reference":[{"key":"12_CR1","volume-title":"The Open Grid Services Architecture, Version 1.5.GGF Informational Document GFD-I.080.","author":"I Foster","year":"2006","unstructured":"Foster I, Berry D, Djaoui A, Grimshaw A, Horn B, Kishimoto H, Maciel F, Savva A, Siebenlist F, Subramaniam R, Treadwell J, Von Reich J (2006) The Open Grid Services Architecture, Version 1.5.GGF Informational Document GFD-I.080."},{"key":"12_CR2","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1109\/SASO.2010.14","volume-title":"SASO 2010 proceedings of the 4th, IEEE international conference on self-adaptive and self-organizing systems","author":"A Chmielowiec","year":"2010","unstructured":"Chmielowiec A, van Steen M: Optimal decentralized formation of k-member partnerships. In SASO 2010 proceedings of the 4th, IEEE international conference on self-adaptive and self-organizing systems. IEEE Computer Society, Washington DC; 2010:154\u2013163. doi:10.1109\/SASO.2010.14"},{"key":"12_CR3","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1145\/1462802.1462807","volume-title":"MW4SOC \u201808: proceedings of the 3rd workshop on middleware for service oriented computing","author":"A Chmielowiec","year":"2008","unstructured":"Chmielowiec A, Pierre G, Gordijn J, van Steen M: Technical challenges in market-driven automated service provisioning. In MW4SOC \u201808: proceedings of the 3rd workshop on middleware for service oriented computing. ACM, New York; 2008:25\u201330. doi:10.1145\/1462802.1462807"},{"issue":"13","key":"12_CR4","doi-asserted-by":"publisher","first-page":"2321","DOI":"10.1016\/j.comnet.2009.03.013","volume":"53","author":"M Jelasity","year":"2009","unstructured":"Jelasity M, Montresor A, Babaoglu O: T-man: gossip-based fast overlay topology construction. Comput Netw 2009, 53(13):2321\u20132339. doi:10.1016\/j.comnet.2009.03.013","journal-title":"Comput Netw"},{"key":"12_CR5","volume-title":"Epidemic-based self-organization in peer-to-peer systems. PhD thesis","author":"S Voulgaris","year":"2006","unstructured":"Voulgaris S: Epidemic-based self-organization in peer-to-peer systems. PhD thesis. Vrije Universiteit, Amsterdam, The Netherlands; 2006."},{"key":"12_CR6","first-page":"17","volume-title":"SFCS \u201880: proceedings of the 21st annual symposium on foundations of computer science","author":"S Micali","year":"1980","unstructured":"Micali S, Vazirani VV: An \"Equation missing\"  No EquationSource Format=\"TEX\", only image and EquationSource Format=\"MATHML\"  algoithm for finding maximum matching in general graphs. In SFCS \u201880: proceedings of the 21st annual symposium on foundations of computer science. IEEE Computer Society, Washington, DC; 1980:17\u201327. doi:10.1109\/SFCS.1980.12"},{"key":"12_CR7","first-page":"586","volume":"443","author":"N Blum","year":"1990","unstructured":"Blum N: A new approach to maximum matching in general graphs. Automata Languages Program 1990, 443: 586\u2013597. doi:10.1007\/BFb0032060","journal-title":"Automata Languages Program"},{"issue":"4","key":"12_CR8","doi-asserted-by":"publisher","first-page":"815","DOI":"10.1145\/115234.115366","volume":"38","author":"HN Gabow","year":"1991","unstructured":"Gabow HN, Tarjan RE: Faster scaling algorithms for general graph matching problems. J ACM 1991, 38(4):815\u2013853. doi:10.1145\/115234.115366 10.1145\/115234.115366","journal-title":"J ACM"},{"key":"12_CR9","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1007\/s10479-005-2452-3","volume":"138","author":"P Hell","year":"2005","unstructured":"Hell P, Klein S, Nogueira LT, Protti F: Packing r-cliques in weighted chordal graphs. Ann Oper Res 2005, 138: 179\u2013187. 10.1007\/s10479-005-2452-3","journal-title":"Ann Oper Res"},{"key":"12_CR10","doi-asserted-by":"crossref","first-page":"152","DOI":"10.1007\/978-3-540-75142-7_14","volume":"4731","author":"A Czygrinow","year":"2007","unstructured":"Czygrinow A, Ha\u0144\u0107kowiak M: Distributed approximations for packing in unit-disk graphs. Distr Comput 2007, 4731: 152\u2013164. doi:10.1007\/978\u20133-540\u201375142\u20137_14","journal-title":"Distr Comput"},{"key":"12_CR11","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1145\/1378533.1378541","volume-title":"Proceedings of the twentieth annual symposium on parallelism in algorithms and architectures. SPAA \u201808","author":"A Czygrinow","year":"2008","unstructured":"Czygrinow A, Ha\u0144\u0107kowiak M, Wawrzyniak W: Distributed packing in planar graphs. In Proceedings of the twentieth annual symposium on parallelism in algorithms and architectures. SPAA \u201808. ACM, New York; 2008:55\u201361. doi:10.1145\/1378533.1378541"},{"issue":"6","key":"12_CR12","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0020-0190(94)90105-8","volume":"49","author":"V Kann","year":"1994","unstructured":"Kann V: Maximum bounded h-matching is max snp-complete. Inform Process Lett 1994, 49(6):309\u2013318. doi:10.1016\/0020\u20130190(94)90105\u20138","journal-title":"Inform Process Lett"},{"key":"12_CR13","doi-asserted-by":"crossref","unstructured":"Crescenzi P, Kann V (1998) A compedium of NP optimization problems.http:\/\/www.nada.kth.se\/~viggo\/problemlist\/compendium.html","DOI":"10.1007\/3-540-63248-4_10"},{"key":"12_CR14","volume-title":"STOC \u201878 proceedings of the tenth annual ACM symposium on theory of computing","author":"DG Kirkpatrick","year":"1978","unstructured":"Kirkpatrick DG, Hell P (1978) On the completeness of a generalized matching problem In: STOC \u201878 proceedings of the tenth annual ACM symposium on theory of computing, 240\u2013245."},{"key":"12_CR15","first-page":"434","volume-title":"SODA \u201890: proceedings of the first annual, ACM-SIAM symposium on discrete algorithms","author":"HN Gabow","year":"1990","unstructured":"Gabow HN: Data structures for weighted matching and nearest common ancestors with linking. In SODA \u201890: proceedings of the first annual, ACM-SIAM symposium on discrete algorithms. Society for Industrial and Applied Mathematics, Philadelphia; 1990:434\u2013443."},{"key":"12_CR16","unstructured":"Hoepman J-H (2004) Simple Distributed Weighted Matchings. ., [http:\/\/arxiv.org\/abs\/cs\/0410047]"},{"key":"12_CR17","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1145\/1378533.1378558","volume-title":"SPAA \u201808: proceedings of the twentieth annual symposium on parallelism in algorithms and architectures","author":"Z Lotker","year":"2008","unstructured":"Lotker Z, Patt-Shamir B, Pettie S: Improved distributed approximate matching. In SPAA \u201808: proceedings of the twentieth annual symposium on parallelism in algorithms and architectures. ACM, New York; 2008:129\u2013136. doi:10.1145\/1378533.1378558"},{"key":"12_CR18","volume-title":"ACM","author":"T Nieberg","year":"2008","unstructured":"Nieberg T2008. Local, distributed weighted matching on general and wireless topologies. ACM, New York. doi:10.1145\/1400863.1400880."},{"key":"12_CR19","volume-title":"In: Stabilization, safety, and security of distributed systems","author":"F Manne","year":"2007","unstructured":"Manne F, Mjelde M (2007) A self-stabilizing weighted matching algorithm In: Stabilization, safety, and security of distributed systems, 383\u2013393.. LNCS, vol 4838\/2007. doi:10.1007\/978\u20133-540\u201376627\u20138_29."},{"issue":"6","key":"12_CR20","doi-asserted-by":"publisher","first-page":"971","DOI":"10.1016\/j.dam.2005.11.003","volume":"154","author":"R Hassin","year":"2006","unstructured":"Hassin R, Rubinstein S: An approximation algorithm for maximum triangle packing. Discrete Appl Math 2006, 154(6):971\u2013979. 10.1016\/j.dam.2005.11.003","journal-title":"Discrete Appl Math"},{"issue":"7","key":"12_CR21","doi-asserted-by":"publisher","first-page":"1640","DOI":"10.1016\/j.dam.2008.11.009","volume":"157","author":"Z-Z Chen","year":"2009","unstructured":"Chen Z-Z, Tanahashi R, Wang L: An improved randomized approximation algorithm for maximum triangle packing. Discrete Appl Math 2009, 157(7):1640\u20131646. doi:10.1016\/j.dam.2008.11.009","journal-title":"Discrete Appl Math"},{"key":"12_CR22","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/3-540-49116-3_24","volume-title":"In STACS 99: proceedings symposium on theoretical aspects of computer science","author":"R Preis","year":"1999","unstructured":"Preis R: Linear time 1\/2-approximation algorithm for maximum weighted matching in general graphs. In In STACS 99: proceedings symposium on theoretical aspects of computer science. Springer, Berlin; 1999:259\u2013269. doi:10.1007\/3\u2013540\u201349116\u20133_24"},{"key":"12_CR23","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1002\/net.3230130404","volume":"13","author":"D Avis","year":"1983","unstructured":"Avis D: A survey of heuristics for the weighted matching problem. Networks 1983, 13: 475\u2013493. doi:10.1002\/net.3230130404","journal-title":"Networks"},{"key":"12_CR24","volume-title":"Vrije Universiteit Amsterdam.","author":"A Chmielowiec","year":"2014","unstructured":"Chmielowiec A (2014) Decentralized k-clique matching. PhD thesis. Vrije Universiteit Amsterdam."},{"issue":"11","key":"12_CR25","doi-asserted-by":"publisher","first-page":"2885","DOI":"10.1016\/j.cor.2008.12.020","volume":"36","author":"J Brimberg","year":"2009","unstructured":"Brimberg J, Mladenovic N, Urosevic D, Ngai E: Variable neighborhood search for the heaviest k-subgraph. Comput Oper Res 2009, 36(11):2885\u20132891. doi:10.1016\/j.cor.2008.12.020","journal-title":"Comput Oper Res"},{"key":"12_CR26","volume-title":"Handbook of metaheuristicsInternational, Series in Operations Research & Management Science, vol. 146","author":"M Gendreau","year":"2010","unstructured":"Gendreau M, Potvin J-Y(eds.): Handbook of metaheuristicsInternational, Series in Operations Research & Management Science, vol. 146. Springer, New York; 2010."},{"issue":"1","key":"12_CR27","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1007\/s10479-009-0657-6","volume":"175","author":"P Hansen","year":"2010","unstructured":"Hansen P, Moreno P\u00e9rez JA: Variable neighbourhood search: methods and applications. Ann Oper Res 2010, 175(1):367\u2013407. doi:10.1007\/s10479\u2013009\u20130657\u20136","journal-title":"Ann Oper Res"},{"issue":"5","key":"12_CR28","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/1317379.1317381","volume":"41","author":"A-M Kermarrec","year":"2007","unstructured":"Kermarrec A-M, van Steen M: Gossiping in distributed systems. SIGOPS Oper Syst Rev 2007, 41(5):2\u20137. doi:10.1145\/1317379.1317381","journal-title":"SIGOPS Oper Syst Rev"},{"issue":"3","key":"12_CR29","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1145\/1275517.1275520","volume":"25","author":"M Jelasity","year":"2007","unstructured":"Jelasity M, Voulgaris S, Guerraoui R, Kermarrec A-M, van Steen M: Gossip-based peer sampling. ACM Trans Comput Syst 2007, 25(3):8. doi:10.1145\/1275517.1275520","journal-title":"ACM Trans Comput Syst"},{"key":"12_CR30","unstructured":"Jelasity M, Montresor A, Jesi GP, Voulgaris SThe Peersim Simulator. ., [http:\/\/peersim.sourceforge.net\/]"}],"container-title":["Journal of Internet Services and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s13174-014-0012-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1186\/s13174-014-0012-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s13174-014-0012-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13174-014-0012-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,9]],"date-time":"2022-02-09T22:14:57Z","timestamp":1644444897000},"score":1,"resource":{"primary":{"URL":"https:\/\/jisajournal.springeropen.com\/articles\/10.1186\/s13174-014-0012-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,10,9]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,12]]}},"alternative-id":["12"],"URL":"https:\/\/doi.org\/10.1186\/s13174-014-0012-2","relation":{},"ISSN":["1867-4828","1869-0238"],"issn-type":[{"value":"1867-4828","type":"print"},{"value":"1869-0238","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,10,9]]},"assertion":[{"value":"29 May 2014","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 September 2014","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 October 2014","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"12"}}