Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor

Author(s):

Doerr, Benjamin
Friedrich, Tobias

dblp
dblp



Editor(s):

Asano, Tetsuo

dblp

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

URL of the conference:

http://www.isical.ac.in/~isaac06/

URL for downloading the paper:

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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
2006ISAAC.pdf