MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Doerr, Benjamin
Friedrich, Tobias
dblp
dblp
Editor(s):
Asano, Tetsuodblp
Not MPII Editor(s):
Asano, Tetsuo
BibTeX cite key*:
DF2006
Title, Booktitle
Title*:
Deterministic Random Walks on the Two-Dimensional Grid
2006ISAAC.pdf (122.6 KB)
Booktitle*:
Algorithms and Computation : 17th International Symposium, ISAAC 2006
Event, URLs
Conference URL::
http://www.isical.ac.in/~isaac06/
Downloading URL:
http://www.mpi-inf.mpg.de/~tfried/paper/2006ISAAC.pdf
http://www.springerlink.com/content/ll72t6x2v3444553/fulltext.pdf
Event Address*:
Kolkata, India
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
18 December 2006
Event End Date:
20 December 2006
Publisher
Name*:
Springer
URL:
http://www.springer.com/
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
4288
Number:
Month:
December
Pages:
474-483
Year*:
2006
VG Wort Pages:
28
ISBN/ISSN:
3-540-49694-6
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
Deterministic and randomized balancing schemes are used to distribute workload evenly in networks. In this paper, we compare two very general ones: The random walk and the (deterministic) Propp machine. Roughly speaking, we show that on the two-dimensional grid, the Propp machine always has the same number of tokens on a node as does the random walk in expectation, apart from an additive error of less than eight. This constant is independent of the total number of tokens and the runtime of the two processes. However, we also show that it makes a difference whether the Propp machine serves the neighbors in a circular or non-circular order.
URL for the Abstract:
http://www.springerlink.com/content/ll72t6x2v3444553/
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{DF2006,
AUTHOR = {Doerr, Benjamin and Friedrich, Tobias},
EDITOR = {Asano, Tetsuo},
TITLE = {Deterministic Random Walks on the Two-Dimensional Grid},
BOOKTITLE = {Algorithms and Computation : 17th International Symposium, ISAAC 2006},
PUBLISHER = {Springer},
YEAR = {2006},
VOLUME = {4288},
PAGES = {474--483},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {Kolkata, India},
MONTH = {December},
ISBN = {3-540-49694-6},
}


Entry last modified by Anja Becker, 03/02/2010
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Tobias Friedrich
Created
11/22/2006 02:10:03 PM
Revisions
8.
7.
6.
5.
4.
Editor(s)
Anja Becker
Uwe Brahm
Regina Kraemer
Christine Kiesel
Christine Kiesel
Edit Dates
25.02.2008 08:54:14
04/25/2007 10:35:25 AM
04/11/2007 11:07:04 AM
06.02.2007 14:44:35
12/08/2006 10:34:04 AM


File Attachment Icon
2006ISAAC.pdf