Sinkroni mrežni algoritmi

master's thesis

• Author: Katarina Petrović
• Mentor: Robert Manger (mentor)
• Committee member: Robert Manger (predsjednik povjerenstva)
• Committee member: Mladen Vuković (član povjerenstva)
• Committee member: Goran Igaly (član povjerenstva)
• Committee member: Ivica Nakić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2020-02-28, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

Ovaj rad opisuje model sinkrone mreže i obrađuje tri sinkrona algoritma u općenitoj mreži, algoritam za izbor vođe, problem najkraćeg puta i maksimalni nezavisni skup. Nabrojani algoritmi služe u rješavaju problema izbora "vođe" u mrežnom računanju, za izgradnju struktura pogodnih za podršku učinkovite komunikacije, rješavanje problema mrežne alokacije resursa i slično. Nakon opisa i analize algoritama, slijedi njihova implementacija u asinkronoj mreži sa sinkronizatorom. U tu svrhu, korišteni su jednostavni sinkronizator i sinkronizator alpha, koji su prethodno opisani. Na kraju je na primjerima demonstriran rad algoritama u odsustvu sinkronizatora.

Abstract (english)

This thesis describes synchronous network model and addresses three algorithms in general synchronous network, leader election, shortest paths and maximal independent set. The above-mentioned algorithms are used to solve the problem of choosing a "leader" in network computing, to build a structure suitable for support communication, to solve the problem of network resource allocations, et cetera. After describing and analyzing the algorithms, they are implemented in asynchronous network model with synchronizer. For this purpose, simple synchronizer and alpha synchronizer were used and described previously. Finally, it is demonstrated on examples how algorithms work in the absence of a synchronizer.

• Keywords: model sinkrone mreže; algoritam za izbor vođe; problem najkraćeg puta; maksimalni nezavisni skup; sinkronizator
• Keywords (english): synchronous network model; leader election; shortest paths; maximal independent set; synchronizer
• Language: croatian
• URN:NBN: urn:nbn:hr:217:716523
• Study programme: Title: Computer Science and Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra računarstva i matematike (magistar/magistra računarstva i matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2020-10-07 09:18:41