Στις ημέρες μας, η εμφάνιση των ασύρματων δικτύων σε πολλές πτυχές της καθημερινότητας, είναι συνεχώς αυξανομενη. Το γεγονός αυτό, έχει ως συνέπεια να υπάρχει μεγάλη ερευνητική δραστηριότητα γύρω από τα ασύρματα δίκτυα, η οποία αφορά όχι μόνο το σχεδιασμό τους και την ανάπτυξη διάφορων πρωτοκόλλων, αλλά και άλλες εφαρμογές, όπως είναι για παράδειγμα η εκτίμηση παραμέτρων. Στα πλαίσια της εργασίας αυτής, μελετάται η ανάπτυξη των αλγορίθμων φλυαρίας, οι οποίοι αφορούν μία κατανεμημένη προσέγγιση του προβλήματος της εκτίμησης παραμέτρων σε ένα δίκτυο. Πιο συγκεκριμένα, σε αντίθεση με τις κλασσικές μεθόδους στις οποίες αναλαμβάνει ένας κεντρικός κόμβος με μεγάλη υπολογιστική ισχύ να λύσει το πρόβλημα της εκτίμησης της παραμέτρου ενδιαφέροντος, με τους αλγόριθμους φλυαρίας αναιρείται η έννοια του κεντρικού κόμβου και η εκτίμηση στηρίζεται στη συνεχή ανταλλαγή πληροφοριών μεταξύ των κόμβων του δικτύου. Με τις προσομοιώσεις που έγιναν στα πλαίσια αυτής της εργασίας, αποδεικνύεται ότι οι εν λόγω αλγόριθμοι εξασφαλίζουν επιτυχημένη προσέγγιση του προβλήματος που καλούνται να επιλύσουν παρότι οι αλγόριθμοι φλυαρίας στηρίζονται σε υποβέλτιστες τεχνικές εκτίμησης παραμέτρων οι οποίες βασίζονται σε αναδρομικούς προσαρμοστικούς αλγορίθμους. Τέλος, αντιμετωπίζεται το πρόβλημα της εκτίμησης της θέσης ενός στόχου που κινείται στην περιοχή ενός δικτύου με βάση τη διαδικασία της φλυαρίας. / In recent years, the emergence of wireless networks in many aspects of daily life, is increasingly growing. This fact has as consequence a strong research activity around various types of wireless networks, not only in the design and development of various protocols, but also in other applications such as parameter estimation. In this thesis, we study the development of gossip algorithms that are related to a distributed approach to the problem of parameter estimation in a network. More specifically, in contrast with classical methods that assume a central node with high computational power to solve the problem of estimation of the parameter of interest, the use of gossip algorithms negates this concept and the estimation process is based on continuing exchange of information between network nodes. Additionally, despite the fact that gossip algorithms belong to suboptimal parameter estimation techniques, that are based on recursive adaptive algorithms, the simulation results presented show that these algorithms ensure successful approach to the problem they have to solve. Finally, the process of gossiping deals with the problem of estimating the position of a moving target in the region of a wireless network.

Recent years have seen a sharp increase in the ubiquity and power of connected devices, such as smartphones, smart appliances and smart sensors. These de- vices produce large amounts of data that can be extremely precious for training larger, more advanced machine learning models. Unfortunately, it is some- times not possible to collect and process these datasets on a central system, due either to their size or to the growing privacy requirements of digital data handling.To overcome this limit, researchers developed protocols to train global models in a decentralised fashion, exploiting the computational power of these edge devices. These protocols do not require any of the data on the device to be shared, relying instead on communicating partially-trained models.Unfortunately, real-world systems are notoriously hard to control, and may present a wide range of challenges that are easily overlooked in academic stud- ies and simulations. This research analyses the gossip learning protocol, one of the main results in the area of decentralised machine learning, to assess its applicability to real-world scenarios.Specifically, this work identifies the main assumptions built into the pro- tocol, and performs carefully-crafted simulations in order to test its behaviour when these assumptions are lifted. The results show that the protocol can al- ready be applied to certain environments, but that it fails when exposed to certain conditions that appear in some real-world scenarios. In particular, the models trained by the protocol may be biased towards the data stored in nodes with faster communication speeds or a higher number of neighbours. Further- more, certain communication topologies can have a strong negative impact on the convergence speed of the models.While this study also suggests effective mitigations for some of these is- sues, it appears that the gossip learning protocol requires further research ef- forts, in order to ensure a wider industrial applicability. / Under de senaste åren har vi sett en kraftig ökning av närvaron och kraften hos anslutna enheter, såsom smartphones, smarta hushållsmaskiner, och smarta sensorer. Dessa enheter producerar stora mängder data som kan vara extremt värdefulla för att träna stora och avancerade maskininlärningsmodeller. Dessvärre är det ibland inte möjligt att samla in och bearbeta dessa dataset på ett centralt system, detta på grund av deras storlek eller de växande sekretesskraven för digital datahantering.För att lösa problemet har forskare utvecklar protokoller för att träna globala modeller på ett decentraliserat sätt och utnyttja beräkningsförmågan hos dessa enheter. Dessa protokoll kräver inte datan på enheter delas utan förlitar sig istället på att kommunicera delvis tränade modeller.Dessvärre så är verkliga system svåra att kontrollera och kan presentera ett brett spektrum av utmaningar som lätt överskådas i akademiska studier och simuleringar. Denna forskning analyserar gossip inlärning protokollet vilket är av de viktigaste resultaten inom decentraliserad maskininlärning, för att bedöma dess tillämplighet på verkliga scenarier.Detta arbete identifierar de huvudsakliga antagandena om protokollet och utför noggrant utformade simuleringar för att testa protokollets beteende när dessa antaganden tas bort. Resultaten visar att protokollet redan kan tillämpas i vissa miljöer, men att det misslyckas när det utsätts för vissa förhållanden som i verklighetsbaserade scenarier. Mer specifikt så kan modellerna som utbildas av protokollet vara partiska och fördelaktiga mot data lagrade i noder med snabbare kommunikationshastigheter eller ett högre antal grannar. Vidare kan vissa kommunikationstopologier få en stark negativ inverkan på modellernas konvergenshastighet.Även om denna studie kom fram till en förmildrande effekt för vissa av dessa problem så verkar det som om gossip inlärning protokollet kräver ytterligare forskningsinsatser för att säkerställa en bredare industriell tillämplighet.

