An efficient failure-resilient mutual exclusion algorithm for distributed systems leveraging a novel zero-message overlay structure
<p>In this paper, we provide a novel failure-resilient token-based mutual exclusion (ME) algorithm for distributed systems. Like a few other solutions in the literature, the proposed solution leverages a logical tree as its underlying topology. However, unlike any other solution, the tree is b...
محفوظ في:
| المؤلف الرئيسي: | |
|---|---|
| مؤلفون آخرون: | |
| منشور في: |
2024
|
| الموضوعات: | |
| الوسوم: |
إضافة وسم
لا توجد وسوم, كن أول من يضع وسما على هذه التسجيلة!
|
| _version_ | 1864513520246194176 |
|---|---|
| author | Mouna Rabhi (17086969) |
| author2 | Roberto Di Pietro (16864155) |
| author2_role | author |
| author_facet | Mouna Rabhi (17086969) Roberto Di Pietro (16864155) |
| author_role | author |
| dc.creator.none.fl_str_mv | Mouna Rabhi (17086969) Roberto Di Pietro (16864155) |
| dc.date.none.fl_str_mv | 2024-03-15T03:00:00Z |
| dc.identifier.none.fl_str_mv | 10.1016/j.comcom.2024.02.007 |
| dc.relation.none.fl_str_mv | https://figshare.com/articles/journal_contribution/An_efficient_failure-resilient_mutual_exclusion_algorithm_for_distributed_systems_leveraging_a_novel_zero-message_overlay_structure/25434763 |
| dc.rights.none.fl_str_mv | CC BY 4.0 info:eu-repo/semantics/openAccess |
| dc.subject.none.fl_str_mv | Engineering Communications engineering Mutual exclusion Distributed systems Failure resilience Overly network Probabilistic protocols |
| dc.title.none.fl_str_mv | An efficient failure-resilient mutual exclusion algorithm for distributed systems leveraging a novel zero-message overlay structure |
| dc.type.none.fl_str_mv | Text Journal contribution info:eu-repo/semantics/publishedVersion text contribution to journal |
| description | <p>In this paper, we provide a novel failure-resilient token-based mutual exclusion (ME) algorithm for distributed systems. Like a few other solutions in the literature, the proposed solution leverages a logical tree as its underlying topology. However, unlike any other solution, the tree is built using a probabilistic, fully distributed approach, without exchanging messages. The current tree-based ME algorithms often overlook considerations for node/link failures or offer costly methods for failure recovery. The proposed algorithm overcomes these limitations by providing an effective solution to maintain a logarithmic cost in case of node failures. The overlay structure – a unique logical tree – used to control access to the critical section maintains its consistency even when nodes fail. An extensive simulation study demonstrates the viability and efficiency of the proposed algorithm under various node failure models, and relevant metrics (e.g., node queue dimension, number of exchanged messages, and number of disconnected nodes) indicate a graceful degradation in performance with decreasing number of functioning nodes. For instance, for 4,096 nodes organized in a logical tree of arity 4 and with 4 physical nodes for logical node, a negligible number of nodes is disconnected from the tree after 250 epochs when the per-node per-epoch failure probability is p f ≤ 0 . 0008 . With a p f = 0 . 0016 , less than 10% of the nodes are disconnected. The proposed algorithm avoids node disconnection while minimally impacting the load of the logical tree nodes. In addition, for the same architecture, when both tree arity and cardinality are 4, after 250 epochs, the node load has demonstrated minimal variation and remains in close proximity to the original load. Moreover, experimental results also reveal a graceful degradation of algorithm performance. The fully distributed solution, rich parametrization for different trade-offs, and viability and resilience of the proposed algorithm also pave the way for future research.</p><h2>Other Information</h2> <p> Published in: Computer Communications<br> License: <a href="http://creativecommons.org/licenses/by/4.0/" target="_blank">http://creativecommons.org/licenses/by/4.0/</a><br>See article on publisher's website: <a href="https://dx.doi.org/10.1016/j.comcom.2024.02.007" target="_blank">https://dx.doi.org/10.1016/j.comcom.2024.02.007</a></p> |
| eu_rights_str_mv | openAccess |
| id | Manara2_35b0a17f386552899e5a76af1c9c224d |
| identifier_str_mv | 10.1016/j.comcom.2024.02.007 |
| network_acronym_str | Manara2 |
| network_name_str | Manara2 |
| oai_identifier_str | oai:figshare.com:article/25434763 |
| publishDate | 2024 |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| rights_invalid_str_mv | CC BY 4.0 |
| spelling | An efficient failure-resilient mutual exclusion algorithm for distributed systems leveraging a novel zero-message overlay structureMouna Rabhi (17086969)Roberto Di Pietro (16864155)EngineeringCommunications engineeringMutual exclusionDistributed systemsFailure resilienceOverly networkProbabilistic protocols<p>In this paper, we provide a novel failure-resilient token-based mutual exclusion (ME) algorithm for distributed systems. Like a few other solutions in the literature, the proposed solution leverages a logical tree as its underlying topology. However, unlike any other solution, the tree is built using a probabilistic, fully distributed approach, without exchanging messages. The current tree-based ME algorithms often overlook considerations for node/link failures or offer costly methods for failure recovery. The proposed algorithm overcomes these limitations by providing an effective solution to maintain a logarithmic cost in case of node failures. The overlay structure – a unique logical tree – used to control access to the critical section maintains its consistency even when nodes fail. An extensive simulation study demonstrates the viability and efficiency of the proposed algorithm under various node failure models, and relevant metrics (e.g., node queue dimension, number of exchanged messages, and number of disconnected nodes) indicate a graceful degradation in performance with decreasing number of functioning nodes. For instance, for 4,096 nodes organized in a logical tree of arity 4 and with 4 physical nodes for logical node, a negligible number of nodes is disconnected from the tree after 250 epochs when the per-node per-epoch failure probability is p f ≤ 0 . 0008 . With a p f = 0 . 0016 , less than 10% of the nodes are disconnected. The proposed algorithm avoids node disconnection while minimally impacting the load of the logical tree nodes. In addition, for the same architecture, when both tree arity and cardinality are 4, after 250 epochs, the node load has demonstrated minimal variation and remains in close proximity to the original load. Moreover, experimental results also reveal a graceful degradation of algorithm performance. The fully distributed solution, rich parametrization for different trade-offs, and viability and resilience of the proposed algorithm also pave the way for future research.</p><h2>Other Information</h2> <p> Published in: Computer Communications<br> License: <a href="http://creativecommons.org/licenses/by/4.0/" target="_blank">http://creativecommons.org/licenses/by/4.0/</a><br>See article on publisher's website: <a href="https://dx.doi.org/10.1016/j.comcom.2024.02.007" target="_blank">https://dx.doi.org/10.1016/j.comcom.2024.02.007</a></p>2024-03-15T03:00:00ZTextJournal contributioninfo:eu-repo/semantics/publishedVersiontextcontribution to journal10.1016/j.comcom.2024.02.007https://figshare.com/articles/journal_contribution/An_efficient_failure-resilient_mutual_exclusion_algorithm_for_distributed_systems_leveraging_a_novel_zero-message_overlay_structure/25434763CC BY 4.0info:eu-repo/semantics/openAccessoai:figshare.com:article/254347632024-03-15T03:00:00Z |
| spellingShingle | An efficient failure-resilient mutual exclusion algorithm for distributed systems leveraging a novel zero-message overlay structure Mouna Rabhi (17086969) Engineering Communications engineering Mutual exclusion Distributed systems Failure resilience Overly network Probabilistic protocols |
| status_str | publishedVersion |
| title | An efficient failure-resilient mutual exclusion algorithm for distributed systems leveraging a novel zero-message overlay structure |
| title_full | An efficient failure-resilient mutual exclusion algorithm for distributed systems leveraging a novel zero-message overlay structure |
| title_fullStr | An efficient failure-resilient mutual exclusion algorithm for distributed systems leveraging a novel zero-message overlay structure |
| title_full_unstemmed | An efficient failure-resilient mutual exclusion algorithm for distributed systems leveraging a novel zero-message overlay structure |
| title_short | An efficient failure-resilient mutual exclusion algorithm for distributed systems leveraging a novel zero-message overlay structure |
| title_sort | An efficient failure-resilient mutual exclusion algorithm for distributed systems leveraging a novel zero-message overlay structure |
| topic | Engineering Communications engineering Mutual exclusion Distributed systems Failure resilience Overly network Probabilistic protocols |