Coordinated cooperative task computing using crash-prone processors with unreliable multicast
| Autor: | Davtyan, S., De Prisco, R., Georgiou, Chryssis, Hadjistasi, Theophanis, Schwarzmann, A. A. |
|---|---|
| Přispěvatelé: | Georgiou, Chryssis [0000-0003-4360-0260] |
| Rok vydání: | 2017 |
| Předmět: |
Computer Networks and Communications
Computer science Crash faults Experimental evaluation Crash 0102 computer and information sciences 02 engineering and technology Parallel computing 01 natural sciences Theoretical Computer Science Unreliable multicast Distributed platforms Artificial Intelligence 0202 electrical engineering electronic engineering information engineering Cooperative tasks Message passing algorithm Time complexity Fault-tolerant Fault-tolerant distributed algorithms Task computing Software Hardware and Architecture Multicast 020206 networking & telecommunications Multicasting Message passing 010201 computation theory & mathematics Distributed algorithm Reliable multicast Reliable Multicast |
| Zdroj: | Journal of Parallel and Distributed Computing J.Parallel Distrib.Comput. |
| Popis: | This paper presents a new message-passing algorithm, called Do-UM, for distributed cooperative task computing in synchronous settings where processors may crash, and where any multicasts (or broadcasts) performed by crashing processors are unreliable. We specify the algorithm, prove its correctness and analyse its complexity. We show that its worst case available processor steps is S = Θ t + n log n log log n + f ( n − f ) and that the number of messages sent is less than n 2 t + n f 2 , where n is the number of processors, t is the number of tasks to be executed and f is the number of failures. To assess the performance of the algorithm in practical scenarios, we perform an experimental evaluation on a planetary-scale distributed platform. This also allows us to compare our algorithm with the currently best algorithm that is, however, explicitly designed to use reliable multicast; the results suggest that our algorithm does not lose much efficiency in order to cope with unreliable multicast. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|