Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. The Driving Philosophers
 
conference paper

The Driving Philosophers

Baehni, S.
•
Baldoni, R.
•
Gerraoui, R.
Show more
2004
Proceedings of the 3rd IFIP International Conference on Theoretical Computer Science (TCS'04)

We introduce a new synchronization problem in mobile ad-hoc systems: the Driving Philosophers. In this problem, an unbounded number of driving philosophers (processes) access a round-about (set of shared resources organized along a logical ring). The crux of the problem is to ensure, beside traditional mutual exclusion and starvation freedom at each particular resource, gridlock freedom (i.e., a cyclic waiting chain among processes). The problem captures explicitly the very notion of process mobility and the underlying model does not involve any assumption on the total number of (participating) processes or the use of shared memory, i.e., the model conveys the ad-hoc environment. We present a generic algorithm that solves the problem in a synchronous model. Instances of this algorithm can be fair but not concurrent, or concurrent but not fair. We derive the impossibility of achieving fairness and concurrency at the same time as well as the impossibility of solving the problem in an asynchronous model. We also conjecture the impossibility of solving the problem in an ad-hoc network model with limited-range communication.

  • Files
  • Details
  • Metrics
Type
conference paper
DOI
10.1007/1-4020-8141-3_16
Web of Science ID

WOS:000227054700016

Author(s)
Baehni, S.
Baldoni, R.
Gerraoui, R.
Pochon, B.
Date Issued

2004

Published in
Proceedings of the 3rd IFIP International Conference on Theoretical Computer Science (TCS'04)
Subjects

NCCR-MICS

•

NCCR-MICS/CL4

Written at

EPFL

EPFL units
DCL  
Available on Infoscience
January 30, 2006
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/221787
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés