polito.it
Politecnico di Torino (logo)

Resettable Encoded Vector Clock for Causality Analysis with an Application to Dynamic Race Detection

Tommaso Pozzetti

Resettable Encoded Vector Clock for Causality Analysis with an Application to Dynamic Race Detection.

Rel. Riccardo Sisto, Ajay Kshemkalyani. Politecnico di Torino, Corso di laurea magistrale in Ingegneria Informatica (Computer Engineering), 2019

[img]
Preview
PDF (Tesi_di_laurea) - Tesi
Document access: Anyone
Licenza: Creative Commons Attribution Non-commercial No Derivatives.

Download (491kB) | Preview
Abstract:

Causality tracking among events is a fundamental challenge in distributed environments. Most previous work on this subject has been focused on designing an efficient and scalable protocol to represent logical time. Several implementations of logical clocks have been proposed, most recently the Encoded Vector Clock (EVC), a protocol to encode Vector Clocks in scalar numbers through the use of prime numbers, to improve performance and scalability. In this thesis work we propose and formalize the concept of Resettable Encoded Vector Clock (REVC), a new logical clock implementation, which builds on the EVC to tackle its very high growth rate issue. We show how our REVC can be applied in both shared memory systems and message passing systems to achieve a consistent logical clock. We show, through practical examples, a comparison between REVC's and EVC's growth rates, to demonstrate our clock's advantages. Finally, we show a practical application of the REVC to the Dynamic Race Detection problem in multi-threaded environments. We compare our tool to the currently existing VC-based tool DJIT+ to show how the REVC can help in achieving higher performance with respect to the Vector Clock.

Relators: Riccardo Sisto, Ajay Kshemkalyani
Academic year: 2019/20
Publication type: Electronic
Number of Pages: 87
Subjects:
Corso di laurea: Corso di laurea magistrale in Ingegneria Informatica (Computer Engineering)
Classe di laurea: New organization > Master science > LM-32 - COMPUTER SYSTEMS ENGINEERING
Ente in cotutela: UNIVERSITY OF ILLINOIS AT CHICAGO (STATI UNITI D'AMERICA)
Aziende collaboratrici: UNSPECIFIED
URI: http://webthesis.biblio.polito.it/id/eprint/12434
Modify record (reserved for operators) Modify record (reserved for operators)