טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentBonne Matthias
SubjectDistributed Detection of Cliques in Dynamics
Networks
DepartmentDepartment of Computer Science
Supervisor Professor Keren Censor-Hillel


Abstract

Real-world computer networks are dynamic in nature - nodes may join or leave the network at any time, and communication links may appear and disappear constantly. To study the capabilities of such networks, we use a dynamic variant of the CONGEST model of computer networks. In this model, a network is represented as an undirected graph, where each vertex is a computation unit, and each edge is a communication link. Since the network is dynamic, the graph may undergo certain changes during the network’s operation.


One of the fundamental problems in the CONGEST model - and in other models of distributed computer networks - is the detection of certain types of subgraphs in the network. In particular, the problem of detecting triangles and larger cliques has been extensively studied over the years.


This thesis provides an in-depth study of the problem of clique detection, and other related problems, in distributed dynamic networks. We show that different types of changes in the network have very different effects on the amount of resources required to solve many of these problems, and that some problems are fundamentally harder than others. We also show that, perhaps surprisingly, the amount of resources required to solve most of the problems is similar for triangles and for larger cliques.