Search

Your search keyword '"Vector clock"' showing total 480 results
Start Over Descriptor "Vector clock"

Refine your results

more »

more »

more »
480 results on '"Vector clock"'

2. The Bloom Clock to Characterize Causality in Distributed Systems

Author

Kshemkalyani, Ajay D., Misra, Anshuman, Kacprzyk, Janusz, Series Editor, Pal, Nikhil R., Advisory Editor, Bello Perez, Rafael, Advisory Editor, Corchado, Emilio S., Advisory Editor, Hagras, Hani, Advisory Editor, Kóczy, László T., Advisory Editor, Kreinovich, Vladik, Advisory Editor, Lin, Chin-Teng, Advisory Editor, Lu, Jie, Advisory Editor, Melin, Patricia, Advisory Editor, Nedjah, Nadia, Advisory Editor, Nguyen, Ngoc Thanh, Advisory Editor, Wang, Jun, Advisory Editor, Barolli, Leonard, editor, Li, Kin Fun, editor, Enokido, Tomoya, editor, and Takizawa, Makoto, editor

Published
2021
Full Text
View/download PDF

3. The Bloom Clock for Causality Testing

Author

Misra, Anshuman, Kshemkalyani, Ajay D., Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Goswami, Diganta, editor, and Hoang, Truong Anh, editor

Published
2021
Full Text
View/download PDF

4. On the Growth of the Prime Numbers Based Encoded Vector Clock

Author

Kshemkalyani, Ajay D., Voleti, Bhargav, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Weikum, Gerhard, Series Editor, Fahrnberger, Günter, editor, Gopinathan, Sapna, editor, and Parida, Laxmi, editor

Published
2019
Full Text
View/download PDF

5. Probabilistic Causal Message Ordering

Author

Mostéfaoui, Achour, Weiss, Stéphane, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, and Malyshkin, Victor, editor

Published
2017
Full Text
View/download PDF

7. Prime clock: Encoded vector clock to characterize causality in distributed systems.

Author

Kshemkalyani, Ajay D., Shen, Min, and Voleti, Bhargav

Subjects
*LARGE scale systems, *CLOCKS & watches, *PRIME numbers, *AUTOREGRESSIVE models
Abstract

The vector clock is a fundamental tool for tracking causality in distributed applications. Unfortunately, it does not scale well to large systems because each process needs to maintain a vector of size n , where n is the total number of processes in the system. To address this problem, we propose the prime clock, which is based on the encoding of the vector clock using prime numbers and uses a single number to represent vector time. We propose the operations on the encoded vector clock (EVC). We then show how to timestamp global states and how to perform operations on the global states using the EVC. Using a theoretical analysis and a simulation model, we evaluate the growth rate of the size of the EVC. The EVC is seen to grow very fast and hence it does not appear to offer a general purpose practical replacement of vector clocks. To address this drawback, we propose several scalability techniques for the EVC that can allow the use of the EVC in practical applications. We then present two case studies of detecting memory consistency errors in MPI one-sided applications and of dynamic race detection in multi-threaded environments, that use a combination of two of these scalability techniques. The results show that the EVC is not just a theoretical concept, but it is applicable to practical problems and can compete in terms of both space and time requirements with other known protocols. • We propose a single integer encoded vector clock (EVC) based on prime numbers. • We give various operations on EVC and evaluate the complexity of EVC. • EVCs tend to grow very fast. • We give scalability techniques for reducing the size of EVC. • Two case studies justify that EVC can perform better than vector clock. [ABSTRACT FROM AUTHOR]

Published
2020
Full Text
View/download PDF

10. Making Operation-Based CRDTs Operation-Based

Author

Baquero, Carlos, Almeida, Paulo Sérgio, Shoker, Ali, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Kobsa, Alfred, Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Magoutis, Kostas, editor, and Pietzuch, Peter, editor

Published
2014
Full Text
View/download PDF

11. RedCard: Redundant Check Elimination for Dynamic Race Detectors

Author

Flanagan, Cormac, Freund, Stephen N., Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, and Castagna, Giuseppe, editor

Published
2013
Full Text
View/download PDF

13. K-Resilient Session Guarantees Synchronization Protocol for Mobile Ad-Hoc Networks

Author

Brzeziński, Jerzy, Dwornikowski, Dariusz, Piątkowski, Łukasz, Sobański, Grzegorz, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Wyrzykowski, Roman, editor, Dongarra, Jack, editor, Karczewski, Konrad, editor, and Waśniewski, Jerzy, editor

Published
2012
Full Text
View/download PDF

14. Consistent Rollback Protocols for Autonomic ASSISTANT Applications

Author

