VICINITY: A pinch of randomness brings out the structure

Spyros Voulgaris, Maarten van Steen

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

16 Citations (Scopus)


Overlay networks are central to the operation of large-scale decentralized applications, be it Internet-scale P2P systems deployed in the wild or cloud applications running in a controlled - albeit large-scale - environment. A number of custom solutions exist for individual applications, each employing a tailor-made mechanism to build and maintain its specific structure. This paper addresses the role of randomness in developing and maintaining such structures. Taking VICINITY, a generic overlay management framework based on self-organization, we explore tradeoffs between deterministic and probabilistic decision-making for structuring overlays. We come to the conclusion that a pinch of randomness may even be needed in overlay construction, but also that much randomness or randomness alone is not good either.

Original languageEnglish
Title of host publicationMiddleware 2013
Subtitle of host publicationACM/IFIP/USENIX 14th International Middleware Conference, Beijing, China, December 9-13, 2013, Proceedings
EditorsDavid Eyers, Karsten Schwan
Place of PublicationBerlin, Heidelberg
Number of pages20
ISBN (Electronic)978-3-642-45065-5
ISBN (Print)978-3-642-45064-8
Publication statusPublished - 1 Dec 2013
Externally publishedYes
Event14th ACM/IFIP/USENIX Middleware Conference, Middleware 2013 - Beijing, China
Duration: 9 Dec 201313 Dec 2013
Conference number: 14

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference14th ACM/IFIP/USENIX Middleware Conference, Middleware 2013


  • Selection function
  • Network size
  • Garbage collection
  • Torus topology
  • Baseline version


Dive into the research topics of 'VICINITY: A pinch of randomness brings out the structure'. Together they form a unique fingerprint.

Cite this