Τα τελευταία χρόνια έχουν γίνει σημαντικές προσπάθειες o Πληροφορικός-Επιστήμονας των Υπολογισμών να εκθέσει με εύληπτο τρόπο τη γνώση και εμπειρία του στις κοινότητες εκείνων που θέλουν να κάνουν υπολογισμούς. Κάτι τέτοιο έχει καταστεί δυνατό με την κατασκευή σύνθετων στη δομή, αλλά εύκολων στη χρήση, εργαλείων-περιβαλλόντων υπολογισμού στα οποία κανείς μπορεί με εντελώς φυσικό τρόπο να προδιαγράψει το πρόβλημά του και -ανάλογα με την εμπειρία του- να επέμβει στη ροή επίλυσής του. Τα Περιβάλλοντα Επίλυσης Προβλημάτων (ΠΕΠ) προβάλλουν λοιπόν ως μια πολύ ελκυστική λύση για τον επιστήμονα των εφαρμογών που αναζητεί μια εύχρηστη, ισχυρή και αξιόπιστη πλατφόρμα λογισμικού για τους υπολογισμούς του. Σε πολλές περιπτώσεις αυτοί οι υπολογισμοί είναι πολύ μεγάλης κλίμακας και απαιτούν πολυάριθμους και αποδοτικούς πόρους. Η τιθάσευσή τους σε κάποια έκταση έγινε δυνατή με τη στροφή σε παράλληλες-κατανεμημένες αρχιτεκτονικές, πρόσφατα μεγάλης κλίμακας, με έμφαση στην ευχρηστία, στην ασφάλεια πρόσβασης και στη συνεργατικότητα (Πλέγμα (Grid)). Σε άλλες περιπτώσεις οι πολυπύρηνοι επεξεργαστές που εξοπλίζουν πλέον τους τυπικούς οικιακούς υπολογιστές μας και οι προβλέψεις για αθρόα κλιμάκωση του αριθμού των προσφερόμενων πυρήνων, προτρέπουν σε επαναδιαπραγμάτευση κλασικών αλγορίθμων με στόχευση στην εξαγωγή παραλληλίας, αφού πλέον αυτή μπορεί να απεικονιστεί άμεσα στο διαθέσιμο υλικό. Επιπρόσθετα μια τέτοια στροφή ώθησε και τη διερεύνηση εναλλακτικών μοντέλων υπολογισμού: Το ασύγχρονο μοντέλο υπολογισμού προσφέροντας τη δυνατότητα για εξάλειψη των χρονοβόρων φάσεων συγχρονισμού των πολλαπλών μονάδων επεξεργασίας προβάλλει ως μια ενδιαφέρουσα επιλογή. Συστηματοποιούμε τη μελέτη των Περιβαλλόντων Επίλυσης Προβλημάτων (ΠΕΠ) εντοπίζοντας τους άξονες που χαρακτηρίζουν αυτήν την κατηγορία συστημάτων λογισμικού και υλοποιώντας το Jylab, ένα πρωτότυπο ΠΕΠ με έμφαση στη φορητότητα, την επαναχρησιμοποίηση ελεύθερα διαθέσιμου κώδικα και τη δυνατότητα για ακολουθιακό, παράλληλο και κατανεμημένο υπολογισμό σε πολλαπλές πλατφόρμες. Ειδικότερα, το Jylab περιλαμβάνει υποστήριξη για ασύγχρονο κατανεμημένο υπολογισμό, ανάλυση ιστογραφημάτων και εκτέλεση υπολογισμών στο Πλέγμα (Grid). Αμέσως μετά εισάγουμε το ασύγχρονο μοντέλο υπολογισμού εστιάζοντας σε καίρια ζητήματα όπως η ανάλυση της σύγκλισης, η ανίχνευση του τερματισμού και η υλοποίησή του. Προτείνουμε πιθανοτικό πλαίσιο εντοπισμού της σύγκλισης και διερευνούμε την πολυπλοκότητα του μοντέλου. Στη συνέχεια μελετούμε αλγορίθμους διάταξης των κόμβων ενός γραφήματος, επικεντρώνοντας στον υπολογισμό του διανύσματος του PageRank το οποίο χρησιμοποιεί η Google για να διατάξει τα αποτελέσματα μιας ερώτησης που υποβάλλουμε στη μηχανή αναζήτησής της. Αποδεικνύουμε πως και άλλες μέθοδοι διάταξης, οι οποίες εκφράζονται πρωταρχικά ως δυναμοσειρές ενός τροποποιημένου μητρώου συνδέσμων μπορούν να γραφτούν ως γινόμενα των επαναληπτικών μητρώων που χρησιμοποιούνται στον υπολογισμό του διανύσματος PageRank, αλλά με διαφορετική παράμετρο σε κάθε όρο τους (μέθοδος της πολυπαραμετρικής απόσβεσης). Στη συνέχεια εκθέτουμε την πειραματική συμπεριφορά του ασύγχρονου μοντέλου, όπως αυτή προκύπτει από υλοποιήσεις κυρίως του αλγορίθμου του PageRank, σε διάφορες πλατφόρμες (τοπικά, στη συστάδα υπολογισμών και στο Πλέγμα (Grid)) και με μονάδες εκτέλεσης νήματα ή διεργασίες. To Jylab χρησιμοποιήθηκε εντατικά σε αυτές τις διερευνήσεις και αποδείχτηκε πως όλοι οι πειραματισμοί μπορούν να τεθούν κάτω από ενιαίο πλαίσιο λογισμικού. Επίσης εισάγουμε μια κλάση αλγορίθμων κατανεμημένου υπολογισμού στατιστικών μεγεθών, τους gossip αλγορίθμους, σε κάθε στοιχειώδες βήμα των οποίων μόνο δύο οντότητες επικοινωνούν και υπολογίζουν. Επεκτείνουμε αυτούς τους αλγορίθμους επιτρέποντας σε k > 2 οντότητες να αλληλεπιδρούν ανά βήμα, προσομοιώνουμε τη συμπεριφορά τους και προτείνουμε πρωτόκολλα υλοποίησής τους. / In recent years computational scientists strive to expose their knowledge and experience to the communities of people interested in performing computations. This endeavor focuses on the construction of complex in structure, however simple in use, toolchains and environments in which a researcher can specify his or her problem and - depending on his experience - change its exact solution flow. In many cases these computations necessitate large-scale and performant resources. Harnessing them, to some extent, became possible by turning to parallel-distributed architectures, recently of large scale, emphasizing usability, security in accessing them and collaboration perspectives (Grid). In other cases, the multicore processors, nowadays powering even typical personal computers, coupled with predictions for dramatic increase in the number of available cores in the near future, suggest a reconsideration of classic algorithms aiming at extracting parallelism, since this can be directly mapped to underlying hardware. Additionally, such a move, also fuels the investigation of alternative computation models: The asynchronous computation model, offering the flexibility for the complete removal of time-consuming synchronization phases, is a very interesting option. We study Problem Solving Environments (PSEs) in a systematic manner, specifying the axes characterizing this category of systems of software also implementing Jylab, a prototype PSE emphasizing portability and the reuse of freely available code and enabling sequential, parallel and distributed computing over multiple platforms. More specifically, Jylab includes support for asynchronous distributed computations, Web graph analysis and Grid computing. Then we introduce the asynchronous computation model, focusing in three core subjects, namely its convergence analysis, the termination detection problem and its implementation. We propose a probabilistic framework for convergence detection and explore the complexity of the model. Afterwards, we survey algorithms for ranking the nodes of a graph, focusing on computing the PageRank vector, which is used by Google for ranking the results of a query submitted to its search engine. We prove that a whole class of ranking methods, primarily expressed as a power series of a modified link matrix can be written as products of iterative matrices similar to those used in computing the PageRank vector, albeit with a different damping parameter for each of its terms (multidamping). Next, we present the experimental behavior of the asynchronous model, mainly as applied in computing the PageRank vector, over different platforms (locally, in a computer cluster and over the Grid) using either threads or processes as its units of execution. Jylab was intensively used in these investigations and it was proved that all experimentations can be cast under a unifying software framework. We also introduce a class of algorithms for the distributed computation of statistical quantities, namely gossip algorithms, for which only two entities communicate and compute at each elementary step. We extend these algorithms be permitting k > 2 entities to interact on a per elementary step basis, simulate their behavior and propose protocols for implementing them.