Weak models of wireless distributed computing Comparison between radio networks and population protocols

Thumbnail Image

Files

master_Tong_Alvarez_Marcos_2016.pdf (1.17 MB)

URL

Journal Title

Journal ISSN

Volume Title

Perustieteiden korkeakoulu | Master's thesis
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.

Authors

Date

2016-08-24

Department

Major/Subject

Foundations of Advanced Computing

Mcode

SCI3014

Degree programme

Master’s Programme in Foundations of Advanced Computing (FAdCo)

Language

en

Pages

112

Series

Abstract

This thesis compares weak distributed computing models that are suit- able for extremely limited wireless networks. The comparison is mainly between multiple variations of radio networks and population protocols. The analysis is based on model features, computability and algorithmic complexity. The thesis analyses essential and optional model features, and organizes the models accordingly. It discusses the applicability of results from stronger models to radio network models, including impossibility results, algorithms and their runtime. It analyzes different radio network algorithms for the classical problems in terms of their features, and it discusses their applicability to other radio network models. It reviews the fundamental differences between population protocols and radio networks. Lastly, the comparative analysis summarizes fundamental differences and separating features.

Description

Supervisor

Suomela, Jukka

Thesis advisor

Martinez, Remberto

Keywords

theory of computing, distributed algorithms, computational complexity, weak models, radio networks, population protocols

Other note

Citation

Permanent link to this item

https://urn.fi/URN:NBN:fi:aalto-201608263085

Collections

[dipl] Perustieteiden korkeakoulu / SCI