AbstractDistributed systems become ubiquitous by allowing users access to a wide range of services at any time, anywhere, and from a variety of devices. In these open environments where there are many opportunities for both fraudulent services and misbehaving clients, service discovery systems are subject to security challenges. Controlling services' access is one of the fundamental issues that must be faced in the context of service discovery in distributed and open environments. Therefore, secure accesses and utilization of available services must be ensured for users. In our previous work, a contract-based approach for controlling the service access in a distributed computing context was presented. In this paper, we address the purpose and the usage of digital signature on negotiated electronic queries between a server and clients in service discovery systems and web service composition. The paper discusses the combined use of Timed Event Graphs and (max, +)- algebra to model, evaluate and optimize the performance of the signature process and client requests validation by a service provider (server). Based on an optimization resource allocation algorithm, an improvement study of the quality of service offered to the clients, in terms of waiting times and validation of their requests, is proposed. The results are reported and show the efficiency of the use of the proposed formal tools for performance analysis, evaluation and tuning of the considered process.