Bertolli, Carlo, Mencagli, Gabriele, Vanneschi, Marco, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Alexander, Michael, editor, D’Ambra, Pasqua, editor, Belloum, Adam, editor, Bosilca, George, editor, Cannataro, Mario, editor, Danelutto, Marco, editor, Di Martino, Beniamino, editor, Gerndt, Michael, editor, Jeannot, Emmanuel, editor, Namyst, Raymond, editor, Roman, Jean, editor, Scott, Stephen L., editor, Traff, Jesper Larsson, editor, Vallée, Geoffroy, editor, and Weidendorfer, Josef, editor

Published
2012
Full Text
View/download PDF

15. A Versatile STM Protocol with Invisible Read Operations That Satisfies the Virtual World Consistency Condition

Author

Imbs, Damien, Raynal, Michel, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Kutten, Shay, editor, and Žerovnik, Janez, editor

Published
2010
Full Text
View/download PDF

18. Effective Program Verification for Relaxed Memory Models

Author

Burckhardt, Sebastian, Musuvathi, Madanlal, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Gupta, Aarti, editor, and Malik, Sharad, editor

Published
2008
Full Text
View/download PDF

19. Debugging and Testing Middleware with Aspect-Based Control-Flow and Causal Patterns

Author

Benavides Navarro, Luis Daniel, Douence, Rémi, Südholt, Mario, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Issarny, Valérie, editor, and Schantz, Richard, editor

Published
2008
Full Text
View/download PDF

20. A Formal Approach to Detect Functionally Irrelevant Barriers in MPI Programs

Author

Sharma, Subodh, Vakkalanka, Sarvani, Gopalakrishnan, Ganesh, Kirby, Robert M., Thakur, Rajeev, Gropp, William, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Lastovetsky, Alexey, editor, Kechadi, Tahar, editor, and Dongarra, Jack, editor

Published
2008
Full Text
View/download PDF

21. On the Performance of Transparent MPI Piggyback Messages

Author

Schulz, Martin, Bronevetsky, Greg, de Supinski, Bronis R., Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Lastovetsky, Alexey, editor, Kechadi, Tahar, editor, and Dongarra, Jack, editor

Published
2008
Full Text
View/download PDF

22. Parametric and Sliced Causality

Author

Chen, Feng, Roşu, Grigore, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Damm, Werner, editor, and Hermanns, Holger, editor

Published
2007
Full Text
View/download PDF

23. Global State Detection Based on Peer-to-Peer Interactions

Author

Chandra, Punit, Kshemkalyani, Ajay D., Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Yang, Laurence T., editor, Amamiya, Makoto, editor, Liu, Zhen, editor, Guo, Minyi, editor, and Rammig, Franz J., editor

Published
2005
Full Text
View/download PDF

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

Author

Tommaso Pozzetti and Ajay D. Kshemkalyani

Subjects
Theoretical computer science, Computational Theory and Mathematics, Shared memory, Hardware and Architecture, Computer science, Vector clock, Signal Processing, Scalar (mathematics), Message passing, Prime number, Logical clock
Abstract

Causality tracking among events is a fundamental challenge in distributed environments. Much previous work on this subject has 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 (VC) in scalar numbers through the use of prime numbers, to improve performance and scalability. 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, the advantage of REVC’s growth rate with respect to EVC’s growth rate. 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 $\text{DJIT}^+$ DJIT + to show how the REVC can help in achieving higher performance with respect to the Vector Clock.

Published
2021

26. A General Model for Reachability Testing of Concurrent Programs

Author

Carver, Richard H., Lei, Yu, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Davies, Jim, editor, Schulte, Wolfram, editor, and Barnett, Mike, editor

Published
2004
Full Text
View/download PDF

27. Detecting Data Races in Sequential Programs with DIOTA

Author

Ronsse, Michiel, Maebe, Jonas, De Bosschere, Koen, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Danelutto, Marco, editor, Vanneschi, Marco, editor, and Laforenza, Domenico, editor

Published
2004
Full Text
View/download PDF

28. A Concept of Replicated Remote Method Invocation

Author

Brzezinski, Jerzy, Sobaniec, Cezary, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Bubak, Marian, editor, van Albada, Geert Dick, editor, Sloot, Peter M. A., editor, and Dongarra, Jack, editor

Published
2004
Full Text
View/download PDF

29. A Lightweight Message Logging Scheme for Fault Tolerant MPI

Author

Lee, Inseon, Yeom, Heon Y., Park, Taesoon, Park, Hyoungwoo, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Wyrzykowski, Roman, editor, Dongarra, Jack, editor, Paprzycki, Marcin, editor, and Waśniewski, Jerzy, editor

Published
2004
Full Text
View/download PDF

30. Parallel Program Design Tool with Application Control Methods Based on Global States

Author

