I detta dokument presenterar vi en distribuerad algoritm för ömsesidig uteslutning baserad på omkastning av vägar. Algoritmen använder inte logiska klockor för att serialisera samtidiga händelser, och alla variabler begränsas. När en process åberopar ett kritiskt avsnitt, skickar den en begäran till svansen av en kö. Ett dynamiskt rotat träd ger stigen till svansen. Algoritmen kräver endast O(Log (n))-meddelanden i genomsnitt, där n är antalet processer i nätverket. Prestandaanalysen av algoritmen bygger på att generera formella effektserier. Detta arbete finansierades delvis av CNRS: Unité associée 040822 och C3-samordnade forskningsprogram.
Enligt vissa antaganden om sannolikhetsfördelningen för transaktioner vid noder visas det REF att ett förväntat O(log n)-meddelande krävs per köoperation, där n är antalet noder i grafen.
A Log (N) Distributed Mutual Exclusion Algorithm Based on the Path Reversal
{'venue': 'Journal of Parallel and Distributed Computing', 'journal': None, 'mag_field_of_study': ['Computer Science']}