Abstrakt. Två mobila agenter (robotar), som utgår från olika noder i ett n-node-nätverk vid eventuellt olika tidpunkter, måste mötas på samma nod. Detta problem kallas mötesplats. Agenter rör sig i synkrona rundor med hjälp av en deterministisk algoritm. I varje omgång, beslutar en agent att antingen förbli sysslolös eller att flytta till en av de angränsande noderna. Varje agent har ett distinkt heltal etikett från uppsättningen {1,.., L}, som det kan använda i utförandet av algoritmen, men det vet inte etiketten på den andra agenten. Det viktigaste effektivitetsmåttet för en mötesplats algoritms prestanda är dess tid, dvs antalet rundor från början av den senare agenten till mötet. Om D är avståndet mellan de ursprungliga positionerna av agenterna, då är  och (D) en uppenbar lägre gräns på tiden för mötesplatsen. Men om varje agens inte har någon annan initial kunskap än sin etikett, är tid O(D) vanligtvis omöjligt att uppnå. Vi studerar den minsta mängd information som måste finnas tillgänglig a priori för agenterna för att uppnå mötesplats i optimal tid (D). Efter standardparadigmet av algoritmer med råd, denna information ges till agenterna i början av ett orakel som känner till hela instansen av problemet, dvs. nätverket, startpositionerna för agenterna, deras väckarrundor, och båda av deras etiketter. Orakeln hjälper agenterna genom att förse dem med samma binära sträng som kallas råd, som kan användas av agenterna under deras navigering. Längden på denna sträng kallas storleken på råd. Vårt mål är att hitta den minsta storleken av råd som gör det möjligt för agenterna att mötas i tid (D). Vi visar att den här optimala storleken på rådgivningen är  till(D log(n/D)+log log L). Den övre gränsen bevisas genom att bygga en rådgivning sträng av denna storlek, och tillhandahålla en naturlig mötesplats algoritm med hjälp av denna rådgivning som fungerar i tid  och (D) för alla nätverk. Den motsvarande nedre gränsen, som är det viktigaste bidraget i detta dokument, bevisas genom att ställa ut klasser av nätverk för vilka det är omöjligt att uppnå mötesplats i tid (D) med mindre råd.
För det andra, i stället för att titta på avvägningar mellan kostnader och storleken på rådgivningen, som vi gör i det här dokumentet, låg fokus för REF på storleken på rådgivningen som var tillräcklig för att uppnå lägsta möjliga kostnad.
Fast Rendezvous with Advice
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}