A method, comprising: performing by one or more computing nodes, each of which comprises at least one processor core and a memory: beginning execution of a multithreaded application that comprises one or more operations to increment a shared counter, wherein the shared counter is implemented as a data structure that is accessible by a plurality of threads of the multithreaded application that are executing on the one or more computing nodes, wherein the data structure stores a representation of an update probability value, wherein the update probability value indicates a probability that the representation of the update probability value will be updated in response to initiation of an increment operation targeting the shared counter, and wherein a projected value of the shared counter is computable based at least in part on the representation of the update probability value; initiating, by a given thread of the application, an increment operation targeting the shared counter; in response to said initiating, determining whether to perform the increment operation, wherein said determining is dependent, at least in part, on the representation of the update probability stored in the data structure; and in response to determining that the increment operation is to be performed, updating the representation of the update probability value stored in the data structure, wherein the updated representation represents a probability that the updated representation of the update probability value stored in the data structure will be further updated in response to initiation of a subsequent increment operation; wherein one or more of said determining whether to perform the increment operation or said updating the representation of the update probability value are dependent on a pre-determined value of a configurable accuracy parameter. performing by one or more computing nodes, each of which comprises at least one processor core and a memory: beginning execution of a multithreaded application that comprises one or more operations to increment a shared counter, wherein the shared counter is implemented as a data structure that is accessible by a plurality of threads of the multithreaded application that are executing on the one or more computing nodes, wherein the data structure stores a representation of an update probability value, wherein the update probability value indicates a probability that the representation of the update probability value will be updated in response to initiation of an increment operation targeting the shared counter, and wherein a projected value of the shared counter is computable based at least in part on the representation of the update probability value; initiating, by a given thread of the application, an increment operation targeting the shared counter; in response to said initiating, determining whether to perform the increment operation, wherein said determining is dependent, at least in part, on the representation of the update probability stored in the data structure; and in response to determining that the increment operation is to be performed, updating the representation of the update probability value stored in the data structure, wherein the updated representation represents a probability that the updated representation of the update probability value stored in the data structure will be further updated in response to initiation of a subsequent increment operation; wherein one or more of said determining whether to perform the increment operation or said updating the representation of the update probability value are dependent on a pre-determined value of a configurable accuracy parameter. beginning execution of a multithreaded application that comprises one or more operations to increment a shared counter, wherein the shared counter is implemented as a data structure that is accessible by a plurality of threads of the multithreaded application that are executing on the one or more computing nodes, wherein the data structure stores a representation of an update probability value, wherein the update probability value indicates a probability that the representation of the update probability value will be updated in response to initiation of an increment operation targeting the shared counter, and wherein a projected value of the shared counter is computable based at least in part on the representation of the update probability value; initiating, by a given thread of the application, an increment operation targeting the shared counter; in response to said initiating, determining whether to perform the increment operation, wherein said determining is dependent, at least in part, on the representation of the update probability stored in the data structure; and in response to determining that the increment operation is to be performed, updating the representation of the update probability value stored in the data structure, wherein the updated representation represents a probability that the updated representation of the update probability value stored in the data structure will be further updated in response to initiation of a subsequent increment operation; wherein one or more of said determining whether to perform the increment operation or said updating the representation of the update probability value are dependent on a pre-determined value of a configurable accuracy parameter.