A distributed resource allocation algorithm for many processes

DOI10.1007/S00236-013-0181-7MaRDI QIDQ378202zbMATH OpenOpenAlexFDO

Authors W. H. Hesselink

Publication date 11 November 2013

Published in Acta Informatica (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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

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.

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

Cites work

• scientific article; zbMATH DE number 1639446 (Why is no real title available?)
• scientific article; zbMATH DE number 996442 (Why is no real title available?)
• scientific article; zbMATH DE number 4039251 (Why is no real title available?)
• A modular algorithm for resource allocation
• A modular drinking philosophers algorithm
• A new solution of Dijkstra's concurrent programming problem
• Splitting forward simulations to cope with liveness
• Stabilizing mobile philosophers
• The existence of refinement mappings
• Upper bounds for static resource allocation in a distributed system

Cited in

(8)

• Resource allocation via message passing
• scientific article; zbMATH DE number 3928336 (Why is no real title available?)
• 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
• scientific article; zbMATH DE number 3874587 (Why is no real title available?)
• An algorithm for dynamic data allocation in distributed systems

Describes a project that uses

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)