Två mobila agenter som startar vid olika noder i ett okänt nätverk måste mötas. Denna uppgift är känd i litteraturen som mötesplats. Varje agent har en annan etikett som är ett positivt heltal känd för det, men okänd för den andra agenten. Agenter rör sig på ett asynkront sätt: agenternas hastighet kan variera och kontrolleras av en motståndare. Kostnaden för en mötesalgoritm är det totala antalet edge traversals av båda agenterna fram till deras möte. Den enda tidigare deterministiska algoritmen som löser detta problem har kostat exponentiellt i storleken på grafen och i den större etiketten. I detta papper presenterar vi en deterministisk mötesplats algoritm med kostnad polynom i storleken på grafen och i längden på den mindre etiketten. Därför minskar vi kostnaden exponentiellt i storleken av grafen och dubbelt exponentiellt i etiketter av agenter. Som en tillämpning av vår mötesplats algoritm löser vi flera grundläggande problem med team av okänd storlek större än 1 av märkta agenter flyttar asynkront i okända nätverk. Bland dem är följande problem: team storlek, där varje agent måste hitta det totala antalet agenter, ledarval, där alla agenter måste producera etiketten på en enda agent, perfekt namnbyte där alla agenter måste anta nya olika etiketter från uppsättningen {1,..., k}, där k är antalet agenter, och skvaller, där varje agent har initialt en bit information (värde) och alla agenter måste producera alla värden. Med hjälp av vår mötesplats algoritm löser vi alla dessa problem på kostnad polynom i storleken på grafen och i den minsta längden av alla etiketter av deltagande agenter.
I synnerhet är det huvudsakliga resultatet av REF en asynkron mötesplatsalgoritm som arbetar i en godtycklig graf till anskaffningsvärde (mätt med antalet kanttraversaler) polynom i grafens storlek och i logaritmen för den mindre etiketten.
How to meet asynchronously at polynomial cost
{'venue': "PODC '13", 'journal': None, 'mag_field_of_study': ['Computer Science']}