Vi anser att en distribuerad version av grafen prospektering och kartering problem där en mobil agent måste passera kanterna på en omärkt (dvs anonym) graf och återgå till sin utgångspunkt, bygga en karta över grafen i processen. I vårt fall, i stället för en enda agent, finns det k identiska (dvs. ömsesidigt oskiljaktiga) agenter ursprungligen utspridda bland n noderna i grafen. Agenterna kan kommunicera genom att skriva till de små offentliga anslagstavlor som finns på varje nod. Målet är att varje agent ska bygga en identiskt märkt karta över grafen; vi kallar detta för problemet med Labelled Map Construction. Detta problem är mycket svårare än utforskning av en enda agent, eftersom det innebär att uppnå samarbete mellan flera agenter. Faktum är att detta problem i vissa fall är deterministiskt olösligt. Vi presenterar deterministiska algoritmer som framgångsrikt och effektivt löser problemet under förutsättning att värdena för n och k är samprime med varandra. Vi visar också hur problemet med Labelled Map Construction är relaterat till andra problem som ledarval och mötesplats för agenter.
Das m.fl. REF beaktade k-agenternas undersökning i whiteboardmodellen.
Map construction of unknown graphs by multiple agents
{'venue': 'Theor. Comput. Sci.', 'journal': 'Theor. Comput. Sci.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}