Multi-Resource Allocation Strategies for Unknown Participants

multi resource allocation with unknown n.w
1 / 33
Embed
Share

Explore various resource allocation models and strategies designed for scenarios where clients do not know each other, focusing on safety, liveness, and exclusion criteria. Discusses K-resource allocation, asynchronous message passing, and deadlock issues. Related work on peer-to-peer systems and drinking philosophers application also examined. Presented at PDAA'2011 in Osaka.

  • Resource Allocation
  • Unknown Participants
  • Multi-Resource
  • Peer-to-Peer
  • Asynchronous
rayaanacharya
caee174 Follow

Uploaded on | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

Download Presentation

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

E N D

Presentation Transcript

  1. Multi-resource Allocation with Unknown Participants Ajoy K. Datta, St phane Devismes, Fran ois Kawala, Lawrence L. Larmore, and Maria Potop-Butucaru

  2. K-resource Allocation C1 N >> M C2 R1 C3 R2 C4 C5 RM C6 Resources CN December 2, 2011 Clients PDAA'2011, Osaka

  3. K-resource Allocation C1 N >> M C2 R1 Clients don t know each other C3 R2 C4 C5 RM C6 Resources CN December 2, 2011 Clients PDAA'2011, Osaka

  4. K-resource Allocation C1 R1,R2 N >> M C2 R1 Clients don t know each other C3 R1,R3 R2 C4 Request: up to K resources R4 C5 Clients only know the IDs of the resource they request RM C6 R2, R6,R7 Resources Request given by an oracle CN December 2, 2011 Clients PDAA'2011, Osaka

  5. K-resource Allocation C1 R1,R2 C2 R1 C3 R1,R3 R2 C4 R4 C5 RM C6 R2, R6,R7 Resources SAFETY: Each resource is used by at most one client at a time CN December 2, 2011 Clients PDAA'2011, Osaka

  6. K-resource Allocation C1 R1,R2 C2 R1 C3 R1,R3 R2 LIVENESS: Every request is eventually satisfied C4 R4 C5 RM C6 R2, R6,R7 Resources CN December 2, 2011 Clients PDAA'2011, Osaka

  7. Related Work K-out-of-L Exclusion Drinking philosophers Application: Peer-to-Peer systems December 2, 2011 PDAA'2011, Osaka

  8. Model Asynchronous message passing Reliable link Any client can only communicate with the resources it requests December 2, 2011 PDAA'2011, Osaka

  9. 2-Resource Allocation Overview Queues At each resource To store client s requests The request at head of the queue is satisfied Issue Deadlock C2 C1 C3 R5 December 2, 2011 PDAA'2011, Osaka

  10. 2-Resource Allocation C1 C2 R1 C3 R2 R3 December 2, 2011 PDAA'2011, Osaka

  11. Deadlock C1 C2 C1 C2 R1 C3 C2 C3 C1 C3 R2 R3 December 2, 2011 PDAA'2011, Osaka

  12. Our solution First request: strong (Second request: weak) Two queues per resource: strong, weak Resource allocated to the head of its strong queue Weak requests move from weak to strong queue Under some conditions December 2, 2011 PDAA'2011, Osaka

  13. Our solution R1 C1 C1,R1,Weak R2 December 2, 2011 PDAA'2011, Osaka

  14. Our solution R1 C1 C1,R2,Strong C1 R2 December 2, 2011 PDAA'2011, Osaka

  15. Our solution C1 R1 C1 C1 R2 December 2, 2011 PDAA'2011, Osaka

  16. Our solution C1 StrongReady R1 C1 C1 R2 December 2, 2011 PDAA'2011, Osaka

  17. Our solution C1 R1 C1 C1 R2 December 2, 2011 PDAA'2011, Osaka

  18. Our solution C1 R1 C1 C1 ResAllowed R2 December 2, 2011 PDAA'2011, Osaka

  19. Our solution C1 R1 CS C1 C1 R2 December 2, 2011 PDAA'2011, Osaka

  20. Our solution C1 R1 C1 Done C1 R2 December 2, 2011 PDAA'2011, Osaka

  21. Our solution C1 R1 C1 Done R2 December 2, 2011 PDAA'2011, Osaka

  22. Our solution EndAck R1 C1 R2 December 2, 2011 PDAA'2011, Osaka

  23. Deadlock C3 C2 C1 C2 C1 C3 R1 R2 R3 December 2, 2011 PDAA'2011, Osaka

  24. Deadlock C2 C1 C3 C2 C1 C3 R1 R2 R3 December 2, 2011 PDAA'2011, Osaka

  25. Dependancy Cycle C2 C1 C3 C2 C1 C3 R1 R2 R3 December 2, 2011 PDAA'2011, Osaka

  26. Conflict Resolution Dependency cycle detection A message follows the dependencies Dependency cycle breaking A dependency is broken A client s request is penalized December 2, 2011 PDAA'2011, Osaka

  27. Fairness Penalization must be fair Identifiers cannot be used We use a token circulating on the resource ring December 2, 2011 PDAA'2011, Osaka

  28. Token (1/2) Token reception The resource marks all its strong requests Token releasing When all marked request have been satisfied Forwarded to the next resource in the ring Each resource gets the token infinitely often December 2, 2011 PDAA'2011, Osaka

  29. Token (2/2) Token holder never penalized Penalized dependency: the one out-coming from the smallest non token holder The token holder flushes its old requests before releasing the token December 2, 2011 PDAA'2011, Osaka

  30. Dynamicity Join New identity Leave With announcement: easy Crash Need a participant detector December 2, 2011 PDAA'2011, Osaka

  31. Participant Detector Required : Perfect [Fetzer,2003] Strong completeness: Every client that leaves tge system is eventually removed from the participant lists Strong accuracy: No client can be removed from a list before it leaves the system December 2, 2011 PDAA'2011, Osaka

  32. K > 2 Generalized the previous solution: hard Pessimistic approach: prevent deadlock creation Resource allocated sequentially Not efficient (not enough concurrency) Hybrid solution ? December 2, 2011 PDAA'2011, Osaka

  33. Thank you December 2, 2011 PDAA'2011, Osaka

Related


No related presentations.

More Related Content