DocumentCode :
3509444
Title :
The Causal Order is Strict
Author :
James, Jerry ; Mukhopadhyay, Supratik
fYear :
2008
fDate :
21-23 Oct. 2008
Firstpage :
140
Lastpage :
143
Abstract :
The causal order is central to many algorithms in both the message-passing and shared memory models. In the message-passing model, the causal order is clearly a strict, or irreflexive partial, order. However, some shared memory models are defined without reference to time. In those models, the causal order can fail to be a strict order. Existing works have either declared that all non-strict orders are not causal, or assumed that the causal order is strict without proof. We prove that, under a small number of reasonable assumptions about systems, the causal order is strict. In particular, we assume neither a global time model nor that processes issue a single shared memory operation at a time.
Keywords :
distributed algorithms; message passing; shared memory systems; causal order; distributed algorithm; message-passing model; shared memory model; strict order; Broadcasting; Conferences; Distributed computing; History; Intersymbol interference; Message passing; Middleware; Pipelines; Silicon compounds; US Government; Causal Order; Formal Verification;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Future Trends of Distributed Computing Systems, 2008. FTDCS '08. 12th IEEE International Workshop on
Conference_Location :
Kunming
ISSN :
1071-0485
Print_ISBN :
978-0-7695-3377-3
Type :
conf
DOI :
10.1109/FTDCS.2008.33
Filename :
4683127
Link To Document :
بازگشت