Distributed coordination of task-oriented services using graph coloring algorithm

Abstract

With the combination of emerging paradigms, such as service-oriented computing and ubiquitous computing, end-users are now provided with a myriad of services to utilize smart objects to achieve their goals. The most promising standard to utilize these services is WS-BPEL, which employs centralized coordination for simpler management of interaction and synchronization. However, centralized approaches suffer from scalability, heterogeneity, and inefficiency, especially when the system is managed across different entities. Moreover, it is quite unrealistic to assume that one client device has permissions to access all available operations of smart objects as well as support different types of required communication interfaces. Hence, in this paper, I propose a novel distributed coordination scheme that helps end-users collaborate more efficiently to achieve their common goals. Unlike traditional distributed coordination methods, that are limited to static environments, the proposed scheme incorporates dynamic ubiquitous computing environments where requirements of tasks and available resources can be altered throughout task execution. Under the proposed scheme, mobile client devices are able to self-collaborate without a dedicated central server by spontaneously electing a task coordinator among them. Moreover, the proposed scheme also deals with dynamic events such as the joining and leaving of users, clients and tasks, supporting dynamic reallocation while keeping them transparent for end-users. Finally, the proposed scheme is evaluated through simulations at different numbers of services and client devices, showing improved results in performance optimality, assignment efficiency, and dependency coverage of composition.