Data processing system and method

• US 20060069942A1
• Filed: 09/02/2005
• Published: 03/30/2006
• Est. Priority Date: 09/04/2004
• Status: Abandoned Application

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Filho, Walfredo Cirne, Sampajo, Livia Maria Rodrigues, Brito, Andrey Elisio Monteiro, Brasilerio, Francisco Vilar
• Application Number:
  US11/219,536
• Publication Number:
  US 20060069942A1
• Time in Patent Office: Days
• US Class Current: 714/4
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

Embodiments of the present invention relate to a data processing system and method and, in particular, to a distributed computing system and method that uses a globally distributed data structure comprising an indication of local state information associated with at least some of the processes constituting a distributed algorithm in influencing at least one of the execution and the termination of those processes.

Claims

1. A synchronous communication system, for use in an asynchronous or hybrid distributed system for executing a distributed algorithm, the system comprising a plurality of processing nodes each running a respective process associated with the distributed algorithm;

and a synchronous communication system for exchanging bounded messages between selected processes within bounded time periods;

the synchronous communication system comprising means to obtain global digest data comprising an indication of events associated with each, or selected, processors of the plurality of processes during a particular time interval.

2. A system as claimed in claim 1 in which the means to obtain the global digest data comprises means to obtain global digest data relating to a number of processes of the plurality of processes.

3. A system as claimed in claim 1 in which the means to obtain global digest data comprises means to obtain the global digest relating to all correct processes of the plurality of processes.

4. A system as claimed in claim 1 comprising means to obtain a plurality of global digest data, each global digest data relating to a respective process of at least some of the plurality of processes.

5. A system as claimed in claim 1 in which the global digests data has a type corresponding to at least one of a synchronisation global digest data and a termination global digest data.

6. A system as claimed in claim 1 in which the global digest data comprises an indication of the operational status of the plurality of processes.

7. A system as claimed in as claimed in claim 6 in which the global digest data can comprise an indication of at least one of those other processors of the plurality of processes that have crashed and those other processors of the plurality of processes that have not crashed.

8. A system as claimed in claim 1 in which the GSD comprises a detection vector having at least one data unit per process of the plurality of processes;

each of the data units providing an indication of the operational status of a respective process.

9. A system as claimed in claim 1 in which the GSD comprises a reception matrix comprising an indication of communication exchanges between the plurality of processes.

10. A system as claimed in claim 9 in which the reception matrix is an n×

n in which an element [i,j] represents a perception of a first process, p_i, of the processing of a second process, p_j.

11. A system as claimed in claim 1 in which the global digest data comprises an ordered set of a number of global digest data.

12. A system as claimed in claim 1 in which the global digest data is well formed.

13. A system as claimed in claim 12 in which the global digest data is such that, for every execution of a synchronisation step, it comprises all of the following properties:

Synchronisation in which at least one SC-GSD is formed such that this property guarantees that all correct processes of the plurality of processes will reach a point in the execution of the algorithm step such that the outcome of the step is known;

Termination in which at least one TC-GSD is formed for every process of the plurality of processes that does not crash before or during the execution of the step, which guarantees that all correct processes of the plurality of processes finish the execution of an algorithm step and are able to proceed to the next step, if there is such a step;

Ordered formation in which no TC-GSD can be formed before a SC-GSD is formed; and

Monotonicity in which if a TC-GSD is formed for a process, p_i, then every subsequent GSD formed is also a TC-GSD for pi.

14. A system as claimed in claim 1 in which the size of the GSD is bounded.

15. A system as claimed in claim 1 in which each of the plurality of processes comprises a respective state machine.

16. A system as claimed in claim 15 in which the state machine comprises at least one of an initial state, a recovery state, a synchronisation and final state.

17. A system as claimed in claim 16 in which a transition from the initial state to the synchronisation and final state occurs if it is determined that the GSD comprises an indication of at least one process of the plurality of processes such that the broadcast message associated with that at least one process has been received by a number of processes of the plurality of processes.

18. A system as claimed in claim 17 in which the number of processes of the plurality of processes comprises all correct processes of the plurality of processes.

19. A system as claimed in claim 16 in which a transition from the initial state to the recovery state occurs if it is determined from the GSD that predeterminable processes of the plurality of processes have an associated operational condition.

20. A system as claimed in claim 19 in which the associated operational condition is a crashed state.

21. A system as claimed in claim 19 in which the predeterminable processes of the plurality of processes are those other processes with corresponding process identification data having a predetermined relationship with identification data of a current process.

22. A system as claimed in claim 21 in which the predeterminable processes of the plurality of processes are those processes having a smaller ID as compared to the ID of the current process.

23. A system as claimed in claim 1 in which the algorithm comprises a predeterminable operational structure.

24. A system as claimed in claim 23 in which the predeterminable operational structure comprises at least one of, and preferably all of, a notification part, a listening part and a synchronisation part.

25. A system as claimed in claim 24 in which the notification part comprises means to send messages relating to a synchronisation step of an associated process to at least selectable processes of the plurality of processes.

26. A system as claimed in claim 24 in which the listening part comprises means for exchanging messages between an associated process and at least selectable processes of the plurality of processes.

27. A system as claimed in claim 24 in which the synchronisation part comprises a detector to detect a prevailing synchronisation condition and means to terminate a synchronisation step of an associated process.

28. A system as claimed in claim 1 in which the synchronous communication system comprises a time division processing arrangement providing substantially contiguous operational time slots.

29. A system as claimed in claim 28 in which the time division processing arrangement comprises a scheduler operable to provide substantially contiguous operational time slots arranged according to a repeating pattern.

30. A system as claimed in claim 29 in which the scheduler comprises means operable such that repeating pattern comprises first, second and third time slots.

31. A system as claimed in claim 30 in which the scheduler is operable such that the first time slot is utilised to provide a globally synchronised clock to the plurality of processes.

32. A system as claimed in claim 30 in which the scheduler is operable such that the second time slot is utilised to exchange messages between the plurality of processes.

33. A system as claimed in claim 30 in which the scheduler is operable such that the third time slot is utilised by the plurality of processes to perform local processing operations.

37. A computer program comprising computer executable code means to implement a system as claimed in claim 1.

34. A synchronous system for use in an asynchronous distributed system for executing a distributed algorithm, comprising a scheduler for exchanging communication messages with a process forming part of the algorithm executable by an asynchronous subsystem of the asynchronous distributed system according to a time division arrangement.

35. A synchronous system as claimed in claim 34 further comprising means to receive at least one message from at least one other process of the distributed algorithm;

the received message being associated with a monotonicity condition.

36. A synchronous system as claimed in claim 35 in which the monotonicity condition is if a TC-GSD is formed for a process p_i, then every subsequent GSD formed is also a TC-GSD for p_i.