Estruturas de dados concorrentes: um estudo de caso em skip graphs. / Concurrent data structures: a case-study on skip graphs

AUTOR(ES)
DATA DE PUBLICAÇÃO

2008

RESUMO

Many existing computer systems are concurrent, or, in other words, they are composed of many entities that, at the same time, operate over some set of shared resources. In this context, we must control the concurrency of the operations, otherwise the interference between them could cause inconsistencies in the shared resources or in the operations themselves. In this text, we specifically discuss concurrent data structures, or, in other words, data structures over which the associated operations -- we consider insertion, removal and search -- could be executed simultaneously by various entities. In order to control the concurrency, we will employ an aproach based on the use of locks, a widely known synchronization primitive in the literature. Our discussion will be presented in terms of data structures called skip graphs, which have interesting properties in other contexts, as the context of distributed systems.

ASSUNTO(S)

análise de complexidade skip graphs skip lists concurrency skip lists skip graphs complexity analisys concorrência

Documentos Relacionados