Linearizing peer-to-peer systems with Oracles

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.

PDF - Published Version Restricted to Repository staff only Download (229kB) | Request a copy

Abstract

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.

Item Type:	Conference or Workshop Item (Full Paper)
Additional Information:	5251/33051 ISBN: 9783319030883
Uncontrolled Keywords:	Peer-to-Peer Systems
Subjects:	Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Kulliyyahs/Centres/Divisions/Institutes (Can select more than one option. Press CONTROL button):	Kulliyyah of Information and Communication Technology > Department of Computer Science Kulliyyah of Information and Communication Technology > Department of Computer Science
Depositing User:	Dr. Rizal Mohd Nor
Date Deposited:	18 Dec 2013 15:47
Last Modified:	18 Dec 2015 21:56
URI:	http://irep.iium.edu.my/id/eprint/33051

Actions (login required)

View Item