Borkowski, Janusz, Tudruj, Marek, Kopanski, Damian, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Wyrzykowski, Roman, editor, Dongarra, Jack, editor, Paprzycki, Marcin, editor, and Waśniewski, Jerzy, editor

Published
2004
Full Text
View/download PDF

34. Database Replication Using Epidemic Communication

Author

Holliday, JoAnne, Agrawal, Divyakant, El Abbadi, Amr, Goos, Gerhard, editor, Hartmanis, Juris, editor, van Leeuwen, Jan, editor, Bode, Arndt, editor, Ludwig, Thomas, editor, Karl, Wolfgang, editor, and Wismüller, Roland, editor

Published
2000
Full Text
View/download PDF

36. Prime clock: Encoded vector clock to characterize causality in distributed systems

Author

Bhargav Voleti, Min Shen, and Ajay D. Kshemkalyani

Subjects
Computer Networks and Communications, Vector clock, Computer science, Distributed computing, Process (computing), 020206 networking & telecommunications, 02 engineering and technology, Prime (order theory), Theoretical Computer Science, Causality (physics), Consistency (database systems), Artificial Intelligence, Hardware and Architecture, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Software
Abstract

The vector clock is a fundamental tool for tracking causality in distributed applications. Unfortunately, it does not scale well to large systems because each process needs to maintain a vector of size n , where n is the total number of processes in the system. To address this problem, we propose the prime clock, which is based on the encoding of the vector clock using prime numbers and uses a single number to represent vector time. We propose the operations on the encoded vector clock (EVC). We then show how to timestamp global states and how to perform operations on the global states using the EVC. Using a theoretical analysis and a simulation model, we evaluate the growth rate of the size of the EVC. The EVC is seen to grow very fast and hence it does not appear to offer a general purpose practical replacement of vector clocks. To address this drawback, we propose several scalability techniques for the EVC that can allow the use of the EVC in practical applications. We then present two case studies of detecting memory consistency errors in MPI one-sided applications and of dynamic race detection in multi-threaded environments, that use a combination of two of these scalability techniques. The results show that the EVC is not just a theoretical concept, but it is applicable to practical problems and can compete in terms of both space and time requirements with other known protocols.

Published
2020

44. Scalability approaches for causal multicast: a survey.

Author

Juan-Marín, Rubén, Decker, Hendrik, Armendáriz-Íñigo, José, Bernabéu-Aubán, José, and Muñoz-Escoí, Francesc

Subjects
*SCALABILITY, *INTERNET searching, *ELECTRONIC commerce, *INTERNET in public administration, *MULTICASTING (Computer networks)
Abstract

Many distributed services need to be scalable: internet search, electronic commerce, e-government $$\ldots $$ In order to achieve scalability those applications rely on replicated components. Because of the dynamics of growth and volatility of customer markets, applications need to be hosted by adaptive systems. In particular, the scalability of the reliable multicast mechanisms used for supporting the consistency of replicas is of crucial importance. Reliable multicast may propagate updates in a pre-defined order (e.g., FIFO, total or causal). Since total order needs more communication rounds than causal order, the latter appears to be the preferable candidate for achieving multicast scalability, although the consistency guarantees based on causal order are weaker than those of total order. This paper provides a historical survey of different scalability approaches for reliable causal multicast protocols. [ABSTRACT FROM AUTHOR]

Published
2016
Full Text
View/download PDF

47. Preserving stabilization while practically bounding state space using incorruptible partially synchronized clocks

Author

Vidhya Tekken Valapil and Sandeep S. Kulkarni

Subjects
Computer Networks and Communications, Computer science, Vector clock, Clock drift, 0102 computer and information sciences, Topology, 01 natural sciences, Theoretical Computer Science, 03 medical and health sciences, Variable (computer science), 0302 clinical medicine, Computational Theory and Mathematics, 010201 computation theory & mathematics, Hardware and Architecture, 030220 oncology & carcinogenesis, Bounded function, Logical clock, State space, Transient (computer programming), Mutual exclusion
Abstract

Stabilization is a key dependability property for dealing with unanticipated transient faults, as it guarantees that even in the presence of such faults, the system will recover to states where it satisfies its specification. One of the desirable attributes of stabilization is the use of bounded space for each variable. In this paper, we present an algorithm that transforms a stabilizing program that uses variables with unbounded domain into a stabilizing program that uses bounded variables by using partially synchronized physical time. Specifically, our algorithm relies on bounded clock drift $$\epsilon $$ among processes and message delivery that either delivers the message in time $$\delta $$ or loses it. If we let $$\epsilon $$ to be as much as 100 s and $$\delta $$ to be as much as 1 h, this property is satisfied by any practical system. While non-stabilizing programs (that do not handle transient faults) can deal with unbounded variables by assigning large enough but bounded space, stabilizing programs—that need to deal with arbitrary transient faults—cannot do the same since a transient fault may corrupt the variable to its maximum value. We show that our transformation algorithm is applicable to several problems including logical clocks, vector clocks, mutual exclusion, diffusing computations, and so on. Moreover, our approach can also be used to bound counters used in an earlier work by Katz and Perry for adding stabilization to a non-stabilizing program. By combining our algorithm with that work by Katz and Perry and by assuming incorruptible partially synchronized clocks, it would be possible to provide stabilization for a rich class of problems, by assigning large enough but bounded space for variables.

