טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentAtsmonguz Liat
SubjectLocal Dynamic Weighted Matching
DepartmentDepartment of Electrical Engineering
Supervisor Professor Idit Keidar
Full Thesis textFull thesis text - English Version


Abstract

We define and solve the distributed dynamic weighted matching problem. Namely, unlike most previous work, we consider a scenario in which the network is asynchronous and dynamic, experiencing churn, failures, topology changes, and link weight changes. An algorithm that solves the dynamic weighted matching problem should adapt to such changes in the network and constantly output a matching.  We develop a new algorithm that solves this problem and guarantees a 2-approximation of the optimal solution. Moreover, we show that following local changes, the algorithm converges back to a 2-approximation after O(1) rounds.