Abstract Två mobila agenter, med start från olika noder i ett nätverk vid möjligen olika tidpunkter, måste träffas på samma nod. Detta problem kallas mötesplats. Agenter rör sig i synkrona rundor. Varje agent har ett distinkt heltal etikett från uppsättningen {1,.., L}. Två huvudsakliga effektivitetsåtgärder för mötesplatsen är dess tid (antalet rundor fram till mötet) och dess kostnad (det totala antalet kanttraversaler). Vi undersöker kompromisser mellan dessa två åtgärder. Ett naturligt riktmärke för både tid och kostnad för möte i ett nätverk är det antal egg traversals som behövs för att besöka alla noder av nätverket, kallas prospekteringstiden. Därför uttrycker vi tid och kostnad för mötesplatsen som funktioner av en övre gräns E på tiden för utforskning (där E och en motsvarande utforskningsförfarande är kända för båda agenter) och av storleken L av etiketten utrymme. Vi presenterar två naturliga mötesplatsalgoritmer. Algorithm Cheap har kostat O(E) (och, i själva verket, en version av denna algoritm för modellen där agenterna startar samtidigt har kosta exakt E) och tid O(E L). Algoritm Fast har både tid och kostnad O(E log L). Våra viktigaste bidrag är lägre gränser som visar att, kanske förvånande, dessa två algoritmer fånga kompromisser mellan tid och kostnad för mötesplats nästan hårt. Vi visar att varje deterministisk mötesplatsalgoritm för kostnadsasymptotiskt E (dvs. kostnad E + o(E)) måste ha tid (E L). Å andra sidan visar vi att varje deterministisk mötesplatssalgoritm med tids komplexitet O(E log L) måste ha kostat E log L. B Avery Miller Ordförande
Detta betonades nyligen i REF där författarna studerade avvägningarna mellan kostnad och tid för det deterministiska mötesplatssproblemet.
Time versus cost tradeoffs for deterministic rendezvous in networks
{'venue': 'Distributed Computing', 'journal': 'Distributed Computing', 'mag_field_of_study': ['Computer Science', 'Engineering']}