NDLI: On space complexity of self-stabilizing leader election in mediated population protocol

Please wait, while we are loading the content...

On space complexity of self-stabilizing leader election in mediated population protocol

Content Provider	Springer Nature Link
Author	Mizoguchi, Ryu Kijima, Shuji Yamashita, Masafumi
Copyright Year	2012
Abstract	Chatzigiannakis et al. (Lect Notes Comput Sci 5734:56–76, 2009) extended the Population Protocol (PP) of Angluin et al. (2004) and introduced the Mediated Population Protocol (MPP) by introducing an extra memory on every agent-to-agent communication link (i.e., edge), in order to model more powerful networks of mobile agents with limited resources. For a general distributed system of autonomous agents, Leader Election (LE) plays a key role in their efficient coordination. A Self-Stabilizing (SS) protocol has ideal properties required for distributed systems of huge numbers of not highly reliable agents typically modeled by PP or MPP; it does not require any initialization and tolerates a finite number of transient failures. Cai et al. (2009) showed that for a system of $$n$$ agents, any PP for SS-LE requires at least $$n$$ agent-states, and gave a PP with $$n$$ agent-states for SS-LE. In this paper, we show, for a system of $$n$$ agents, any MPP for SS-LE with 2 edge-states (i.e., 1 bit memory) on every edge requires at least $$(1/2) \lg {n}$$ agent-states, and give an MPP for SS-LE with $$(2/3)n$$ agent-states and 2 edge-states on every edge. Furthermore, we show that a constant number of edge-states on every edge do not help in designing an MPP for SS-LE with a constant number of agent-states, and that there is no MPP for SS-LE with 2 agent-states, regardless of the number of edge-states; the edge-state is not a complete alternative of the agent-state, although it can help in reducing the number of agent-states, when solving SS-LE.
Starting Page	451
Ending Page	460
Page Count	10
File Format	PDF
ISSN	01782770
Journal	Distributed Computing
Volume Number	25
Issue Number	6
e-ISSN	14320452
Language	English
Publisher	Springer-Verlag
Publisher Date	2012-09-01
Publisher Place	Berlin/Heidelberg
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Population protocols Mediated population protocols Leader election Self-stabilization Space complexity Computer Communication Networks Theory of Computation Computer Systems Organization and Communication Networks Computer Hardware Software Engineering/Programming and Operating Systems
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science Computer Networks and Communications Computational Theory and Mathematics Hardware and Architecture

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Randomized self-stabilizing and space optimal leader election under arbitrary scheduler on rings

Fault-containing self-stabilizing distributed protocols

Fast computation by population protocols with a leader

Randomized leader election

Self-stabilizing smoothing and balancing networks

How much memory is needed for leader election

Leader election using loneliness detection

Leader election for anonymous asynchronous agents in arbitrary networks

HyperTree for self-stabilizing peer-to-peer systems

On space complexity of self-stabilizing leader election in mediated population protocol

Similar Documents

Randomized self-stabilizing and space optimal leader election under arbitrary scheduler on rings

Fault-containing self-stabilizing distributed protocols

Fast computation by population protocols with a leader

Randomized leader election

Self-stabilizing smoothing and balancing networks

How much memory is needed for leader election

Leader election using loneliness detection

Leader election for anonymous asynchronous agents in arbitrary networks

HyperTree for self-stabilizing peer-to-peer systems

On space complexity of self-stabilizing leader election in mediated population protocol