טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentChen Jiaqi
SubjectReactive Proof Labeling Schemes for
Distributed Decision
DepartmentDepartment of Industrial Engineering and Management
Supervisors PROF. Shay Kutten
PROF. Shlomo Dolev
Full Thesis textFull thesis text - English Version


Abstract

We generalize the definition of Proof Labeling Schemes (PLS) to reactive systems, that is, systems where the configuration is supposed to keep changing forever. More specifically, we define and initiate the development of efficient Reactive Proof Labeling Schemes (RPLSs) tailored to specific tasks. As a test case, we address the main classical problem of self-stabilization -- token passing. Different RPLSs are given for the cases that the network is assumed to be a tree, or an anonymous ring, or a general graph, and the sizes of RPLSs' labels are analyzed. We also address the question of whether an RPLS exists. First, on the positive side, we show (following the local stabilzer approach of Afek and Dolev) that there exists a universal RPLS for any distributed task for a family of graphs with unique identities (although the size of the labels for the universal RPLS is relatively large). For the case of anonymous networks (even for the special case of rings), interestingly, it is known that no token passing algorithm is possible even if the number n of nodes is known. Nevertheless, we show that an RPLS is possible. On the negative side, we show that if one drops the assumption that n is known, then the construction becomes impossible.