The Naimi–Trehel algorithm is an
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
for achieving
mutual exclusion
In computer science, mutual exclusion is a property of concurrency control, which is instituted for the purpose of preventing race conditions. It is the requirement that one thread of execution never enters a critical section while a concurr ...
in a
distributed system
Distributed computing is a field of computer science that studies distributed systems, defined as computer systems whose inter-communicating components are located on different networked computers.
The components of a distributed system commun ...
.
Unlike
Lamport's distributed mutual exclusion algorithm and its related version, this algorithm does not use
logical clock
A logical clock is a mechanism for capturing chronological and causal relationships in a distributed system. Often, distributed systems may have no physically synchronous global clock. In many applications (such as distributed GNU make), if two pro ...
s.
This method requires only
''O''(log(number of processes in the network)) messages on average.
When a process invokes a
critical section
In concurrent programming, concurrent accesses to shared resources can lead to unexpected or erroneous behavior. Thus, the parts of the program where the shared resource is accessed need to be protected in ways that avoid the concurrent access. One ...
, it sends a request to a
queue at a particular processor which is specified by a path built by the algorithm as it runs.
References
article at citeseerx.ist.psu.edu by Mohamed Naimi, Michel Trehel, André Arnold
Concurrency control algorithms
Distributed computing
{{Comp-sci-stub