Non token based solutions to mutual exclusion in distributed computing include Lamport Algorithm. There was a single centralized pending request queue which allowed the processes to enter their critical section on a first come first serve basis. This queue is just a data structure like any other we could support a distributed version of a data structure i.e an integer with increment or double operations. We can use this same strategy to support a distribution of the pending request queue data structure.
Each process keeps a queue of time-stamped requests for critical section sorted in ascending order and a list of known times for all other processes.
To request entry to its critical section P broadcasts <req,t> to all other processes.
When Pj receives a request to enter critical section, a timestamped acknowledgement is returned.
To enter the critical section, P must have req at the head of the reqQ and its timestamp should be smaller than all the known times for all other processes.
On the other hand, to release the critical section, P removes the request from its reqQ and broadcasts a release message to all the other processes.
When a process receives a release message, it removes the P's request from its reqQ. Note that this may cause this process to enter its critical section since it may now have the request with the minimum timestamp.
We can prove that this works by using contradiction. Suppose two processes were both in their critical section These processes Pa and Pb would have their <reqa,ta> and <reqb, tb> respectively at the head of their sorted reqQ.
If we assume that ta < tb. But Pb is in its critical section and so its time stamp must be less than the known time of a at Pb. Hence reqa with timestamp of ta must be in the reqQ at Pb. Therefore reqb is not at the head of Pb's reqQ.
Thus we know that only one process can be in the critical section meeting our goal.