Vi studerar konvergenshastigheten för distribuerade iterativa algoritmer för samförstånd och genomsnittliga problem, med betoning på de senare. Vi betraktar först fallet med en fast kommunikationstopologi. Vi visar att en enkel anpassning av en konsensusalgoritm leder till en genomsnittsalgoritm. Vi bevisar lägre gränser på den värsta konvergenstiden för olika klasser av linjära, tidsinvarianta, distribuerade konsensusmetoder, och ger en algoritm som i huvudsak matchar dessa lägre gränser. Vi betraktar sedan fallet med en tidsvarierande topologi, och ger en polynom-tid genomsnittsalgoritm.
Olsjevsky och Tsitsiklis REF gav lägre gränser på den värsta konvergenstiden för många olika typer av linjära, tidsinvarianta, distribuerade konsensusalgoritmer.
Convergence speed in distributed consensus and averaging
{'venue': 'IN PROC. OF THE 45TH IEEE CDC', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}