Voting and Auction based Monitors

Condition variables and monitors go hand in hand.  There are various monitor protocols: Signal-and-Continue (SC), Signal-and-Urgent-Wait (SU), Signal-and-Exit, Urgent-Signal-and-Continue etc.  Basically these protocols define what order threads get to enter, reenter, and exit methods in a monitor.  They are defined by a first-come first-served (FCFS) queuing schemes to ensure their specific protocols are met.

I am proposing two protocols that are based on Voting and Auctions.  The idea here is that threads get to enter in the order in which they were voted or if they won the auction.  The auction would be like the auctions that google uses for placement of ads on a page.

SU Monitor for producer consumer problem

Monitor queues for producer consumer problem.

The threads could base their decisions on data the monitor has about each of the threads, data the thread has collected, or some other way defined by the coder.  This is the interesting part.

I think that there may be a way to use Arrow’s Theorem to provide some guarantees about some things.

Schepperle, H., & Bohm, K. (2008). Auction-Based Traffic Management: Towards Effective Concurrent Utilization of Road Intersections. E-Commerce Technology and the Fifth …, 105–112. doi:10.1109/CEC/EEE.2008.9

The above reference seems to be heading in the direction I was thinking except they were narrower.

 

And while I was writing this I found http://www.isi.edu/~lerman/projects/task/ has some good papers on mathematical modeling of multiagent systems.

Leave a Reply