---
_id: '223'
abstract:
- lang: eng
text: We consider the problem of aggregation in overlay networks. We use a synchronous
time model in which each node has polylogarithmic memory and can send at most
a polylogarithmic number of messages per round. We investigate how to quickly
compute the result of an aggregate functionf over elements that are distributed
among the nodes of the network such that the result is eventually known by a selected
root node. We show how to compute distributive aggregate functions such as SUM,
MAX, and OR in time $O(\log n / \log\log n)$ using a tree that is created in a
pre-processing phase. If only a polylogarithmic number of data items need to be
aggregated, we show how to compute the result in time $O(\sqrt{\log n / \log\log
n})$. Furthermore, we show how to compute holistic aggregate functions such as
DISTINCT, SMALLEST(k) and MODE(k) in time $O(\log n / \log\log n)$. Finally, we
show a lower bound of $\Omega(\sqrt{\log n / \log\log n})$ for deterministic algorithms
that compute any of the aggregate functions in the scope of the thesis.
accept: '1'
author:
- first_name: Kristian
full_name: Hinnenthal, Kristian
id: '32229'
last_name: Hinnenthal
citation:
ama: Hinnenthal K. *Aggregation in Overlay Networks*. Universität Paderborn;
2016.
apa: Hinnenthal, K. (2016). *Aggregation in Overlay Networks*. Universität
Paderborn.
bibtex: '@book{Hinnenthal_2016, title={Aggregation in Overlay Networks}, publisher={Universität
Paderborn}, author={Hinnenthal, Kristian}, year={2016} }'
chicago: Hinnenthal, Kristian. *Aggregation in Overlay Networks*. Universität
Paderborn, 2016.
ieee: K. Hinnenthal, *Aggregation in Overlay Networks*. Universität Paderborn,
2016.
mla: Hinnenthal, Kristian. *Aggregation in Overlay Networks*. Universität Paderborn,
2016.
short: K. Hinnenthal, Aggregation in Overlay Networks, Universität Paderborn, 2016.
date_created: 2017-10-17T12:41:35Z
date_updated: 2019-01-03T13:12:59Z
ddc:
- '040'
department:
- _id: '79'
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-21T10:35:39Z
date_updated: 2018-03-21T10:35:39Z
file_id: '1510'
file_name: 223-MasterarbeitHinnenthal.pdf
file_size: 1127144
open_access: 1
relation: main_file
success: 1
file_date_updated: 2018-03-21T10:35:39Z
language:
- iso: eng
project:
- _id: '1'
name: SFB 901
- _id: '13'
name: SFB 901 - Subprojekt C1
- _id: '4'
name: SFB 901 - Project Area C
publisher: Universität Paderborn
status: public
supervisor:
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
title: Aggregation in Overlay Networks
type: mastersthesis
user_id: '15504'
year: '2016'
...