I detta arbete överväger vi en lösning av automata (eller noder) som rör sig passivt i en väl blandad lösning utan att kunna styra sin rörelse. Noder kan samarbeta genom att interagera i par och varje sådan interaktion kan resultera i en uppdatering av deras lokala stater. Dessutom kan noderna också välja att ansluta till varandra för att börja bilda någon nödvändig struktur. Sådana noder kan betraktas som små programmerbara bitar av materia, som små nanorobotar eller programmerbara molekyler. Den modell som vi introducerar här är en mer tillämpad version av nätverksbyggare, vilket innebär fysiska (eller geometriska) begränsningar på de anslutningar som noderna får bilda. Varje nod kan ansluta till andra noder endast via ett mycket begränsat antal lokala portar. Anslutningar görs alltid på enhet avstånd och är vinkelräta mot anslutningar till angränsande portar, vilket gör att modellen kan bilda 2D eller 3D-former. Vi tillhandahåller direkta konstruktörer för några grundläggande form konstruktion problem, som spännvidd linje, spännvidd fyrkant, och själveplikering. Vi utvecklar sedan nya tekniker för att bestämma vår modells beräknings- och konstruktiva kapacitet. En av de viktigaste nyheterna i vår strategi är att utnyttja antagandena att systemet är väl blandat och har en unik ledare, för att ge avslutande protokoll som är korrekta med stor sannolikhet. Detta gör det möjligt för oss att utveckla terminerande subrutiner som kan komponeras sekventiellt för att bilda större modulära protokoll. Ett av våra viktigaste resultat är ett avslutande protokoll som räknar storleken n av systemet med hög sannolikhet. Vi använder sedan detta protokoll som en subrutin för att utveckla våra universella konstruktörer, etablera att det är möjligt för noderna att bli självorganiserade med hög sannolikhet till godtyckligt komplexa former samtidigt som det fortfarande upptäcker avslutande av konstruktionen.
Ett annat aktuellt exempel utnyttjar en förvald ledare för att räkna storleken på befolkningen genom ett protokoll som alltid avslutas och är korrekt med hög sannolikhet REF.
Terminating distributed construction of shapes and patterns in a fair solution of automata
{'venue': 'Distributed Computing', 'journal': 'Distributed Computing', 'mag_field_of_study': ['Engineering', 'Computer Science']}