research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Incollection
Entered by:
TitleDistributed Algorithm Engineering
Bibtex cite IDRACTI-RU1-2002-19
Booktitle Experimental Algorithmics -- From Algorithm Design to Robust and Efficient Software
Year published 2002
Pages 197-228
Chapter 10
Publisher Springer-Verlag
When one engineers distributed algorithms, some special characteristics arise that are different from conventional (sequential or parallel) computing paradigms. These characteristics include: the need for either a scalable real network environment or a platform supporting a simulated distributed environment; the need to incorporate asynchrony, where arbitrarya synchrony is hard, if not impossible, to implement; and the generation of “difficult” input instances which is a particular challenge. In this work, we identifys ome of the methodological issues required to address the above characteristics in distributed algorithm engineering and illustrate certain approaches to tackle them via case studies. Our discussion begins byad dressing the need of a simulation environment and how asynchronyis incorporated when experimenting with distributed algorithms. We then proceed bys uggesting two methods for generating difficult input instances for distributed experiments, namelya game-theoretic one and another based on simulations of adversarial arguments or lower bound proofs. We give examples of the experimental analysis of a pursuit-evasion protocol and of a shared memorypro blem in order to demonstrate these ideas. We then address a particularlyi nteresting case of conducting experiments with algorithms for mobile computing and tackle the important issue of motion of processes in this context. We discuss the two-tier principle as well as a concurrent random walks approach on an explicit representation of motions in ad-hoc mobile networks, which allow at least for averagecase analysis and measurements and may give worst-case inputs in some cases. Finally, we discuss a useful interplay between theory and practice that arise in modeling attack propagation in networks.
Spirakis, Paul
Zaroliagis, Christos
J19-dist-alg-eng.pdf (main file)
Publication ID320