HyperChromatic trees: a fine-grained approach to distributed algorithms on RedBlack trees

Consultar RECERCAT

Para acceder a los documentos con el texto completo, por favor, siga el siguiente enlace: http://hdl.handle.net/2117/84042

dc.contributor	Universitat Politècnica de Catalunya. Departament de Ciències de la Computació
dc.contributor.author	Messeguer Peypoch, Xavier
dc.contributor.author	Valles Fuente, Borja
dc.date	1998-03
dc.identifier.citation	Messeguer, X., Valles, B. "HyperChromatic trees: a fine-grained approach to distributed algorithms on RedBlack trees". 1998.
dc.identifier.uri	http://hdl.handle.net/2117/84042
dc.language.iso	eng
dc.relation	LSI-98-13-R
dc.rights	info:eu-repo/semantics/openAccess
dc.subject	Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica
dc.subject	RedBlack trees
dc.subject	Concurrent algorithms
dc.subject	Concurrent rebalancing
dc.subject	Safety and liveness proofs
dc.subject	Local rules
dc.title	HyperChromatic trees: a fine-grained approach to distributed algorithms on RedBlack trees
dc.type	info:eu-repo/semantics/publishedVersion
dc.type	info:eu-repo/semantics/report
dc.description.abstract	We introduce a relaxed version of RedBlack trees. As concurrent algorithms on balanced search trees are nowadays based on local rules, we propose a set of fine-grained local rules that take more advantage of concurrency that previous approaches. Based on them we design a rebalancing concurrent algorithm and prove its correctness. Finally we sketch how to complete this algorithm to include concurrent insertions and deletions.

Subirana Torrent, Juan A.; Messeguer Peypoch, Xavier

Subirana Torrent, Juan A.; Albà, M. Mar; Messeguer Peypoch, Xavier

Messeguer Peypoch, Xavier

Gabarró Vallès, Joaquim; Messeguer Peypoch, Xavier

Bougé, Luc; Gabarró Vallès, Joaquim; Messeguer Peypoch, Xavier; Schabanel, Nicolas

Coordinación

Patrocinio