I detta dokument studeras komplexiteten i den distribuerade konstruktionen av rent additiva skiftnycklar i CONGEST-modellen. Vi beskriver algoritmer för att bygga sådana skiftnycklar i flera fall. På grund av behovet av att samtidigt fatta beslut på långt skilda platser använder algoritmerna ytterligare mekanismer jämfört med sina sekventiella motsvarigheter. Vi kompletterar våra algoritmer med en lägre gräns för antalet rundor som krävs för att beräkna parvisa skiftnycklar. Standardnedskärningarna från set-dislectionness och jämlikhet verkar olämpliga för denna uppgift eftersom ingen specifik kant behöver tas bort från diagrammet. För att få vår lägre gräns definierar vi istället ett nytt kommunikationskomplex problem som minskar till att beräkna en gles skiftnyckel och visar sig vara en lägre gräns för dess kommunikationskomplexitet. Denna teknik utökar avsevärt den nuvarande verktygslådan som används för att erhålla
Flera lägre gränser för tids komplexiteten av skiftnyckelkonstruktion i den överbelastade modellen där presenteras i REF, men dessa är endast tillämpliga på parvis skiftnycklar med ett begränsat antal par, och inte för alla-par skiftnycklar.
Distributed construction of purely additive spanners
{'venue': 'Distributed Computing', 'journal': 'Distributed Computing', 'mag_field_of_study': ['Mathematics', 'Computer Science', 'Engineering']}