Published
2019

48. A time-stamping system to detect memory consistency errors in MPI one-sided applications

Author

Karl Fürlinger, Thanh-Dang Diep, Kien Trung Pham, and Nam Thoai

Subjects
MPICH, Computer Networks and Communications, Vector clock, Computer science, 010103 numerical & computational mathematics, computer.software_genre, Supercomputer, 01 natural sciences, Computer Graphics and Computer-Aided Design, Execution time, Theoretical Computer Science, 010101 applied mathematics, Consistency (database systems), Computer engineering, Artificial Intelligence, Hardware and Architecture, Synchronization (computer science), Scalability, 0101 mathematics, computer, Time complexity, Software, Debugger
Abstract

Many high performance computing applications have been developed by using MPI one-sided communication. The separation between data movement and synchronization poses enormous challenges for programmers in preserving the reliability of programs. One of those challenges is the detection of memory consistency errors, which are a notorious bug, degrading the reliability and performance of programs. Even an MPI expert can easily make these mistakes. The lockopts bug, which occurred in an RMA test case of the MPICH MPI implementation, is an example for this situation. MC-Checker is the most effective debugger in solving the memory consistency errors. MC-Checker did ignore the transitive ordering of the happened-before relation to ensure the acceptable overheads in terms of time complexity. Consequently, MC-Checker is prone to error due to the source of false positives attributable to the ignorance of the transitive ordering of the happened-before relation. To address this issue, we propose a time-stamping system based on the encoded vector clock to help preserve the full happened-before relation with reasonable overhead. The system is implemented in MC-CChecker, which is an enhancement of MC-Checker. The experimental findings prove that MC-CChecker not only effectively detects memory consistency errors like MC-Checker did, but also completely eliminates the potential source of false positives, which is a major limitation of MC-Checker while still retaining acceptable overheads of execution time and memory usage. Especially, MC-CChecker is fairly scalable when processing a large number of trace files generated from running the lockopts up to 8192 processes.

Published
2019

49. Virtual time and its application to data race detection.

Author

YU Zhen, SU Xiaohong, WANG Tiantian, and MA Peijun

Abstract

Aiming at applying virtual time mechanism to data race detection, a model is proposed to uniformly describe different implementation forms of virtual time. We firstly establish an abstract model for a distributed execution. Based on this model, we give a unified description on virtual time's three basic implementation forms; scalar time system, vector time system and matrix time system. Furthermore, we take vector time system and matrix time system for examples to illustrate four optimization techniques for virtual time. At last, we discuss the problems to be solved when applying virtual time to data races detection in shared - memory concurrent systems and four application examples. The model proposed in this paper unifies different implementation forms of virtual time and reduces the difficulty of applying virtual time to data race detection. [ABSTRACT FROM AUTHOR]

Published
2015
Full Text
View/download PDF

50. The Bloom Clock for Causality Testing

Author

Ajay D. Kshemkalyani and Anshuman Misra

Subjects
020203 distributed computing, Computer science, Vector clock, Probabilistic logic, 020206 networking & telecommunications, 02 engineering and technology, Bloom filter, Causality (physics), 0202 electrical engineering, electronic engineering, information engineering, False positive paradox, Overhead (computing), False positive rate, Timestamp, Algorithm
Abstract

Testing for causality between events in distributed executions is a fundamental problem. Vector clocks solve this problem but do not scale well. The probabilistic Bloom clock can determine causality between events with lower space, time, and message-space overhead than vector clock; however, predictions suffer from false positives. We give the protocol for the Bloom clock based on Counting Bloom filters and study its properties including the probabilities of a positive outcome and a false positive. We show the results of extensive experiments to determine how these above probabilities vary as a function of the Bloom timestamps of the two events being tested, and to determine the accuracy, precision, and false positive rate of a slice of the execution containing events in the temporal proximity of each other. Based on these experiments, we make recommendations for the setting of the Bloom clock parameters. We postulate the causality spread hypothesis from the application’s perspective to indicate whether Bloom clocks will be suitable for correct predictions with high confidence. The Bloom clock design can serve as a viable space-, time-, and message-space-efficient alternative to vector clocks if false positives can be tolerated by an application.

Published
2020

Catalog

Books, media, physical & digital resources
See catalog results