Abstrakt. I detta arbete studerar vi de grundläggande namn- och räkneproblemen (och vissa variationer) i nätverk som är anonyma, okända och möjligen dynamiska. Vid beräkningen måste noderna bestämma nätverkets storlek n och när de namnges måste de sluta med unika identiteter. Med anonym menar vi att alla noder börjar från identiska tillstånd möjligen från en unik ledare nod och av okänd att noder inte har någon förkunskaper om nätverket (förutom några minimal kunskap vid behov) inklusive okunnighet om n. Nätverksdynamik modelleras av 1-interval konnektivitet modell [KLO10], där kommunikationen är synkron och en värsta-fall motståndare väljer kanterna på varje runda subjekt till villkoret att varje instans är ansluten. Vi fokuserar först på statiska nätverk med sändning där vi bevisar att, utan en ledare, räkna är omöjligt att lösa och att namngivning är omöjligt att lösa även med en ledare och även om noder vet n. Dessa omöjligheter för över till dynamiska nätverk också. Vi visar också att en unik ledare räcker för att lösa räkna i linjär tid. Sedan fokuserar vi på dynamiska nätverk med sändning. Vi antar att dynamik gör icke-trivial beräkning omöjlig. Med tanke på detta låter vi noderna veta en övre gräns på den maximala grad som någonsin kommer att visas och visar att i detta fall noderna kan få en övre gräns på n. Slutligen, vi ersätter bred- på Detta arbete har delvis fått stöd av EU (Europeiska socialfonden - ESF) och grekiska nationella medel genom det operativa programmet "Utbildning och livslångt lärande" (EdLLL), under rubriken "Foundations of Dynamic Distributed Computing Systems" (FOCUS). gjuten med en-till-varje, där en nod kan skicka ett annat budskap till var och en av sina grannar. Intressant nog har denna naturliga variation visat sig vara beräkningsmässigt likvärdig med en full-kunskap modell, där unika namn finns och storleken på nätverket är känd.
En Counting protokoll för Anonym Dynamic Networks där en övre gräns på maximal grad är känd presenterades i REF.
Naming and Counting in Anonymous Unknown Dynamic Networks
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}