Sammanfattning Betrakta en nätverksbaserad miljö, stödja mobila agenter, där det finns ett svart hål: en skadlig värd som gör sig av med besökande agenter vid deras ankomst, lämnar inga observerbara spår av en sådan förstörelse. Det svarta hålets sökproblem är att samla ett team av asynkrona mobila agenter, utföra samma protokoll och kommunicera med hjälp av whiteboards, för att framgångsrikt identifiera platsen för det svarta hålet; vi är intresserade av lösningar som är generiska (dvs. topologi-oberoende). Vi etablerar snäva gränser på storleken på laget (dvs. antalet agenter), och kostnaden (dvs. antalet rörelser) för en storlekoptimal lösning protokoll. Dessa gränser beror på vilken kunskap agenterna har om nätverket och på hur konsekvent de lokala märkningarna är. I synnerhet bevisar vi att: med topologisk okunnighet + 1 agenter behövs och räcker, och kostnaden är (n 2 ), där är den maximala graden av en nod och n är antalet noder i nätverket; med topologisk okunnighet men i närvaro av riktning endast två agenter räcker och kostnaden är (n 2 ); och med fullständig topologisk kunskap räcker endast två agenter och kostnaden är (n log n). Alla de övre bevisen är konstruktiva.
Om nätverkets topologi är okänd behövs minst + 1 agenter, där  till är den maximala nodgraden i grafen REF.
Searching for a black hole in arbitrary networks: optimal mobile agents protocols
{'venue': 'Distributed Computing', 'journal': 'Distributed Computing', 'mag_field_of_study': ['Computer Science', 'Engineering']}