A distributed resource allocation algorithm for many processes

DOI10.1007/S00236-013-0181-7zbMATH Open1362.68215arXiv1204.6170OpenAlexW2134926993MaRDI QIDQ378202FDOQ378202

Authors: W. H. Hesselink 

Publication date: 11 November 2013

Published in: Acta Informatica (Search for Journal in Brave)

Abstract: Resource allocation is the problem that a process may enter a critical section CS of its code only when its resource requirements are not in conflict with those of other processes in their critical sections. For each execution of CS, these requirements are given anew. In the resource requirements, levels can be distinguished, such as e.g. read access or write access. We allow infinitely many processes that communicate by reliable asynchronous messages and have finite memory. A simple starvation-free solution is presented. Processes only wait for one another when they have conflicting resource requirements. The correctness of the solution is argued with invariants and temporal logic. It has been verified with the proof assistant PVS.

Full work available at URL: https://arxiv.org/abs/1204.6170

Recommendations

• A modular algorithm for resource allocation
• scientific article; zbMATH DE number 3874587
• scientific article; zbMATH DE number 3928336
• Multiple instance resource allocation in distributed computing systems
• The mutual exclusion problem

Mathematics Subject Classification ID

Distributed algorithms (68W15) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• The existence of refinement mappings
• A modular algorithm for resource allocation
• A new solution of Dijkstra's concurrent programming problem
• Stabilizing mobile philosophers
• Upper bounds for static resource allocation in a distributed system
• A modular drinking philosophers algorithm
• Splitting forward simulations to cope with liveness
• Title not available (Why is that?)

Cited In (8)

• Title not available (Why is that?)
• Flow and greedy algorithms of resource co-allocation in distributed systems
• A distributed algorithm for parallel multi-task allocation based on profit sharing learning
• A modular algorithm for resource allocation
• Multiple instance resource allocation in distributed computing systems
• Title not available (Why is that?)
• An algorithm for dynamic data allocation in distributed systems
• Resource allocation via message passing

Uses Software

• SPIN

This page was built for publication: A distributed resource allocation algorithm for many processes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q378202)