Linearizing peer-to-peer systems with Oracles

We study distributed linearization or topological sorting in peer-to-peer networks. We define strict and eventual variants of the problem. We consider these problems restricted to existing peer identifiers or without this restriction. None of these variants are solvable in the asynchronous message-p...

Full description

Bibliographic Details
Main Authors:	Mohd. Nor, Rizal, Nesterenko, Mikhail, Tixeuil, Sébastien
Format:	Conference or Workshop Item
Language:	English
Published:	Springer 2013
Subjects:	QA75 Electronic computers. Computer science
Online Access:	http://irep.iium.edu.my/33051/ http://irep.iium.edu.my/33051/ http://irep.iium.edu.my/33051/ http://irep.iium.edu.my/33051/1/linearizingp2pwithoracles.pdf

id	iium-33051
recordtype	eprints
spelling	iium-330512015-12-18T13:56:59Z http://irep.iium.edu.my/33051/ Linearizing peer-to-peer systems with Oracles Mohd. Nor, Rizal Nesterenko, Mikhail Tixeuil, Sébastien QA75 Electronic computers. Computer science We study distributed linearization or topological sorting in peer-to-peer networks. We define strict and eventual variants of the problem. We consider these problems restricted to existing peer identifiers or without this restriction. None of these variants are solvable in the asynchronous message-passing system model. We define a collection of oracles and prove which oracle combination is necessary to enable a solution for each variant of the linearization problem. We then present a linearization algorithm. We prove that this algorithm and a specific combination of the oracles solves each stated variant of the linearization problem. Springer 2013 Conference or Workshop Item PeerReviewed application/pdf en http://irep.iium.edu.my/33051/1/linearizingp2pwithoracles.pdf Mohd. Nor, Rizal and Nesterenko, Mikhail and Tixeuil, Sébastien (2013) Linearizing peer-to-peer systems with Oracles. In: 15th Internationl Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2013), 13-16 Nov 2013, Osaka. http://dx.doi.org/10.1007/978-3-319-03089-0_16 10.1007/978-3-319-03089-0_16
repository_type	Digital Repository
institution_category	Local University
institution	International Islamic University Malaysia
building	IIUM Repository
collection	Online Access
language	English
topic	QA75 Electronic computers. Computer science
spellingShingle	QA75 Electronic computers. Computer science Mohd. Nor, Rizal Nesterenko, Mikhail Tixeuil, Sébastien Linearizing peer-to-peer systems with Oracles
description	We study distributed linearization or topological sorting in peer-to-peer networks. We define strict and eventual variants of the problem. We consider these problems restricted to existing peer identifiers or without this restriction. None of these variants are solvable in the asynchronous message-passing system model. We define a collection of oracles and prove which oracle combination is necessary to enable a solution for each variant of the linearization problem. We then present a linearization algorithm. We prove that this algorithm and a specific combination of the oracles solves each stated variant of the linearization problem.
format	Conference or Workshop Item
author	Mohd. Nor, Rizal Nesterenko, Mikhail Tixeuil, Sébastien
author_facet	Mohd. Nor, Rizal Nesterenko, Mikhail Tixeuil, Sébastien
author_sort	Mohd. Nor, Rizal
title	Linearizing peer-to-peer systems with Oracles
title_short	Linearizing peer-to-peer systems with Oracles
title_full	Linearizing peer-to-peer systems with Oracles
title_fullStr	Linearizing peer-to-peer systems with Oracles
title_full_unstemmed	Linearizing peer-to-peer systems with Oracles
title_sort	linearizing peer-to-peer systems with oracles
publisher	Springer
publishDate	2013
url	http://irep.iium.edu.my/33051/ http://irep.iium.edu.my/33051/ http://irep.iium.edu.my/33051/ http://irep.iium.edu.my/33051/1/linearizingp2pwithoracles.pdf
first_indexed	2023-09-18T20:47:44Z
last_indexed	2023-09-18T20:47:44Z
_version_	1777409788195373056

Linearizing peer-to-peer systems with Oracles

Similar Items