For our purposes, a parallel workload is expected to comprise of - Computation, Lock Requests, Lock Releases, Memory Requests and Barrier Synchronization.
Computation has associated with it a specific computation duration, during which the process does not communicate with any of its peers. Lock requests and releases are made for some specific locks - each with its unique lock identifier. The lock requests are modeled as a distributed queue, which is served in the FIFO order. Each lock has a initial lock manager, to which the first lock request is made. Each subsequent lock request is then made to the previous owner of the lock, who becomes the manager for that period. Each lock request is, thus, serviced by the use of only two messages - a lock request and a lock grant. Obviously, lock requests made by the process to itself (it the same process is the lock manager) is served without any exchange of messages. When a lock is released by a process, it sends a lock grant message to the requester if there are any waiters in the distributed queue.
Memory requests are can be made any process to any of its peers, and the memory request is served with a message, whose size is determined by the size of memory that is being returned. Barrier arrival messages are sent by all the processes to a pre-determined barrier master process. The barrier master sends out barrier release messages to all the other processes once it has got the arrival message from all the processes, including itself.
Any kind of request message sent results in the requesting process to block till the response for the process is received. A process services requests for memory, requests for locks and handles barrier arrival messages with a higher priority than its local computation. For the purpose of simplicity it has been assumed that all messages that are not memory request responses have a fixed size. Also, we assume that processing of messages have no overhead, except the time spent in receiving the same, which depends on the size of the message.