THE PROCESSOR IDENTITY PROBLEM

作     者：LIPTON, RJ PARK, A 

作者机构：UNIV CALIF DAVISCALIF PRIMATE RES CTRDIV COMP SCIDAVISCA 95616 

出 版 物：《INFORMATION PROCESSING LETTERS》 (信息处理快报)

年 卷 期：1990年第36卷第2期

页      面：91-94页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Computer system initialization parallel algorithms probabilistic algorithms synchronization 

摘      要：This paper investigates the problem of assigning unique identifiers to processors that communicate through shared memory. Solutions to fundamental multiprocessor coordination problems such as the Mutual Exclusion Problem and the Choice Coordination Problem often rely on unique identifiers. We present a probabilistic protocol that solves this Processor Identity Problem for asynchronous processors that communicate through a common shared memory. This protocol requires no central arbiter, and all processors start in exactly the same state. The use of our protocol simplifies shared memory processor design by eliminating the need to encode processor identifiers in system hardware or software structures.